A model predictive control approach for discrete-time rescheduling in complex central railway station areas.

*(English)*Zbl 1251.90005Summary: Railway networks are operated more and more at capacity margins, schedules are becoming more susceptible to disturbances, and delays propagate and hamper the service level experienced by the customers. As a consequence railway traffic management is becoming increasingly challenging, thus motivating the development of computer-aided systems. This paper proposes a dispatching assistant in the form of a model predictive control framework for a complex central railway station area. The closed-loop discrete-time system suggests rescheduling trains according to solutions of a binary linear optimization model. The model assigns precomputed blocking-stairways to trains while respecting resource-based clique constraints, connection constraints, platform related constraints and consistency constraints with the objective of maximizing customer satisfaction. In collaboration with the Swiss Federal Railways (SBB), the approach was successfully applied for an operational day at the central railway station area Berne, Switzerland. The model is capable of considering many alternative routing possibilities and departure timings, a potential of our approach, which can also be deduced from computational results.

##### MSC:

90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |

90B35 | Deterministic scheduling theory in operations research |

##### Keywords:

railway transport; real-time scheduling; dispatching problem; rescheduling; integer programming##### Software:

JGraphT
PDF
BibTeX
XML
Cite

\textit{G. Caimi} et al., Comput. Oper. Res. 39, No. 11, 2578--2593 (2012; Zbl 1251.90005)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Java graph library (JGraphT). \(\langle\)http://jgrapht.sourceforge.net/〉 and 〈http://www.jgrapht.org/javadoc/〉. |

[2] | Adenso-Diaz, B.; Gonzalez, M.O.; Gonzalez-Torre, P., On-line timetable re-scheduling in regional train services, Transportation research part B, 33, 387-398, (1999) |

[3] | Bertsimas, D.; Weismantel, R., Optimization over integers, (2005), Dynamic Ideas |

[4] | Caimi G. Algorithmic decision support for train scheduling in a large railway network. PhD thesis, ETH Zurich; 2009. |

[5] | Caimi, G.C.; Chudak, F.A.; Fuchsberger, M.; Laumanns, M.; Zenklusen, R., A new resource-constrained multicommodity flow model for conflict-free train routing and scheduling, Transportation science, 45, 2, 212-227, (2010) |

[6] | Chou, Y.H.; Weston, P.F.; Roberts, C., Collaborative rescheduling in a distributed railway control system, () |

[7] | Chvátal, V., On certain polytopes associated with graphs, Journal of combinatorial theory (B), 18, 138-154, (1975) · Zbl 0277.05139 |

[8] | Corman F. Real-time Railway Traffic Management: dispatching in complex, large and busy railway networks. PhD thesis, TU Delft; 2010. |

[9] | Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M., Evaluation of Green wave policy in real-time railway traffic management, Transportation research part C: emerging technologies, 17, 6, 607-616, (2009), [Investigates Green wave policy in dutch stations] |

[10] | Corman F, D’Ariano A, Pacciarelli D, Pranzo M. Bi-objective conflict detection and resolution in railway traffic management. Transportation Research Part C: Emerging Technologies, doi:10.1016/j.trc.2010.09.009, in press. |

[11] | Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M., A tabu search algorithm for rerouting trains during rail operations, Transportation research part B: methodological, 44, 1, 175-192, (2010) |

[12] | Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M., Centralized versus distributed systems to reschedule trains in two dispatching areas, Public transport, 2, 219-247, (2010) |

[13] | D’Ariano A. Improving real-time train dispatching: models, algorithms and applications. PhD thesis, TU Delft; 2008. |

[14] | D’Ariano, A.; Corman, F.; Pacciarelli, D.; Pranzo, M., Reordering and local rerouting strategies to manage train traffic in real time, Transportation science, 42, 4, 405-419, (2008) |

[15] | D’Ariano, A.; Pacciarelli, D.; Pranzo, M., A branch and bound algorithm for scheduling trains in a railway network, European journal of operational research, 183, 2, 643-657, (2007) · Zbl 1179.90135 |

[16] | Dessouky, M.M.; Lu, Q.; Zhao, J.; Leachman, R.C., An exact solution procedure to determine the optimal dispatching times for complex rail networks, IIE transactions on operations engineering, 38, 2, 141-152, (2006) |

[17] | Dolder, U.; Krista, M.; Voelcker, M., RCS—rail control system. realtime train run simulation and conflict detection on a netwide scale based on updated train positions, () |

[18] | Eichenberger, P., Kapazitätssteigerung durch ETCS, Signal und draht, 99, 3, 6-14, (2007) |

[19] | Fay, A., A fuzzy knowledge-based system for railway traffic control, Engineering applications of artificial intelligence, 13, 719-729, (2000) |

[20] | Flamini M. Job-Shop scheduling algorithms with applications to railway traffic control. PhD thesis, Università Roma Tre; 2005. |

[21] | Flamini, M.; Pacciarelli, D., Real time management of a metro rail terminus, European journal of operational research, (2007) · Zbl 1146.90029 |

[22] | Geissler H. Frieden in Stuttgart. Technical report, SMA and Partner AG, 2011. Published by \(\langle\)http://www.schlichtung-s21.de/〉. |

[23] | Ginkel, A.; Schöbel, A., To wait or not to wait? the bicriteria delay management problem in public transportation, Transportation science, 41, 4, 527-538, (2007) |

[24] | Heilporn, G.; De Giovanni, L.; Labbé, M., Optimization models for the single delay management problem in public transportation, European journal of operational research, 189, 3, 762-774, (2008) · Zbl 1146.90330 |

[25] | Herrmann TM. Stability of timetables and train routings through station regions. PhD thesis, ETH Zurich; 2005. |

[26] | Ho, T.K.; Norton, J.P.; Goodman, C.J., Optimal traffic control at railway junctions, IEE Proceedings, 144, 140-148, (1997) |

[27] | Ho, T.K.; Yeung, T.H., Railway junction traffic control by heuristic methods, IEE Proceedings electric power application, 148, 1, 77-84, (2001) |

[28] | Huerlimann D. Objektorientierte Modellierung von Infrastrukturelementen und Betriebsvorgängen im Eisenbahnwesen. PhD thesis, ETH Zurich; 2001. |

[29] | Huisman D. Integrated and dynamic vehicle and crew scheduling. PhD thesis, Tinbergen Institute, Erasmus University Rotterdam; 2004. |

[30] | Hürlimann G. Die Eisenbahn der Zukunft. PhD thesis, ETH Zürich; 2006. |

[31] | Iwnicki S. Handbook of railway vehicle dynamics. CRC Press; 2006. |

[32] | Jovanovic, D.; Harker, P.T., Tactical scheduling of rail operations: the scan i system, Transportation science, 25, 1, 46-64, (1991) |

[33] | Komaya, K., An integrated framework of simulation and scheduling in railway systems, Computers in railways III, 611-622, (1992) |

[34] | Kraft, E.R., A branch and bound procedure for optimal train dispatching, Journal of the transport research forum, 28, 263-276, (1987) |

[35] | Kuckelberg A. Mikroskopische Disposition spurgebundener Verkehrsmittel unter Echtzeitbedingungen; 2011. |

[36] | Lambropoulos, T., Genetic algorithm application for the solution of the optimal dispatching problem, Computers in railways VIII, 827-836, (2002) |

[37] | Lüthi M. Improving the efficiency of heavily used railway networks through integrated real-time rescheduling. PhD thesis, ETH Zurich; 2009. |

[38] | Maróti G. Operations research models for railway rolling stock planning. PhD thesis, TU Eindhoven; 2006. |

[39] | Mascis, A.; Pacciarelli, D., Job-shop scheduling with blocking and no-wait constraints, European journal of operational research, 143, 3, 498-517, (2002) · Zbl 1082.90528 |

[40] | Pachl, J., Railway operation and control, (2002), VTD Rail Publishing Mountlake Terrace, USA, ISBN 0-9719915-1-0 |

[41] | Padberg, M., On the facial structure of set packing polyhedra, Mathematical programming, 5, 199-255, (1973) · Zbl 0272.90041 |

[42] | Pascoal MMB. Implementations and empirical comparison of k shortest loopless path; 2006. |

[43] | Priewasser J. Dispatching in a main station area. Master’s thesis, ETH Zurich; 2009. |

[44] | Rodriguez, J., A constraint programming model for real-time train scheduling at junctions, Transportation research part B, 41, 2, 231-245, (2007) |

[45] | Rodriguez, J., A study of the use of state resources in a constraint-based model for routing and scheduling trains, () |

[46] | Sahin, I., Railway traffic control and train scheduling based on inter-train conflict management, Transportation research part B, 33, 511-534, (1999) |

[47] | Sauder, R.L.; Westerman, W.M., Computer aided train dispatching: decision support through optimization, Interfaces, 13, 6, 24-37, (1983) |

[48] | Schrijver, A., Combinatorial optimization, (2003), Springer · Zbl 0542.90067 |

[49] | () |

[50] | Törnquis J. Railway traffic disturbance management. PhD thesis, Blekinge Institute of Technology; 2006. |

[51] | Törnquist, J.; Persson, J.A., Train traffic deviation handling using tabu search and simulated annealing, (), 1-10 |

[52] | Törnquist, J.; Persson, J.A., N-tracked railway traffic re-scheduling during disturbances, Transportation research part B: methodological, 41, 3, 342-362, (2007) |

[53] | Tucker, A., An efficient test for circular-arc graphs, SIAM journal on computing, 9, 1, 1-24, (1980) · Zbl 0453.05054 |

[54] | Wegele S, Schnieder E. Dispatching of trains using genetic algorithms. In: Hansen IA, Dekking FM, Goverde RMP, Heidergott B, Meester LE, editors. 1st international seminar on railway operations modelling and analysis. Delft; 2005. |

[55] | Weidmann U, Wichser J, Barth E, Bepperling S, Höppner S, Kirsch U. Zukunft Bahnhof Bern (ZBB). Technical report, ETH Zurich, Institute for Transport Planning and Systems; 2009. |

[56] | Wende, D., Fahrdynamik des schienenverkehrs, (2003), Vieweg and Teubner, [in German]. ISBN 978-3-519-00419-6 |

[57] | Weymann F. Qualität von Heuristiken in der Disposition des Eisenbahnbetriebs. PhD thesis, Aachen: RWTH Aachen; 2011. |

[58] | Winter P. Current state and recent trends in European Railway Signalling and Telecommunication systems. In: UIC, editor. Railway signaling and telecommunication technology; 1998. p. 13-21. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.