Single Step Flight Schedule Optimization

• US 20100082383A1
• Filed: 10/01/2008
• Published: 04/01/2010
• 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 GmbH (Accenture PLC)
• Inventors: Smith, Stuart H., Pachon, Julian
• Granted Patent: US 8,645,177 B2
• Time in Patent Office: Days
• US Class Current: 705/7
• 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-generated method for generating aircraft routings comprising:

generating a first graph comprising possible flight segments between airline stations for an airline;

determining a set of permissible crew pairings based on a traversal of the first graph, 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;

generating a second graph comprising the determined set of permissible crew pairings;

determining a set of permissible aircraft routings based on a traversal of the second graph, 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; 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 and adding the segment to a permissible crew pairing if the first constraints are not violated.

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 and adding the segment to a permissible aircraft routing if the second constraints are not violated.

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 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;

determining a set of permissible crew pairings based on a processing of the first data structure, 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;

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

determining a set of permissible aircraft routings based on a processing of the second data structure, 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; 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 set of permissible crew pairings based on a traversal of a first graph comprising possible flight segments between airline stations for an airline, 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;

an aircraft routing module to determine a set of permissible aircraft routings based on a traversal of a second graph comprising the determined 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

an 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.