{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:34Z","timestamp":1770681634939,"version":"3.49.0"},"reference-count":42,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,12,11]],"date-time":"2020-12-11T00:00:00Z","timestamp":1607644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In railway traffic systems, whenever disturbances occur, it is important to effectively reschedule trains while optimizing the goals of various stakeholders. Algorithms can provide significant benefits to support the traffic controllers in train rescheduling, if well integrated into the overall traffic management process. In the railway research literature, many algorithms are proposed to tackle different versions of the train rescheduling problem. However, limited research has been performed to assess the capabilities and performance of alternative approaches, with the purpose of identifying their main strengths and weaknesses. Evaluation of train rescheduling algorithms enables practitioners and decision support systems to select a suitable algorithm based on the properties of the type of disturbance scenario in focus. It also guides researchers and algorithm designers in improving the algorithms. In this paper, we (1) propose an evaluation framework for train rescheduling algorithms, (2) present two train rescheduling algorithms: a heuristic and a MILP-based exact algorithm, and (3) conduct an experiment to compare the two multi-objective algorithms using the proposed framework (a proof-of-concept). It is found that the heuristic algorithm is suitable for solving simpler disturbance scenarios since it is quick in producing decent solutions. For complex disturbances wherein multiple trains experience a primary delay due to an infrastructure failure, the exact algorithm is found to be more appropriate.<\/jats:p>","DOI":"10.3390\/a13120332","type":"journal-article","created":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T20:56:57Z","timestamp":1607893017000},"page":"332","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["An Evaluation Framework and Algorithms for Train Rescheduling"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8377-8536","authenticated-orcid":false,"given":"Sai Prashanth","family":"Josyula","sequence":"first","affiliation":[{"name":"Department of Computer Science, Blekinge Institute of Technology, 37141 Karlskrona, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johanna T\u00f6rnquist","family":"Krasemann","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Blekinge Institute of Technology, 37141 Karlskrona, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Lundberg","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Blekinge Institute of Technology, 37141 Karlskrona, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.trc.2016.08.011","article-title":"A new rail optimisation model by integration of traffic management and train automation","volume":"71","author":"Rao","year":"2016","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Terlaky, T., Anjos, M.F., and Ahmed, S. (2017). Advances and Trends in Optimization with Engineering Applications, SIAM.","DOI":"10.1137\/1.9781611974683"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lamorgese, L., Mannino, C., and Piacentini, M. (2017). Integer Optimization Techniques for Train Dispatching in Mass Transit and Main Line. Advances and Trends in Optimization with Engineering Applications, SIAM.","DOI":"10.1137\/1.9781611974683.ch6"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.trc.2016.11.015","article-title":"Recent success stories on integrated optimization of railway systems","volume":"74","author":"Klug","year":"2017","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_5","unstructured":"Peterson, A., Wahlborg, M., H\u00e4ll, C.H., Schmidt, C., Kordnejad, B., Warg, J., Johansson, I., Joborn, M., Gestrelius, S., and T\u00f6rnquist Krasemann, J. (2020, October 26). Deliverable D 3.1: Analysis of the Gap between Daily Timetable and Operational Traffic. Available online: https:\/\/www.semanticscholar.org\/paper\/Deliverable-D-3.1%3A-Analysis-of-the-gap-between-and-Peterson-Wahlborg\/e27a5bff7cead805b824ebce44d2223a7a495b65."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2997","DOI":"10.1109\/TITS.2015.2446985","article-title":"A survey on problem models and solution approaches to rescheduling in railway networks","volume":"16","author":"Fang","year":"2015","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_7","first-page":"535","article-title":"Comparing the effectiveness of two real-time train rescheduling systems in case of perturbed traffic conditions","volume":"103","author":"Wegele","year":"2008","journal-title":"Comput. Railw."},{"key":"ref_8","unstructured":"Flier, H.F. (2011). Optimization of Railway Operations: Algorithms, Complexity, and Models. [Ph.D. Thesis, ETH Zurich]."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.trb.2014.01.009","article-title":"An overview of recovery models and algorithms for real-time railway rescheduling","volume":"63","author":"Cacchiani","year":"2014","journal-title":"Transp. Res. Part Methodol."},{"key":"ref_10","unstructured":"Morant, A. (2014). Dependability and Maintenance Analysis of Railway Signalling Systems. [Ph.D. Thesis, Lule\u00e5 University of Technology]."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Van Thielen, S. (2019). Conflict Prevention Strategies for Real-Time Railway Traffic Management. [Ph.D. Thesis, KU Leuven].","DOI":"10.1016\/j.jrtpm.2019.07.001"},{"key":"ref_12","first-page":"42","article-title":"Differences and similarities in European railway disruption management practices","volume":"8","author":"Schipper","year":"2018","journal-title":"J. Rail Transp. Plan. Manag."},{"key":"ref_13","unstructured":"Tschirner, S. (2015). The GMOC Model: Supporting Development of Systems for Human Control. [Ph.D. Thesis, Uppsala University]."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/j.trb.2017.10.005","article-title":"A real-time conflict solution algorithm for the train rescheduling problem","volume":"106","author":"Bettinelli","year":"2017","journal-title":"Transp. Res. Part Methodol."},{"key":"ref_15","unstructured":"T\u00f6rnquist, J. (2006, January 14). Computer-based decision support for railway traffic scheduling and dispatching: A review of models and algorithms. Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS\u201905), Palma, Spain."},{"key":"ref_16","first-page":"146","article-title":"A multi-criteria decision support methodology for real-time train scheduling","volume":"5","author":"Meloni","year":"2015","journal-title":"J. Rail Transp. Plan. Manag."},{"key":"ref_17","first-page":"23","article-title":"A comparison of algorithms for minimising delay costs in disturbed railway traffic scenarios","volume":"2","author":"Fan","year":"2012","journal-title":"J. Rail Transp. Plan. Manag."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/j.trb.2010.08.001","article-title":"An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network","volume":"45","author":"Min","year":"2011","journal-title":"Transp. Res. Part Methodol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.trb.2006.06.001","article-title":"N-tracked railway traffic re-scheduling during disturbances","volume":"41","author":"Persson","year":"2007","journal-title":"Transp. Res. Part Methodol."},{"key":"ref_20","first-page":"95","article-title":"Computational decision-support for railway traffic management and associated configuration challenges: An experimental study","volume":"5","year":"2015","journal-title":"J. Rail Transp. Plan. Manag."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1080\/03081060.2018.1453916","article-title":"Automated real-time railway traffic control: An experimental analysis of reliability, resilience and robustness","volume":"41","author":"Corman","year":"2018","journal-title":"Transp. Plan. Technol."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Josyula, S.P., T\u00f6rnquist Krasemann, J., and Lundberg, L. (2020). Parallel computing for multi-objective train rescheduling. IEEE Trans. Emerg. Top. Comput.","DOI":"10.1109\/TETC.2020.3030984"},{"key":"ref_23","unstructured":"Josyula, S.P., and T\u00f6rnquist Krasemann, J. (2017, January 4\u20137). 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, Lille, France."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.tre.2013.04.003","article-title":"A direct comparison of physical block occupancy versus timed block occupancy in train timetabling formulations","volume":"54","author":"Harrod","year":"2013","journal-title":"Transp. Res. Part Logist. Transp. Rev."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Lamorgese, L., Mannino, C., Pacciarelli, D., and T\u00f6rnquist Krasemann, J. (2018). Train Dispatching. Handbook of Optimization in the Railway Industry, Springer.","DOI":"10.1007\/978-3-319-72153-8_12"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.trc.2015.01.014","article-title":"Closing the loop in real-time railway control: Framework design and impacts on operations","volume":"54","author":"Corman","year":"2015","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.trpro.2015.09.012","article-title":"What about train length and energy efficiency of freight trains in rescheduling models?","volume":"10","author":"Toletti","year":"2015","journal-title":"Transp. Res. Procedia"},{"key":"ref_28","unstructured":"(2020, October 26). Trafikverket Network Statement. Available online: www.trafikverket.se\/en\/startpage\/operations\/Operations-railway\/Network-Statement\/network-statement-2020\/."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1287\/opre.2014.1327","article-title":"An Exact Decomposition Approach for the Real-Time Train Dispatching Problem","volume":"63","author":"Lamorgese","year":"2015","journal-title":"Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Li, M., and Yao, X. (2019). Quality Evaluation of Solution Sets in Multiobjective Optimisation: A Survey. ACM Comput. Surv., 52.","DOI":"10.1145\/3300148"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.trc.2019.02.022","article-title":"A closed form railway line delay propagation model","volume":"102","author":"Harrod","year":"2019","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_32","unstructured":"Hwang, C.L., and Masud, A.S.M. (2012). Multiple Objective Decision Making\u2014Methods and Applications: A State-of-the-Art Survey, Springer."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Arora, J.S. (2017). Chapter 18\u2014Multi-objective Optimum Design Concepts and Methods. Introduction to Optimum Design, Academic Press. [4th ed.].","DOI":"10.1016\/B978-0-12-800806-5.00018-4"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/S0377-2217(03)00020-1","article-title":"Compromise solution by MCDM methods: A comparative analysis of VIKOR and TOPSIS","volume":"156","author":"Opricovic","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1016\/j.trc.2018.07.003","article-title":"A parallel algorithm for train rescheduling","volume":"95","author":"Josyula","year":"2018","journal-title":"Transp. Res. Part Emerg. Technol."},{"key":"ref_36","unstructured":"Optimization, L.G. (2020, October 26). Gurobi Optimizer Reference Manual Version 9.0. Available online: https:\/\/www.gurobi.com\/wp-content\/plugins\/hd_documentations\/documentation\/9.0\/refman.pdf."},{"key":"ref_37","unstructured":"Trafikverket (2017, November 28). Maps of Traffic Management Areas. Available online: https:\/\/www.trafikverket.se\/for-dig-i-branschen\/jarnvag\/Trafikledning."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Verma, J., and Abdel-Salam, A.S.G. (2019). Testing Statistical Assumptions in Research, John Wiley & Sons.","DOI":"10.1002\/9781119528388"},{"key":"ref_39","unstructured":"McDonald, J.H. (2009). Handbook of Biological Statistics, Sparky House Publishing."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Marino, M.J. (2018). Chapter 3\u2014Statistical Analysis in Preclinical Biomedical Research. Research in the Biomedical Sciences, Academic Press.","DOI":"10.1016\/B978-0-12-804725-5.00003-3"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1007\/s11081-017-9366-1","article-title":"Best practices for comparing optimization algorithms","volume":"18","author":"Beiranvand","year":"2017","journal-title":"Optim. Eng."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1016\/j.ejor.2006.10.034","article-title":"A branch and bound algorithm for scheduling trains in a railway network","volume":"183","author":"Pacciarelli","year":"2007","journal-title":"Eur. J. Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/332\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:43:50Z","timestamp":1760179430000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/12\/332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,11]]},"references-count":42,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["a13120332"],"URL":"https:\/\/doi.org\/10.3390\/a13120332","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,11]]}}}