System, method and computer program product for schedule recovery
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
48 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25)
-
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. - View Dependent Claims (27, 28, 29)
-
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.- View Dependent Claims (31, 32, 33)
-
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. - View Dependent Claims (35, 36, 37, 38, 39, 40)
-
-
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. - View Dependent Claims (42, 43, 44)
-
-
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. - View Dependent Claims (46, 47, 48)
-
Specification