×

A heuristic approach to solving the train traffic re-scheduling problem in real time. (English) Zbl 1461.90048

Summary: Effectiveness in managing disturbances and disruptions in railway traffic networks, when they inevitably do occur, is a significant challenge, both from a practical and theoretical perspective. In this paper, we propose a heuristic approach for solving the real-time train traffic re-scheduling problem. This problem is here interpreted as a blocking job-shop scheduling problem, and a hybrid of the mixed graph and alternative graph is used for modelling the infrastructure and traffic dynamics on a mesoscopic level. A heuristic algorithm is developed and applied to resolve the conflicts by re-timing, re-ordering, and locally re-routing the trains. A part of the Southern Swedish railway network from Karlskrona centre to Malmö city is considered for an experimental performance assessment of the approach. The network consists of 290 block sections, and for a one-hour time horizon with around 80 active trains, the algorithm generates a solution in less than ten seconds. A benchmark with the corresponding mixed-integer program formulation, solved by commercial state-of-the-art solver Gurobi, is also conducted to assess the optimality of the generated solutions.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B90 Case-oriented studies in operations research

Software:

Gurobi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] ; The 2017 European Railway Performance Index: Boston, MA, USA 2017; .
[2] ; Study on the Prices and Quality of Rail Passenger Services: Brussel, Belgium 2016; .
[3] Lamorgese, L.; Mannino, C.; Pacciarelli, D.; Törnquist Krasemann, J.; Train Dispatching; Handbook of Optimization in the Railway Industry, International Series in Operations Research & Management Science: Cham, Switzerland 2018; Volume Volume 268 . · Zbl 1396.90001
[4] Cacchiani, V.; Huisman, D.; Kidd, M.; Kroon, L.; Toth, P.; Veelenturf, L.; Wagenaar, J.; An overview of recovery models and algorithms for real-time railway rescheduling; Transp. Res. B Methodol.: 2010; Volume 63 ,15-37.
[5] Fang, W.; Yang, S.; Yao, X.; A Survey on Problem Models and Solution Approaches to Rescheduling in Railway Networks; IEEE Trans. Intell. Trans. Syst.: 2015; Volume 16 ,2997-3016.
[6] Josyula, S.; Törnquist Krasemann, J.; Passenger-oriented Railway Traffic Re-scheduling: A Review of Alternative Strategies utilizing Passenger Flow Data; Proceedings of the 7th International Conference on Railway Operations Modelling and Analysis: ; .
[7] Szpigel, B.; Optimal train scheduling on a single track railway; Oper. Res.: 1973; Volume 72 ,343-352.
[8] D’Ariano, A.; Pacciarelli, D.; Pranzo, M.; A branch and bound algorithm for scheduling trains in a railway network; Eur. J. Oper. Res.: 2017; Volume 183 ,643-657. · Zbl 1179.90135
[9] Khosravi, B.; Bennell, J.A.; Potts, C.N.; Train Scheduling and Rescheduling in the UK with a Modified Shifting Bottleneck Procedure; Proceedings of the 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 2012: ; ,120-131.
[10] Liu, S.; Kozan, E.; Scheduling trains as a blocking parallel-machine job shop scheduling problem; Comput. Oper. Res.: 2009; Volume 36 ,2840-2852. · Zbl 1160.90476
[11] Mascis, A.; Pacciarelli, D.; Job-shop scheduling with blocking and no-wait constraints; Eur. J. Oper. Res.: 2002; Volume 143 ,498-517. · Zbl 1082.90528
[12] Oliveira, E.; Smith, B.M.; ; A Job-Shop Scheduling Model for the Single-Track Railway Scheduling Problem: Leeds, UK 2000; .
[13] Törnquist, J.; Persson, J.A.; N-tracked railway traffic re-scheduling during disturbances; Transp. Res. Part B Methodol.: 2007; Volume 41 ,342-362.
[14] Pellegrini, P.; Douchet, G.; Marliere, G.; Rodriguez, J.; Real-time train routing and scheduling through mixed integer linear programming: Heuristic approach; Proceedings of the 2013 International Conference on Industrial Engineering and Systems Management (IESM): ; .
[15] Xu, Y.; Jia, B.; Ghiasib, A.; Li, X.; Train routing and timetabling problem for heterogeneous train traffic with switchable scheduling rules; Transp. Res. Part C Emerg. Technol.: 2017; Volume 84 ,196-218.
[16] Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M.; Centralized versus distributed systems to reschedule trains in two dispatching areas; Public Trans. Plan. Oper.: 2010; Volume 2 ,219-247.
[17] Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M.; Optimal inter-area coordination of train rescheduling decisions; Trans. Res. Part E: 2012; Volume 48 ,71-88. · Zbl 1247.90155
[18] Corman, F.; Pacciarelli, D.; D’Ariano, A.; Samá, M.; Rescheduling Railway Traffic Taking into Account Minimization of Passengers’ Discomfort; Proceedings of the International Conference on Computational Logistics, ICCL 2015: ; ,602-616.
[19] Lamorgese, L.; Mannino, C.; An Exact Decomposition Approach for the Real-Time Train Dispatching Problem; Oper. Res.: 2015; Volume 63 ,48-64. · Zbl 1327.90352
[20] Meng, L.; Zhou, X.; Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables; Trans. Res. Part B Methodol.: 2014; Volume 67 ,208-234.
[21] Tormo, J.; Panou, K.; Tzierpoulos, P.; Evaluation and Comparative Analysis of Railway Perturbation Management Methods; Proceedings of the Conférence Mondiale sur la Recherche Dans les Transports (13th WCTR): ; .
[22] Rodriguez, J.; An incremental decision algorithm for railway traffic optimisation in a complex station. Eleventh; Proceedings of the International Conference on Computer System Design and Operation in the Railway and Other Transit Systems (COMPRAIL08): ; ,495-504.
[23] Bettinelli, A.; Santini, A.; Vigo, D.; A real-time conflict solution algorithm for the train rescheduling problem; Trans. Res. Part B Methodol.: 2017; Volume 106 ,237-265.
[24] Samà, M.; D’Ariano, A.; Corman, F.; Pacciarelli, D.; A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations; Comput. Oper. Res.: 2017; Volume 78 ,480-499. · Zbl 1391.90311
[25] Burdett, R.L.; Kozan, E.; A sequencing approach for creating new train timetables; OR Spectr.: 2010; Volume 32 ,163-193. · Zbl 1181.90112
[26] Tan, Y.; Jiang, Z.; A Branch and Bound Algorithm and Iterative Reordering Strategies for Inserting Additional Trains in Real Time: A Case Study in Germany; Math. Probl. Eng.: 2015; Volume 2015 ,289072. · Zbl 1394.90415
[27] Gholami, O.; Sotskov, Y.N.; A fast heuristic algorithm for solving parallel-machine job-shop scheduling problems; Int. J. Adv. Manuf. Technol.: 2014; Volume 70 ,531-546.
[28] Sotskov, Y.; Gholami, O.; Mixed graph model and algorithms for parallel-machine job-shop scheduling problems; Int. J. Prod. Res.: 2017; Volume 55 ,1549-1564.
[29] Krasemann, J.T.; Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances; Transp. Res. Part C Emerg. Technol.: 2012; Volume 20 ,62-78.
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.