System, method and computer program product for schedule recovery

• US 20050071206A1
• Filed: 04/30/2004
• Published: 03/31/2005
• Est. Priority Date: 04/30/2003
• Status: Abandoned Application

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Berge, Matthew E.
• Application Number:
  US10/836,714
• Publication Number:
  US 20050071206A1
• Time in Patent Office: Days
• US Class Current: 705/6
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A system, method and computer program product are provided to permit the efficient recovery from schedule disruptions, such as due to a weather condition, a system outage or the like. The system, method and computer program product evaluate a plurality of leg replicants for at least some flight legs of a plurality of itineraries. The leg replicants may include flight legs that have been subject to a ground delay, cancellation or rerouting. A Lagrangian relaxation technique followed by a Lagrangian heuristic may be used to construct schedules for the itineraries from the leg replicants. During Lagrangian relaxation, some or all of the capacity constraints are relaxed to simplify its solution. During this process, a value may be assigned to each leg replicant that is at least partially based upon an objective function relating value to arrival delay. Flight legs may be swapped between itineraries to improve the resulting schedules.

Claims

1. A method of determining an alternative schedule comprising:

identifying a plurality of leg replicants for at least some legs of a plurality of itineraries; and

evaluating different combinations of the leg replicants for the respective legs of the plurality of itineraries in order to construct schedules for the plurality of itineraries, wherein evaluating different combinations of the leg replicants comprises initially relaxing at least some capacity constraints.

2. A method according to claim 1 wherein evaluating different combinations of the leg replicants comprises utilizing Lagrangian relaxation to initially relax at least some of the capacity constraints and to subsequently reevaluate at least some of the different combinations while subject to the capacity constraints.

3. A method according to claim 2 further comprising assigning a value to each leg replicant.

4. A method according to claim 3 wherein assigning the value comprises assigning the value based upon at least one of distance of the respective leg, seating capacity and an objective function relating value to arrival delay.

5. A method according to claim 3 wherein evaluating different combinations of the leg replicants further comprises identifying the schedules for the plurality of itineraries that are comprised of combinations of the leg replicants that have the largest collective value.

6. A method according to claim 5 wherein identifying the schedules comprises separately determining the schedule for each itinerary that is comprised of leg replicants having the largest collective value while at least some of the capacity constraints are relaxed.

7. A method according to claim 6 wherein evaluating different combinations further comprises:

ordering the schedules that were determined while the capacity constraints are relaxed based upon the collective value of the leg replicants comprising the respective schedules; and

sequentially reevaluating each schedule in order while taking into account the capacity constraints.

8. A method of swapping legs between itineraries comprising:

identifying swap opportunities to swap legs between respective pairs of itineraries;

estimating a benefit of each swap opportunity; and

evaluating, for each swap opportunity that is determined to be beneficial, different combinations of leg replicants for the legs that have been swapped between the respective pair of itineraries in order to construct schedules for the respective pair of itineraries.

9. A method according to claim 8 wherein identifying swap opportunities comprises identifying a swap opportunity between a respective pair of itineraries with each itinerary having a first scheduled flight leg and a subsequent scheduled flight leg, wherein identifying a swap opportunity comprises identifying a pair of itineraries in which:

(i) the subsequent scheduled flight leg of one itinerary have a propagated delay, (ii) the first scheduled flight legs of both itineraries has a common destination airport, and (iii) a difference between scheduled departure times of the subsequent scheduled flight legs of the pair of itineraries is no greater than a predefined time.

10. A method according to claim 8 wherein identifying swap opportunities comprises identifying swap opportunities between pairs of itineraries scheduled to be flown by compatible aircraft.

11. A method according to claim 10 wherein identifying swap opportunities between pairs of itineraries scheduled to be flown by compatible aircraft comprises identifying aircraft to be compatible if the aircraft are one of the same type or operationally equivalent.

12. A method according to claim 8 wherein estimating the benefit of each swap opportunity comprises determining a value of each itinerary to be a sum of a value of each leg included in the itinerary, and wherein the method further comprises determining that a swap opportunity is beneficial if the collective value of the pair of itineraries associated with the swap opportunity exceeds the collective value of the itineraries prior to any swap of legs therebetween.

13. A method according to claim 8 further comprising:

determining a value for each itinerary to be a sum of a value of each leg included in the itinerary following evaluation of different combinations of leg replicants; and

accepting the schedules constructed for the pair of itineraries if the collective value of the pair of itineraries exceeds the collective value of the itineraries prior to any swap of legs therebetween.

14. A method of determining an alternative schedule comprising:

constructing a network for each pool of equipment with each node of the network representing an airport at a predefined period of time and each arc representing a leg replicant for a respective flight leg, wherein each pool of equipment comprises leg replicants for the flight legs scheduled to be flown by a plurality of compatible aircraft; and

determining a maximum value path through the network for each of the plurality of compatible aircraft.

15. A method according to claim 14 wherein constructing the network comprises constructing the network such that each arc entering a node represents a leg replicant that has an availability time prior to a departure time of each arc departing the node.

16. A method according to claim 14 further comprising ordering the aircraft and thereafter determining the maximum value path through the network for each aircraft in order.

17. A method according to claim 14 wherein determining the maximum value path through the network comprises eliminating any arcs representative of a leg replicant that requires more of a system resource than is available.

18. A method according to claim 14 wherein determining the maximum value path through the network comprises eliminating any arcs representative of a leg replicant of a flight leg having another leg replicant that has already been included in the maximum value path constructed for another aircraft.

19. A system of determining an alternative schedule comprising:

a processing element for identifying a plurality of leg replicants for at least some legs of a plurality of itineraries, and for evaluating different combinations of the leg replicants for the respective legs of the plurality of itineraries in order to construct schedules for the plurality of itineraries, wherein said processing element initially relaxes at least some capacity constraints while evaluating different combinations of the leg replicants.

20. A system according to claim 19 wherein said processing element utilizes Lagrangian relaxation to initially relax at least some of the capacity constraints and to subsequently reevaluate at least some of the different combinations while subject to the capacity constraints.

21. A system according to claim 20 wherein said processing element also assigns a value to each leg replicant.

22. A system according to claim 21 wherein said processing element assigns the value based upon at least one of distance of the respective leg, seating capacity and an objective function relating value to arrival delay.

23. A system according to claim 21 wherein said processing element evaluates different combinations of the leg replicants by identifying the schedules for the plurality of itineraries that are comprised of combinations of the leg replicants that have the largest collective value.

24. A system according to claim 23 wherein said processing element separately determines the schedule for each itinerary that is comprised of leg replicants having the largest collective value while at least some of the capacity constraints are relaxed.

25. A system according to claim 24 wherein said processing element evaluates different combinations by ordering the schedules that were determined while the capacity constraints are relaxed based upon the collective value of the leg replicants comprising the respective schedules, and then sequentially reevaluating each schedule in order while taking into account the capacity constraints.

26. A system of swapping legs between itineraries comprising:

a processing element for identifying swap opportunities to swap legs between respective pairs of itineraries, estimating a benefit of each swap opportunity, and evaluating, for each swap opportunity that is determined to be beneficial, different combinations of leg replicants for the legs that have been swapped between the respective pair of itineraries in order to construct schedules for the respective pair of itineraries.

27. A system according to claim 26 wherein said processing element identifies a swap opportunity between a respective pair of itineraries with each itinerary having a first scheduled flight leg and a subsequent scheduled flight leg, and the pair of itineraries being such that:

(i) the subsequent scheduled flight leg of one itinerary has a propagated delay, (ii) the first scheduled flight legs of both itineraries have a common destination airport, and (iii) a difference between scheduled departure times of the subsequent scheduled flight legs of the pair of itineraries is no greater than a predefined time.

28. A system according to claim 26 wherein said processing element estimates the benefit of each swap opportunity by determining a value of each itinerary to be a sum of a value of each leg included in the itinerary, and wherein said processing element also determines that a swap opportunity is beneficial if the collective value of the pair of itineraries associated with the swap opportunity exceeds the collective value of the itineraries prior to any swap of legs therebetween.

29. A system according to claim 26 wherein said processing element determines a value for each itinerary to be a sum of a value of each leg included in the itinerary following evaluation of different combinations of leg replicants, and accepts the schedules constructed for the pair of itineraries if the collective value of the pair of itineraries exceeds the collective value of the itineraries prior to any swap of legs therebetween.

30. A system of determining an alternative schedule comprising:

a processing element for constructing a network for each pool of equipment with each node of the network representing an airport at a predefined period of time and each arc representing a leg replicant for a respective flight leg, wherein each pool of equipment comprises leg replicants for the flight legs scheduled to be flown by a plurality of compatible aircraft; and

wherein said processing element is also capable of determining a maximum value path through the network for each of the plurality of compatible aircraft.

31. A system according to claim 30 wherein said processing element orders the aircraft and thereafter determines the maximum value path through the network for each aircraft in order.

32. A system according to claim 30 wherein said processing element determines the maximum value path through the network by eliminating any arcs representative of a leg replicant that requires more of a system resource than is available.

33. A system according to claim 30 wherein said processing element determines the maximum value path through the network by eliminating any arcs representative of a leg replicant of a flight leg having another leg replicant that has already been included in the maximum value path constructed for another aircraft.

34. A computer program product for determining an alternative schedule, the computer program product comprising a computer-readable storage medium having computer-readable program code embodied in said medium, the computer-readable program code comprising:

a first executable portion adapted to identify a plurality of leg replicants for at least some legs of a plurality of itineraries; and

a second executable portion adapted to evaluate different combinations of the leg replicants for the respective legs of the plurality of itineraries in order to construct schedules for the plurality of itineraries, wherein said second executable portion is adapted to evaluate different combinations of the leg replicants by initially relaxing at least some capacity constraints.

35. A computer program product according to claim 34 wherein said second executable portion is adapted to evaluate different combinations of the leg replicants by utilizing Lagrangian relaxation to initially relax at least some of the capacity constraints and then subsequently reevaluating at least some of the different combinations while subject to the capacity constraints.

36. A computer program product according to claim 35 further comprising a third executable portion adapted to assign a value to each leg replicant.

37. A computer program product according to claim 36 wherein said third executable portion is adapted to assign the value by assigning the value based upon at least one of distance of the respective leg, seating capacity and an objective function relating value to arrival delay.

38. A computer program product according to claim 36 wherein said second executable portion is adapted to evaluate different combinations of the leg replicants by identifying the schedules for the plurality of itineraries that are comprised of combinations of the leg replicants that have the largest collective value.

39. A computer program product according to claim 38 wherein said second executable portion is adapted to identify the schedules by separately determining the schedule for each itinerary that is comprised of leg replicants having the largest collective value while at least some of the capacity constraints are relaxed.

40. A computer program product according to claim 39 wherein said second executable portion is adapted to evaluate different combinations by ordering the schedules that were determined while the capacity constraints are relaxed based upon the collective value of the leg replicants comprising the respective schedules and by sequentially reevaluating each schedule in order while taking into account the capacity constraints.

41. A computer program product for swapping legs between itineraries, the computer program product comprising a computer-readable storage medium having computer-readable program code embodied in said medium, the computer-readable program code comprising:

a first executable portion adapted to identify swap opportunities to swap legs between respective pairs of itineraries;

a second executable portion adapted to estimate a benefit of each swap opportunity; and

a third executable portion adapted to evaluate, for each swap opportunity that is determined to be beneficial, different combinations of leg replicants for the legs that have been swapped between the respective pair of itineraries in order to construct schedules for the respective pair of itineraries.

42. A computer program product according to claim 41 wherein said first executable portion is adapted to identify swap opportunities by identifying a swap opportunity between a respective pair of itineraries with each itinerary having a first scheduled flight leg and a subsequent scheduled flight leg and with the respective pair of itineraries being such that:

(i) the subsequent scheduled flight leg of one itinerary has a propagated delay, (ii) the first scheduled flight legs of both itineraries have a common destination airport, and (iii) a difference between scheduled departure times of the subsequent scheduled flight legs of the pair of itineraries is no greater than a predefined time.

43. A computer program product according to claim 41 said second executable portion is adapted to estimate the benefit of each swap opportunity by determining a value of each itinerary to be a sum of a value of each leg included in the itinerary, and wherein the computer program product further comprises a fourth executable portion adapted to determine that a swap opportunity is beneficial if the collective value of the pair of itineraries associated with the swap opportunity exceeds the collective value of the itineraries prior to any swap of legs therebetween.

44. A computer program product according to claim 41 further comprising:

a fourth executable portion adapted to determine a value for each itinerary to be a sum of a value of each leg included in the itinerary following evaluation of different combinations of leg replicants; and

a fifth executable portion adapted to accept the schedules constructed for the pair of itineraries if the collective value of the pair of itineraries exceeds the collective value of the itineraries prior to any swap of legs therebetween.

45. A computer program product for determining an alternative schedule, the computer program product comprising a computer-readable storage medium having computer-readable program code embodied in said medium, the computer-readable program code comprising:

a first executable portion adapted to construct a network for each pool of equipment with each node of the network representing an airport at a predefined period of time and each arc representing a leg replicant for a respective flight leg, wherein each pool of equipment comprises leg replicants for the flight legs scheduled to be flown by a plurality of compatible aircraft; and

a second executable portion adapted to determine a maximum value path through the network for each of the plurality of compatible aircraft.

46. A computer program product according to claim 45 further comprising a third executable portion adapted to order the aircraft such that said second executable portion is adapted to thereafter determine the maximum value path through the network for each aircraft in order.

47. A computer program product according to claim 45 wherein said second executable portion is adapted to determine the maximum value path through the network by eliminating any arcs representative of a leg replicant that requires more of a system resource than is available.

48. A computer program product according to claim 45 wherein said second executable portion is adapted to determine the maximum value path through the network by eliminating any arcs representative of a leg replicant of a flight leg having another leg replicant that has already been included in the maximum value path constructed for another aircraft.