Train Driver Rostering at SBB Cargo

Problem Statement

SBB Cargo is the freight division of the Swiss Federal Railways (SBB). Spread over Switzerland, SBB Cargo has 10 regional train driver depots. The regional train driver depots provide train drivers and engines, are responsible for crew rostering, and participate in crew scheduling. The sizes of train driver depots range from small ones like Goldau (7 train drivers) and Chiasso (21 train drivers) up to big ones like Basel (122 train drivers), Erstfeld (128 train drivers), and Limmattal (164 train drivers).

The task of this diploma thesis was to find a mathematical formulation of the train driver rostering problem at SBB Cargo including the many legal restrictions and preferences of train drivers. Further, the goal was to implement the resulting mathematical optimization model in a suitable computing environment and investigate its capability to create cyclic rosters on a test scenario. The envisaged benefits from the availability of such a model are

1. speedup in roster generation, therefore,
2. increased variety of rosters for the train drivers to choose from,
3. possibility to check the influence of new groups or work time models on rosters of other groups, and,
4. decision support for depot planners at SBB Cargo by automatically generating the duties of a depot.

Summary and Results

The idea to solve the train driver rostering problem was to use a multi-commodity network flow model to describe the possible sequences of duties and days-off for cyclic rosters. The multi-commodity approach is used to control the week to week transitions in the cyclic roster, and to avoid shorter cycles than the group size. This results in a mixed integer program (MIP) which should be solved by an available state-of-the-art MIP solver using a branch and bound strategy.

In a first step this model was used to calculate rosters for a single group of train drivers. In a second step the model was extended to assign duties to different groups of train drivers and to generate the rosters of the groups in one step. In both cases the problem size of the resulting MIP was reduced by combining similar duties into one condensed duty in order to reduce the computation time to find a solution of the MIP. Furthermore, the task of uncondensing gives the roster designer some degree of freedom to realize unmodeled personal preferences.