An Evaluation Framework and Algorithms for Train Rescheduling
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 traf...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-12-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/12/332 |
| _version_ | 1827700289968275456 |
|---|---|
| author | Sai Prashanth Josyula Johanna Törnquist Krasemann Lars Lundberg |
| author_facet | Sai Prashanth Josyula Johanna Törnquist Krasemann Lars Lundberg |
| author_sort | Sai Prashanth Josyula |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T14:09:12Z |
| format | Article |
| id | doaj.art-d331707609784361a51aae43183b068d |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T14:09:12Z |
| publishDate | 2020-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-d331707609784361a51aae43183b068d2023-11-21T00:22:30ZengMDPI AGAlgorithms1999-48932020-12-01131233210.3390/a13120332An Evaluation Framework and Algorithms for Train ReschedulingSai Prashanth Josyula0Johanna Törnquist Krasemann1Lars Lundberg2Department of Computer Science, Blekinge Institute of Technology, 37141 Karlskrona, SwedenDepartment of Computer Science, Blekinge Institute of Technology, 37141 Karlskrona, SwedenDepartment of Computer Science, Blekinge Institute of Technology, 37141 Karlskrona, SwedenIn 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.https://www.mdpi.com/1999-4893/13/12/332algorithm evaluationdecision support systemsparallel algorithmsmulti-objective optimizationtrain rescheduling |
| spellingShingle | Sai Prashanth Josyula Johanna Törnquist Krasemann Lars Lundberg An Evaluation Framework and Algorithms for Train Rescheduling Algorithms algorithm evaluation decision support systems parallel algorithms multi-objective optimization train rescheduling |
| title | An Evaluation Framework and Algorithms for Train Rescheduling |
| title_full | An Evaluation Framework and Algorithms for Train Rescheduling |
| title_fullStr | An Evaluation Framework and Algorithms for Train Rescheduling |
| title_full_unstemmed | An Evaluation Framework and Algorithms for Train Rescheduling |
| title_short | An Evaluation Framework and Algorithms for Train Rescheduling |
| title_sort | evaluation framework and algorithms for train rescheduling |
| topic | algorithm evaluation decision support systems parallel algorithms multi-objective optimization train rescheduling |
| url | https://www.mdpi.com/1999-4893/13/12/332 |
| work_keys_str_mv | AT saiprashanthjosyula anevaluationframeworkandalgorithmsfortrainrescheduling AT johannatornquistkrasemann anevaluationframeworkandalgorithmsfortrainrescheduling AT larslundberg anevaluationframeworkandalgorithmsfortrainrescheduling AT saiprashanthjosyula evaluationframeworkandalgorithmsfortrainrescheduling AT johannatornquistkrasemann evaluationframeworkandalgorithmsfortrainrescheduling AT larslundberg evaluationframeworkandalgorithmsfortrainrescheduling |