Modeling and Solving the Crew Rostering Problem

Alberto Caprara, Paolo Toth, Daniele Vigo and Matteo Fischetti
Additional contact information
Alberto Caprara: University of Bologna, Bologna, Italy
Paolo Toth: University of Bologna, Bologna, Italy
Daniele Vigo: University of Bologna, Bologna, Italy
Matteo Fischetti: University of Udine, Udine, Italy

Operations Research, 1998, vol. 46, issue 6, 820-830

Abstract: The Crew Rostering Problem (CRP) aims at determining an optimal sequencing of a given set of duties into rosters satisfying operational constraints deriving from union contract and company regulations. Previous work on CRP addresses mainly urban mass-transit systems, in which the minimum number of crews to perform the duties can easily be determined, and the objective is to evenly distribute the workload among the crews. In typical railway applications, however, the roster construction has to take into account more involved sequencing rules, and the main objective is the minimization of the number of crews needed to perform the duties. In this paper we propose a basic model for CRP, and describe a Lagrangian lower bound based on the solution of an assignment problem on a suitably defined graph. The information obtained through the lower bound computation is used to drive an effective algorithm for finding a tight approximate solution to the problem. Computational results for real-world instances from railway applications involving up to 1,000 duties are presented, showing that the proposed approach yields, within short computing time, lower and upper bound values that are typically very close. The code based on the approach we propose won the FARO competition organized by the Italian railway company, Ferrovie dello Stato SpA, in 1995.

Keywords: Networks/graphs; matchings; Programming; heuristics; relaxations; applications; Transportation; network models; personnel scheduling; railways (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.6.820 (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:46:y:1998:i:6:p:820-830

Access Statistics for this article

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