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.
Scheda prodotto non validato
Scheda prodotto in fase di analisi da parte dello staff di validazione
|Titolo:||A branch and bound algorithm for scheduling trains in a rail network|
|Rivista:||EUROPEAN JOURNAL OF OPERATIONAL RESEARCH|
|Citazione:||D'Ariano, A., Pacciarelli, D., & Pranzo, M. (2007). A branch and bound algorithm for scheduling trains in a rail network. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 183(2), 643-657.|
|Appare nelle tipologie:||1.1 Articolo in rivista|
File in questo prodotto: