## Selected Topics in Large Scale Discrete Optimization

## MODELS AND ALGORITHMS FOR RAILWAY CREW MANAGEMENT

### DEIS, University of Bologna, Italy

### Friday, October 30, 1998

### 1:00 PM - 3:30 PM

### DIMACS Center, CoRE Building, Room 431, Rutgers University

*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.