A branch and bound algorithm for scheduling trains in a railway network |
| |
Authors: | Andrea D&rsquo Ariano,Dario Pacciarelli,Marco Pranzo |
| |
Affiliation: | 1. Department of Transport and Planning, Delft University of Technology, P.O. Box 5048, 2600 GA Delft, The Netherlands;2. Dipartimento di Informatica e Automazione, Università degli Studi Roma Tre, via della vasca navale, 79 – 00146 Roma, Italy;3. Dipartimento di Ingegneria dell’Informazione, Università di Siena, via Roma, 56 – 53100 Siena, Italy |
| |
Abstract: | The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits. |
| |
Keywords: | Train scheduling Real-time conflict resolution Alternative graph Branch and bound algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|