This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Cappanera, P. Articles by Gallo, G. Search for Related Content

A Multicommodity Flow Approach to the Crew Rostering Problem

Dipartimento di Informatica, Università di Pisa, Via F. Buonarroti 2, 56127 Pisa, Italy
Dipartimento di Informatica, Università di Pisa, Via F. Buonarroti 2, 56127 Pisa, Italy
cappaner{at}di.unipi.it
gallo{at}di.unipi.it

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.

Subject classifications: transportation; scheduling; personnel; crew rostering; programming; integer; cutting plane/facet; valid inequalities.
History: Received October 2001; revision received January 2003; revision received March 2003; accepted May 2003.

This article has been cited by other articles:

				S. E. Sampson OR PRACTICE--Optimization of Vacation Timeshare Scheduling Operations Research, September 1, 2008; 56(5): 1079 - 1088. [Abstract] [PDF]