Modeling and solving the crew rostering problem

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.