An Evaluation Framework and Algorithms for Train Rescheduling
Open Access
- 11 December 2020
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 13 (12) , 332
Abstract
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.Keywords
This publication has 31 references indexed in Scilit:
- A Survey on Problem Models and Solution Approaches to Rescheduling in Railway NetworksIEEE Transactions on Intelligent Transportation Systems, 2015
- Closing the loop in real-time railway control: Framework design and impacts on operationsTransportation Research Part C: Emerging Technologies, 2015
- An Exact Decomposition Approach for the Real-Time Train Dispatching ProblemOperations Research, 2015
- An overview of recovery models and algorithms for real-time railway reschedulingTransportation Research Part B: Methodological, 2014
- A direct comparison of physical block occupancy versus timed block occupancy in train timetabling formulationsTransportation Research Part E: Logistics and Transportation Review, 2013
- A comparison of algorithms for minimising delay costs in disturbed railway traffic scenariosJournal of Rail Transport Planning & Management, 2012
- An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway networkTransportation Research Part B: Methodological, 2011
- A branch and bound algorithm for scheduling trains in a railway networkEuropean Journal of Operational Research, 2007
- N-tracked railway traffic re-scheduling during disturbancesTransportation Research Part B: Methodological, 2007
- Compromise solution by MCDM methods: A comparative analysis of VIKOR and TOPSISEuropean Journal of Operational Research, 2004