A Multicommodity Flow Approach to the Crew Rostering Problem

Paola Cappanera () and Giorgio Gallo ()
Additional contact information
Paola Cappanera: Dipartimento di Informatica, Università di Pisa, Via F. Buonarroti 2, 56127 Pisa, Italy
Giorgio Gallo: Dipartimento di Informatica, Università di Pisa, Via F. Buonarroti 2, 56127 Pisa, Italy

Operations Research, 2004, vol. 52, issue 4, 583-596

Abstract: The problem of finding a work assignment for airline crew members in a given time horizon is addressed. In the literature this problem is usually referred to as the airline crew rostering problem . It consists of constructing monthly schedules for crew members by assigning them pairings, rest periods, annual and sick leave, training periods, union activities, and so forth, so as to satisfy the collective agreements and security rules. We formulate the airline crew rostering problem as a 0--1 multicommodity flow problem where each employee corresponds to a commodity; determining a monthly schedule for an employee is the same as computing a path on a suitably defined graph while still satisfying union conventions. A preprocessing phase is performed that reduces the dimension of the graph. To tighten the linear programming formulation of our model, we propose some families of valid inequalities that have proved to be computationally effective. Some of them can be treated implicitly when constructing the graph. Computational results obtained with a commercial integer programming solver (CPLEX) are analyzed.

Keywords: transportation; scheduling; personnel; crew rostering; programming; integer; cutting plane/facet; valid inequalities (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0110 (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:oropre:v:52:y:2004:i:4:p:583-596

Access Statistics for this article

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