Single Step Flight Schedule Optimization
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
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.
Specification