Integer Programming Techniques for Train Dispatching in Mass Transit and Main Line

Abstract

Trains moving in railway systems are often affected by delays or cancellations. This in turn may produce knock-on effects and propagate to other trains and other regions of the network. These undesired effects may be alleviated by suitably rerouting and rescheduling trains in real time. Train dispatching is thus a central task in managing railway systems because it allows recovery from undesirable deviations from the timetable and a better exploitation of railway resources. With few exceptions, dispatching is still almost entirely in the hands of human operators, despite the fact that it is a large and complex optimization problem that does not lend itself to manual solution. In this chapter, we describe how integer programming (IP) can be exploited to quickly find optimal solutions to large dispatching problems and describe real-life implementations of these ideas.