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 recomputed, 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.

D'Ariano, A., Pacciarelli, D., Pranzo, M. (2007). A branch and bound algorithm for scheduling trains in a railway network. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 183, 643-657 [10.1016/j.ejor.2006.10.034].

A branch and bound algorithm for scheduling trains in a railway network

D'ARIANO, Andrea;PACCIARELLI, Dario;
2007-01-01

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 recomputed, 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.
2007
D'Ariano, A., Pacciarelli, D., Pranzo, M. (2007). A branch and bound algorithm for scheduling trains in a railway network. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 183, 643-657 [10.1016/j.ejor.2006.10.034].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/146292
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 444
  • ???jsp.display-item.citation.isi??? 23
social impact