Models and algorithms for rail transportation problems

The rail transportation industry is very rich in terms of problems that can be modeled and solved using mathematical optimization. Some recent contributions dealing with Train Timetabling, and with Railway Crew  Management, will be described. These problems account for a large portion of the planning performed by most  railways.    Given a set of schedules, the Train Timetabling Problem (also called the train dispatching problem) determines a feasible plan of meets and overtakes that satisfies a system of constraints on the operation of trains. A popular  objective for this problem is to minimize deviations from the planned arrival and departure times. Heuristic algortihms, based on Lagrangian relaxation and particularly suited for the solution of large size instances, are described. Extensive computational results on real-world instances provided by Rete Ferroviaria Italiana, the Italian railway infrastructure company, are reported.   In the Crew Management Problem, one is given a set of depots, where the available crews are located, and a planned timetable for the train services to be performed every day of a certain time period. Each crew can perform a roster, defined as a cyclic sequence of services whose operational cost and feasibility depend on several rules laid down by union contracts and company regulations. The Crew Management Problem consists of finding a set of rosters for the crews, covering once every trip, so as to satisfy all the operational constraints at minimum cost. Heuristic algorithms, based on a Set Covering formulation and a graph theoretical model, are presented. Extensive computational results on real-world instances provided by Trenitalia, the Italian train operator company, are given.

Paolo Toth is professor of Combinatorial Optimization at the Faculty of Engineering of the University of Bologna. His main research interests are the design and implementation of effective exact and approximate algorithms for optimization problems (TSP, VRP, Knapsack, Crew Management, Train Timetabling, Packing, ...). He is author of over 110 papers published in international journals, co-author of the book "Knapsack Problems: Algorithms and Computer Implementations" (J. Wiley, 1990), and co-Editor of the books "Combinatorial Optimization" ( J. Wiley, 1979), "FORTRAN Codes for Network Optimization" (Annals of OR, 1988), "Advanced Methods in Transportation Analysis" (Springer, 1996) and "The Vehicle Routing Problem" (SIAM Monographs, 2002). He is Associate Editor of "Transportation Science", "Networks", "Journal of Heuristics", "European Journal of OR", "ITOR", "Discrete Applied Mathematics", "Journal of the Operational Research Society". He has also worked with AGIP, FS (the Italian Railway Company), Haworth and several Mass Transit Companies on real-world projects. From 1995 to 1996 he was President of EURO (Association of the European OR Societies). He is President of IFORS (International Federation of the OR Societies) for the years 2001-2003. In the year 1998, he was conferred the Harold Larnder Memorial Award (annual Award of the Canadian OR Society), and the EURO Gold Medal (the highest European OR award). In May 2003, the University of Montreal conferred him a Doctorate "honoris causa" in Operational Research.