Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling

Jean-François Cordeau, Goran Stojković, François Soumis and Jacques Desrosiers
Additional contact information
Jean-François Cordeau: École des Hautes Études Commerciales and GERAD, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7
Goran Stojković: École Polytechnique and GERAD, C.P. 6079, Succ. Centre-Ville, Montréal, Canada H3C 3A7
François Soumis: École Polytechnique and GERAD, C.P. 6079, Succ. Centre-Ville, Montréal, Canada H3C 3A7
Jacques Desrosiers: École des Hautes Études Commerciales and GERAD, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7

Transportation Science, 2001, vol. 35, issue 4, 375-388

Abstract: Given a set of flight legs to be flown by a single type of aircraft, the simultaneous aircraft routing and crew scheduling problem consists of determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and side constraints are satisfied. While some side constraints such as maximum flight time and maintenance requirements involve only crews or aircraft, linking constraints impose minimum connection times for crews that depend on aircraft connections. To handle these linking constraints, a solution approach based on Benders decomposition is proposed. The solution process iterates between a master problem that solves the aircraft routing problem, and a subproblem that solves the crew pairing problem. Because of their particular structure, both of these problems are solved by column generation. A heuristic branch-and-bound method is used to compute integer solutions. On a set of test instances based on data provided by an airline, the integrated approach produced significant cost savings in comparison with the sequential planning process commonly used in practice. The largest instance solved contains more than 500 flight legs over a 3-day period.

Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (99)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.35.4.375.10432 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:35:y:2001:i:4:p:375-388

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().