Single step flight schedule optimization

• US 8,645,177 B2
• Filed: 10/01/2008
• Issued: 02/04/2014
• Est. Priority Date: 10/01/2008
• Status: Active Grant

• Current Assignee: GE Aviation Systems Taleris Ltd. (GE Aerospace), GE Flight Efficiency Services, Inc.
• Original Assignee: Accenture Global Services Limited (Accenture PLC)
• Inventors: Pachon, Julian, Smith, Stuart H.
• Primary Examiner(s): Jeanty, Romain
• Assistant Examiner(s): Gills, Kurtis
• Application Number:
  US12/243,490
• Publication Number:
  US 20100082383A1
• Time in Patent Office: 1,952 Days
• Field of Search: 705/7.12
• US Class Current: 705/7.12
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G08G 5/00 Traffic control systems for aircraft , e.g. air-traffic control [ATC]

Abstract

The subject matter of this specification can be embodied in, among other things, a method that includes generating a first graph including possible flight segments between airline stations for an airline and determining a set of permissible crew pairings based on a traversal of the first graph. The method also includes generating a second graph comprising the determined set of permissible crew pairings and determining a set of permissible aircraft routings based on a traversal of the second graph. The method includes generating a set of optimized aircraft routings using an integer-programming algorithm that accepts the determined set of permissible aircraft routings as input, and outputting the set of optimized aircraft routings for use in a flight schedule.

Claims

1. A computer-implemented method for generating aircraft routings comprising:

generating, using one or more processors, a first graph comprising possible flight segments between airline stations for an airline, the possible flight segments comprising all possible crew connections at a first airline station from an incoming flight to an outgoing flight and being based on crew scheduling constraints associated with the first airline station;

determining, using the one or more processors, a first set of permissible crew pairings based on a first traversal of the first graph, the first traversal being based on at least a minimum crew connection time, wherein a permissible crew pairing comprises a sequence of one or more flight segments that a crew is permitted to travel subject to specified first constraints;

determining, using the one or more processors, a second set of permissible crew pairings based in part on the first set of permissible crew pairings and the crew scheduling constraints associated with a second airline station, at which at least one permissible crew pairing of the first set of permissible crew pairings is to arrive;

generating, using the one or more processors, a second graph comprising the second set of permissible crew pairings;

determining, using the one or more processors, a set of permissible aircraft routings based on a second traversal of the second graph, the second traversal being based on at least one of the permissible crew pairings, such that permissible aircraft routings in the set of permissible aircraft routings each account for the second set of permissible crew pairings, wherein a permissible aircraft routing comprises a series of one or more flight segments for an aircraft to fly subject to specified second constraints;

generating a set of optimized aircraft routings using an integer programming algorithm that is executed using the one or more processors and that accepts the determined set of permissible aircraft routings as input, such that each optimized aircraft routing is already associated with permissible crew pairings; and

outputting the set of optimized aircraft routings for use in a flight schedule.

2. The method of claim 1, wherein nodes of the first graph comprise representations of the airline stations and edges of the first graph comprise representations of the flight segments between the airline stations.

3. The method of claim 1, wherein nodes of the second graph comprise representations of the airline stations and edges of the second graph comprise representations of crew that are permitted to travel on flight segments between the airline stations subject to the first constraints.

4. The method of claim 1, wherein the determined set of permissible crew pairings are linked in the second graph based on whether an arrival time for crew pairings associated with incoming flights at an airline station are within a specified minimum time of a departure time for crew pairings associated with outgoing flights.

5. The method of claim 1, wherein the set of optimized aircraft routings is optimized based on one or more optimization variables included in the linear programming algorithm.

6. The method of claim 5, wherein the optimization variables for which the set of optimized aircraft routings are optimized comprise cost of operations associated with aircraft routings, profit associated with the aircraft routings, or aircraft or crew use.

7. The method of claim 1, wherein the specified first constraints for the permissible crew pairings comprise regulatory, contractual, or operational constraints.

8. The method of claim 7, wherein the regulatory, contractual, or operational constraints comprise requiring that crew pairings start and end at the same airline station, maximum or minimum flying time for the crew, maximum or minimum on duty time for the crew, maximum number of landings for the crew, or maximum or minimum time between consecutive flights for the crew.

9. The method of claim 1, wherein the specified second constraints for the permissible aircraft routings comprising regulatory or operational constraints.

10. The method of claim 9, wherein the regulator or operational constraints comprise that a routing be divisible by integer n crew pairings, start and end at the same airline station, maximum or minimum flying time for the aircraft, maximum or minimum time away from a base airline station, maximum number of landings for the aircraft, or maximum or minimum time between consecutive flights for the aircraft.

11. The method of claim 1, wherein determining a set of permissible aircraft routings comprises requiring that an aircraft routing is divisible into integer n crew pairings, wherein each crew pairing starts and ends at the same airline station.

12. The method of claim 1, wherein the traversals of the first and second graphs comprise depth first searches.

13. The method of claim 1, wherein determining the set of permissible crew pairings based on the traversal comprises:

checking the first constraints for the crew after each flight segment;

determining that the first constraints are not violated; and

adding the segment to a permissible crew pairing.

14. The method of claim 1, wherein determining the set of permissible crew pairings based on the traversal comprises requiring that a permissible crew pairing start and end at the same airline station.

15. The method of claim 14, wherein the same airline station comprises a base station that is an airline hub for an airline associated with the crew.

16. The method of claim 14, wherein determining the set of permissible crew pairings based on the traversal further comprises requiring that the start and end at the same airline station occur during a 24-hour period.

17. The method of claim 1, wherein determining the set of permissible aircraft routings based on the traversal comprises:

checking the second constraints for the aircraft after each flight segment;

determining that the second constraints are not violated; and

adding the segment to a permissible aircraft routing.

18. The method of claim 1, wherein the integer programming algorithm comprises a column generation function.

19. The method of claim 1, wherein the first and second graphs comprise space/time graphs.

20. A computer program product tangibly embodied in a non-transitory computer-readable storage device, the computer program product including instructions that, when executed, perform operations for scheduling aircraft routings, the operations comprising:

generating a first data structure storing possible flight segments between airline stations for an airline, the possible flight segments comprising all possible crew connections at a first airline station from an incoming flight to an outgoing flight and being based on crew scheduling constraints associated with the first airline station;

determining a first set of permissible crew pairings based on a processing of the first data structure, the processing of the first data structure being based on at least a minimum crew connection time, wherein a permissible crew pairing comprises a sequence of one or more flight segments that a crew is permitted to travel subject to specified first constraints;

determining a second set of permissible crew pairings based in part on the first set of permissible crew pairings and the crew scheduling constraints in view of a second airline station, at which at least one permissible crew pairing of the first set of permissible crew pairings is to arrive;

generating a second data structure storing the second set of permissible crew pairings;

determining a set of permissible aircraft routings based on a processing of the second data structure, the processing of the second data structure being based on at least one of the permissible crew pairings, such that permissible aircraft routines in the set of permissible aircraft routings each account for the second set of permissible crew pairings, wherein a permissible aircraft routing comprises a series of one or more flight segments for an aircraft to fly subject to specified second constraints;

generating a set of optimized aircraft routings using an integer programming algorithm that accepts the determined set of permissible aircraft routings as input, such that each optimized aircraft routing is already associated with permissible crew pairings; and

outputting the set of optimized aircraft routings for use in a flight schedule.

21. A system for generating airline routings comprising:

one or more computers having

a crew pairing generation module to;

determine a first set of permissible crew pairings based on a first traversal of a first graph comprising possible flight segments between airline stations for an airline, the possible flight segments comprising all possible crew connections at a first airline station from an incoming flight to an outgoing flight and being based on crew scheduling constraints associated with the first airline station, the first traversal being based on at least a minimum crew connection time, wherein a permissible crew pairing comprises a sequence of one or more flight segments that a crew is permitted to travel subject to specified first constraints, and

determining a second set of permissible crew pairings based in part on the first set of permissible crew pairings and the crew scheduling constraints in view of a second airline station, at which at least one permissible crew pairing of the first set of permissible crew pairings is to arrive;

an aircraft routing module to;

generate a second graph including the determined second set of permissible crew pairings, and

determine a set of permissible aircraft routings based on a second traversal of a second graph comprising the determined set of permissible crew pairings, the second traversal being based on at least one of the permissible crew pairings, such that permissible aircraft routings in the set of permissible aircraft routings each account for the second set of permissible crew pairings, wherein a permissible aircraft routing comprises a series of one or more flight segments for an aircraft to fly subject to specified second constraints; and

a column generation module to receive the determined set of permissible aircraft routings as input and output a set of optimized aircraft routings based on specified optimization constraints, such that each optimized aircraft routing is already associated with permissible crew pairings.