Crew Management is concerned with building the work schedules (rosters) of crews needed to cover a given set of timetabled trips. We give a general definition of the problem, and show possible operational constraints and objective functions arising in real-world applications.

In practice, the overall problem is decomposed into two subproblems, called Crew Scheduling (CSP) and Crew Rostering (CRP). In CSP the short-term schedule of the crews is considered, and a convenient set of duties covering all the trips is constructed. In CRP the selected duties are sequenced to obtain the final rosters. Several mathematical programming and graph-theory formulations, and different exact and heuristic algorithms proposed in the literature for the solution of the two subproblems are presented. Advantages and disadvantages of the proposed formulations and algorithms are discussed.

Two main solution approaches are illustrated in more details. CSP is solved by generating a very large number of potential duties, and by solving an associated Set Covering Problem to select a minimum-cost set of duties covering all the trips. CRP is solved by using a Lagrangian relaxation of a graph-theoretical formulation of the problem. Extensive computational results on real-world instances arising in the Italian railway company, Ferrovie dello Stato SpA, are presented.

Return to the LSDO tutorial topics page