Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An evaluation framework and algorithms for train rescheduling
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.ORCID iD: 0000-0001-8377-8536
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.ORCID iD: 0000-0002-8373-8398
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
2020 (English)In: Algorithms, E-ISSN 1999-4893, Vol. 13, no 12, article id 332Article in journal (Refereed) Published
Abstract [en]

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. © 2020 by the authors. Licensee MDPI, Basel, Switzerland.

Place, publisher, year, edition, pages
MDPI AG , 2020. Vol. 13, no 12, article id 332
Keywords [en]
Algorithm evaluation, Decision support systems, Multi-objective optimization, Parallel algorithms, Train rescheduling, Integer programming, Railroads, Traffic control, Complex disturbance, Evaluation framework, Infrastructure failures, Multi objective algorithm, Railway traffic systems, Traffic controllers, Train rescheduling algorithms, Heuristic algorithms
National Category
Transport Systems and Logistics Computer Sciences
Identifiers
URN: urn:nbn:se:bth-20887DOI: 10.3390/a13120332ISI: 000601873200001Scopus ID: 2-s2.0-85098057885OAI: oai:DiVA.org:bth-20887DiVA, id: diva2:1514544
Funder
Swedish Transport Administration, 108023,826206
Note

open access

Available from: 2021-01-06 Created: 2021-01-06 Last updated: 2023-03-29Bibliographically approved
In thesis
1. Parallel algorithms for solving the train timetable rescheduling problem
Open this publication in new window or tab >>Parallel algorithms for solving the train timetable rescheduling problem
2021 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In railways, it is essential to achieve high train punctuality. Thus, whenever disturbances occur, it is important to reschedule the trains effectively. This task is typically handled manually by traffic controllers in real-time. This thesis presents efficient computer algorithms for assisting traffic controllers in effectively rescheduling a train timetable during disturbances.

The train timetable rescheduling problem is typically hard to solve as the solutions of interest, spread across a vast solution space, need to be searched quickly. Two main solution approaches involve using (i) exact algorithms, which typically search the entire solution space, and (ii) heuristic algorithms, which try to search for a good-enough solution quickly. Although research on competitive algorithms is prevalent, limited research exists on exploring the benefits and challenges of using parallel computing to tackle the problem.

The primary objectives of this thesis are: (i) to model the train timetable rescheduling problem's search tree to be well-suited for parallel computing, (ii) to devise parallel heuristic search algorithms that can quickly and effectively solve the problem for one or many rescheduling objectives, (iii) to investigate the potential and limitations of parallel computing in the context of the problem, (iv) to investigate the comparison and evaluation of alternative solution approaches to analyze their strengths and limitations.

In this thesis, we model the problem's search tree as a binary tree where the edges represent alternative rescheduling decisions and leaf nodes represent feasible timetables. We solve the problem by searching the tree using a parallel strategy that combines a depth-first search with simultaneous breadth-wise tree exploration. We evaluate our parallel algorithms for various disturbances on a Swedish railway network through experiments.

The results of our research show that a parallel depth-first search algorithm can quickly search the devised search tree for solutions. With multiple rescheduling objectives, the parallel search algorithm obtained better solutions and showed higher speedups. Additional problem constraints often improved the search process by making the parallel algorithm reach the solutions faster. The results also show the potential and challenges of using graphics processing units for detecting conflicts in the timetable during the search. In conclusion, this thesis shows that parallel train timetable rescheduling algorithms can improve the search speed and the quality of the solution(s) obtained in real-time within the computational time limit.

Place, publisher, year, edition, pages
Karlskrona: Blekinge Tekniska Högskola, 2021. p. 249
Series
Blekinge Institute of Technology Doctoral Dissertation Series, ISSN 1653-2090 ; 6
Keywords
Parallel computing, Parallel heuristic search algorithms
National Category
Computer Sciences Transport Systems and Logistics
Research subject
Computer Science
Identifiers
urn:nbn:se:bth-22002 (URN)978-91-7295-426-7 (ISBN)
Supervisors
Available from: 2021-08-10 Created: 2021-08-09 Last updated: 2021-10-12Bibliographically approved

Open Access in DiVA

fulltext(733 kB)613 downloads
File information
File name FULLTEXT01.pdfFile size 733 kBChecksum SHA-512
2da2cfc68c78b4278d15df7f1ac646a19e16fbead8af0c1e5b8b54c479a29f9f4b99b4fc098b3f8246ecc9e4d61339f8636d73cb7b23c772314d62849bd99412
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Josyula, Sai PrashanthTörnquist Krasemann, JohannaLundberg, Lars

Search in DiVA

By author/editor
Josyula, Sai PrashanthTörnquist Krasemann, JohannaLundberg, Lars
By organisation
Department of Computer Science
In the same journal
Algorithms
Transport Systems and LogisticsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 613 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 246 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf