A new approach for crew pairing problems by column generation with an application to air transportation
Lavoie, Sylvie; Minoux, Michel; Odier, Edouard (1988), A new approach for crew pairing problems by column generation with an application to air transportation, European Journal of Operational Research, 35, 1, p. 45-58. http://dx.doi.org/10.1016/0377-2217(88)90377-3
Type
Article accepté pour publication ou publiéDate
1988Journal name
European Journal of Operational ResearchVolume
35Number
1Publisher
Elsevier
Pages
45-58
Publication identifier
Metadata
Show full item recordAbstract (EN)
We propose a new approach to crew-pairing problems arising in the context of airline companies. The problem is first formulated as a large scale set covering problem with many colums, each column representing a valid crew-pairing. We then suggest a solution procedure for the continuous relaxation of this large scale problem, based on generalized linear programming, in which the column generation subproblem is shown to be equivalent to a shortest path problem in an associated graph. Computational results obtained on a series of real problems (involving up to 329 flight segments) are reported, confirming both computational efficiency and practical applicability of the new approach. Indeed not only were the resulting solutions observed to be integral for most test problems, but average savings of about 4 to 5% over the best available hand-built solutions were shown to be obtained.Subjects / Keywords
Combinatorial optimization; generalized linear programming; scheduling; air transportationRelated items
Showing items related by title and author.
-
Ribeiro, Celso Carneiro; Minoux, Michel; Penna, Manoel Camillo (1989) Article accepté pour publication ou publié
-
Métivier, Ludovic; Brossier, Romain; Mérigot, Quentin; Oudet, Edouard; Virieux, Jean (2016) Article accepté pour publication ou publié
-
Duprez, Michel; Lleras, Vanessa; Lozinski, Alexei (2020) Document de travail / Working paper
-
Métivier, Ludovic; Brossier, Romain; Mérigot, Quentin; Oudet, Edouard; Virieux, Jean (2016) Article accepté pour publication ou publié
-
Buffoni, Boris; Séré, Eric; Toland, John (2005) Article accepté pour publication ou publié