• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
1988
Journal name
European Journal of Operational Research
Volume
35
Number
1
Publisher
Elsevier
Pages
45-58
Publication identifier
http://dx.doi.org/10.1016/0377-2217(88)90377-3
Metadata
Show full item record
Author(s)
Lavoie, Sylvie
Minoux, Michel
Odier, Edouard
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 / Keywords
Combinatorial optimization; generalized linear programming; scheduling; air transportation

Related items

Showing items related by title and author.

  • Thumbnail
    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é
  • Thumbnail
    An optimal transport approach for seismic tomography: application to 3D full waveform inversion 
    Métivier, Ludovic; Brossier, Romain; Mérigot, Quentin; Oudet, Edouard; Virieux, Jean (2016) Article accepté pour publication ou publié
  • Thumbnail
    A new ϕ -FEM approach for problems with natural boundary conditions 
    Duprez, Michel; Lleras, Vanessa; Lozinski, Alexei (2020) Document de travail / Working paper
  • Thumbnail
    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é
  • Thumbnail
    Minimisation methods for quasi-linear problems, with an application to periodic water waves 
    Buffoni, Boris; Séré, Eric; Toland, John (2005) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo