Daily Aircraft Routing and Scheduling

Guy Desaulniers, Jacques Desrosiers, Yvan Dumas, Marius M. Solomon and François Soumis
Additional contact information
Guy Desaulniers: GERAD and École Polytechnique de Montréal, Montréal, Québec, Canada H3C 3A7
Jacques Desrosiers: GERAD and École des Hautes Études Commerciales, Montréal, Québec, Canada H3T 2A7
Yvan Dumas: Ad Opt Technologies, Montréal, Québec, Canada H3V 1G4
Marius M. Solomon: Northeastern University and GERAD, Boston, Massachusetts 02115
François Soumis: GERAD and École Polytechnique de Montréal, Montréal, Québec, Canada H3C 3A7

Management Science, 1997, vol. 43, issue 6, 841-855

Abstract: In this paper we consider the daily aircraft routing and scheduling problem (DARSP). It consists of determining daily schedules which maximize the anticipated profits derived from the aircraft of a heterogeneous fleet. This fleet must cover a set of operational flight legs with known departure time windows, durations and profits according to the aircraft type. We present two models for this problem: a Set Partitioning type formulation and a time constrained multicommodity network flow formulation. We describe the network structure of the subproblem when a column generation technique is applied to solve the linear relaxation of the first model and when a Dantzig-Wolfe decomposition approach is used to solve the linear relaxation of the second model. The linear relaxation of the first model provides upper bounds. Integer solutions to the overall problem are derived through branch-and-bound. By exploiting the equivalence between the two formulations, we propose various optimal branching strategies compatible with the column generation technique. Finally we report computational results obtained on data provided by two different airlines. These results show that significant profit improvement can be generated by solving the DARSP using our approach and that this can be obtained in a reasonable amount of CPU time.

Keywords: air transportation; routing; scheduling; column generation; Dantzig-Wolfe decomposition; multi-commodity network (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (55)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.43.6.841 (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:ormnsc:v:43:y:1997:i:6:p:841-855

Access Statistics for this article

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