Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search

Meinolf Sellmann (), Kyriakos Zervoudakis (), Panagiotis Stamatopoulos () and Torsten Fahle ()

Annals of Operations Research, 2002, vol. 115, issue 1, 207-225

Abstract: The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and column generation alone. Copyright Kluwer Academic Publishers 2002

Keywords: airline crew assignment; hybrid OR–CP method; constraint programming based column generation; set partitioning (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1021105422248 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:115:y:2002:i:1:p:207-225:10.1023/a:1021105422248

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1021105422248

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().