×

A branch and bound algorithm for scheduling trains in a railway network. (English) Zbl 1179.90135

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adenso-Dı´az, B.; Oliva González, M.; González-Torre, P., On-line timetable rescheduling in regional train services, Transportation Research Part B, 33, 387-398 (1999)
[2] Brännlund, U.; Lindberg, P. O.; Nöu, A.; Nilsson, J. E., Railway timetabling using lagrangian relaxation, Transportation Science, 32, 358-369 (1998) · Zbl 1004.90035
[3] Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Operations Research, 50, 851-861 (2002) · Zbl 1163.90482
[4] Carlier, J., The one-machine sequencing problem, European Journal of Operational Research, 11, 42-47 (1982) · Zbl 0482.90045
[5] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management Science, 35, 2, 164-176 (1989) · Zbl 0677.90036
[6] Carlier, J.; Pinson, E., Adjustment of heads and tails for the job-shop problem, European Journal of Operational Research, 78, 146-161 (1994) · Zbl 0812.90063
[7] Cordeau, J. F.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transportation Science, 32, 4, 380-420 (1998) · Zbl 0987.90507
[8] 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 Transaction, 38, 2, 141-152 (2006)
[9] Dorfman, M. J.; Medanic, J., Scheduling trains on a railway network using a discrete event model of railway traffic, Transportation Research Part B, 38, 81-98 (2004)
[10] Fay, A., A fuzzy knowledge-based system for railway traffic control, Engineering Application of Artificial Intelligence, 13, 719-729 (2000)
[11] R. Hemelrijk, J. Kruijer, D.K. de Vries, Schiphol tunnel 2007. Description of the situation, Internal report, Holland Railconsult, Utrecht, The Netherlands, 2003.; R. Hemelrijk, J. Kruijer, D.K. de Vries, Schiphol tunnel 2007. Description of the situation, Internal report, Holland Railconsult, Utrecht, The Netherlands, 2003.
[12] Higgins, A.; Kozan, E.; Ferreira, L., Optimal scheduling of trains on a single line track, Transportation Research Part B, 30, 147-161 (1996)
[13] Higgins, A.; Kozan, E., Heuristic techniques for single line train scheduling, Journal of Heuristics, 3, 43-62 (1997) · Zbl 1071.90535
[14] J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, University of California, Los Angeles, USA, 1955.; J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, University of California, Los Angeles, USA, 1955.
[15] Jovanovic, D.; Harker, P. T., Tactical scheduling of train operations: The SCAN I system, Transportation Science, 25, 46-64 (1991)
[16] Kauppi, A.; Wikstrm, J.; Sandblad, B.; Andersson, A. W., Future train traffic control: Control by re-planning, Cognition Technology and Work, 8, 1, 50-56 (2006)
[17] Kraft, E., A branch and bound procedure for optimal train dispatching, Journal of the Transportation Research Forum, 28, 3, 263-276 (1987)
[18] 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
[19] Nie, L.; Hansen, I. A., System analysis of train operations and track occupancy at railway stations, European Journal of Transport and Infrastructure Research, 5, 1, 31-54 (2005)
[20] E. Oliveira, B.M. Smith, A Job-Shop Scheduling Model for the Single-Track Railway Scheduling Problem, School of Computing Research Report 2000.21, University of Leeds, England, 2000.; E. Oliveira, B.M. Smith, A Job-Shop Scheduling Model for the Single-Track Railway Scheduling Problem, School of Computing Research Report 2000.21, University of Leeds, England, 2000.
[21] Pachl, J., Railway Operation and Control Mountlake Terrace (2002), VTD Rail Publishing
[22] L. Ping, N. Axin, J. Limin, W. Fuzhang, Study on intelligent train dispatching, in: Proceedings of IEEE Intelligent Transportation Systems Conference, Oakland, USA, 25-29 August 2001.; L. Ping, N. Axin, J. Limin, W. Fuzhang, Study on intelligent train dispatching, in: Proceedings of IEEE Intelligent Transportation Systems Conference, Oakland, USA, 25-29 August 2001.
[23] Şahin, İ., Railway traffic control and train scheduling based on inter-train conflict management, Transportation Research Part B, 33, 511-534 (1999)
[24] A.A.M. Schaafsma, Dynamic traffic management – innovative solution for the Schiphol bottleneck 2007, in: Proceedings of the First International Seminar on Railway Operations Modelling and Analysis, Delft, The Netherlands, 8-10 June 2005.; A.A.M. Schaafsma, Dynamic traffic management – innovative solution for the Schiphol bottleneck 2007, in: Proceedings of the First International Seminar on Railway Operations Modelling and Analysis, Delft, The Netherlands, 8-10 June 2005.
[25] Szpigel, B., Optimal Train Scheduling on a Single Track Railway, (Ross, M., Operational Research ’72 (1973), Amsterdam: Amsterdam The Netherlands), 343-352
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.