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
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (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 / KeywordsCombinatorial optimization; generalized linear programming; scheduling; air transportation
Showing items related by title and author.
An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment 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é
Measuring the misfit between seismograms using an optimal transport distance: application to full waveform inversion Métivier, Ludovic; Brossier, Romain; Mérigot, Quentin; Oudet, Edouard; Virieux, Jean (2016) Article accepté pour publication ou publié
Game theoretic centrality: a novel approach to prioritize disease candidate genes by combining biological networks with the Shapley value Sun, Min Woo; Moretti, Stefano; Paskov, Kelley; Stockham, Nate; Varma, Maya; Chrisman, Brianna; Washington, Peter Y.; Jung, Jae-Yoon; Wall, Dennis P. (2020) Article accepté pour publication ou publié