Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
A parallel algorithm for train rescheduling
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
2018 (English)In: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 95, p. 545-569Article in journal (Refereed) Published
Abstract [en]

One of the crucial factors in achieving a high punctuality in railway traffic systems, is the ability to effectively reschedule the trains when disturbances occur. The railway traffic rescheduling problem is a complex task to solve both from a practical and a computational perspective. Problems of practically relevant sizes have typically a very large search space, making them time-consuming to solve even for state-of-the-art optimization solvers. Though competitive algorithmic approaches are a widespread topic of research, not much research has been done to explore the opportunities and challenges in parallelizing them. This paper presents a parallel algorithm to efficiently solve the real-time railway rescheduling problem on a multi-core parallel architecture. We devised (1) an effective way to represent the solution space as a binary tree and (2) a novel sequential heuristic algorithm based on a depth-first search (DFS) strategy that quickly traverses the tree. Based on that, we designed a parallel algorithm for a multi-core architecture, which proved to be 10.5 times faster than the sequential algorithm even when run on a single processing core. When executed on a parallel machine with 8 cores, the speed further increased by a factor of 4.68 and every disturbance scenario in the considered case study was solved within 6 s. We conclude that for the problem under consideration, though a sequential DFS approach is fast in several disturbance scenarios, it is notably slower in many other disturbance scenarios. The parallel DFS approach that combines a DFS with simultaneous breadth-wise tree exploration, while being much faster on an average, is also consistently fast across all scenarios.

Place, publisher, year, edition, pages
Elsevier, 2018. Vol. 95, p. 545-569
Keywords [en]
Railway traffic; Rescheduling; Parallel depth-first search; Optimization
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:bth-16868DOI: 10.1016/j.trc.2018.07.003ISI: 000447112500032OAI: oai:DiVA.org:bth-16868DiVA, id: diva2:1239007
Projects
TRANS-FORM
Funder
Swedish Research Council Formas
Note

open access

Available from: 2018-08-15 Created: 2018-08-15 Last updated: 2018-11-01

Open Access in DiVA

fulltext(2312 kB)33 downloads
File information
File name FULLTEXT01.pdfFile size 2312 kBChecksum SHA-512
6f3f5749770b2bacd120af54096be5d630c3aaf8f327b4c8c8b77774f15b7afa41b5cf24cc4343bef81e51e36cfc8fb1d337451dcbcff5f9cf9c0f742f823062
Type fulltextMimetype application/pdf

Other links

Publisher's full texthttps://doi.org/10.1016/j.trc.2018.07.003

Authority records BETA

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 and Engineering
In the same journal
Transportation Research Part C: Emerging Technologies
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 33 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: 138 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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