Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A parallel algorithm for train rescheduling
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datalogi och datorsystemteknik.
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datalogi och datorsystemteknik.
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datalogi och datorsystemteknik.
2018 (Engelska)Ingår i: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 95, s. 545-569Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Elsevier, 2018. Vol. 95, s. 545-569
Nyckelord [en]
Railway traffic; Rescheduling; Parallel depth-first search; Optimization
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
URN: urn:nbn:se:bth-16868DOI: 10.1016/j.trc.2018.07.003ISI: 000447112500032OAI: oai:DiVA.org:bth-16868DiVA, id: diva2:1239007
Projekt
TRANS-FORM
Forskningsfinansiär
Forskningsrådet Formas
Anmärkning

open access

Tillgänglig från: 2018-08-15 Skapad: 2018-08-15 Senast uppdaterad: 2019-08-15
Ingår i avhandling
1. Parallel algorithms for real-time railway rescheduling
Öppna denna publikation i ny flik eller fönster >>Parallel algorithms for real-time railway rescheduling
2019 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

In railway traffic systems, it is essential to achieve a high punctuality to satisfy the goals of the involved stakeholders. Thus, whenever disturbances occur, it is important to effectively reschedule trains while considering the perspectives of various stakeholders. The train rescheduling problem is a complex task to solve, both from a practical and a computational perspective. From the latter perspective, a reason for the complexity is that the rescheduling solution(s) of interest may be dispersed across a large solution space. This space needs to be navigated fast while avoiding portions leading to undesirable solutions and exploring portions leading to potentially desirable solutions. The use of parallel computing enables such a fast navigation of the search tree. Though competitive algorithmic approaches for train rescheduling are a widespread topic of research, limited research has been conducted to explore the opportunities and challenges in parallelizing them.

This thesis presents research studies on how trains can be effectively rescheduled while considering the perspectives of passengers along with that of other stakeholders. Parallel computing is employed, with the aim of advancing knowledge about parallel algorithms for solving the problem under consideration.

The presented research contributes with parallel algorithms that reschedule a train timetable during disturbances and studies the incorporation of passenger perspectives during rescheduling. Results show that the use of parallel algorithms for train rescheduling improves the speed of solution space navigation and the quality of the obtained solution(s) within the computational time limit.

This thesis consists of an introduction and overview of the work, followed by four research papers which present: (1) A literature review of studies that propose and apply computational support for train rescheduling with a passenger-oriented objective; (2) A parallel heuristic algorithm to solve the train rescheduling problem on a multi-core parallel architecture; (3) A conflict detection module for train rescheduling, which performs its computations on a graphics processing unit; and (4) A redesigned parallel algorithm that considers multiple objectives while rescheduling.

Ort, förlag, år, upplaga, sidor
Sweden: Blekinge Institute of Technology, 2019. s. 184
Serie
Blekinge Institute of Technology Licentiate Dissertation Series, ISSN 1650-2140 ; 9
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:bth-18511 (URN)978-91-7295-378-9 (ISBN)
Presentation
2019-10-17, J1640, Campus Gräsvik, Karlskrona, 09:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2019-08-02 Skapad: 2019-08-02 Senast uppdaterad: 2019-09-17Bibliografiskt granskad

Open Access i DiVA

fulltext(2312 kB)88 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 2312 kBChecksumma SHA-512
6f3f5749770b2bacd120af54096be5d630c3aaf8f327b4c8c8b77774f15b7afa41b5cf24cc4343bef81e51e36cfc8fb1d337451dcbcff5f9cf9c0f742f823062
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltexthttps://doi.org/10.1016/j.trc.2018.07.003

Personposter BETA

Josyula, Sai PrashanthTörnquist Krasemann, JohannaLundberg, Lars

Sök vidare i DiVA

Av författaren/redaktören
Josyula, Sai PrashanthTörnquist Krasemann, JohannaLundberg, Lars
Av organisationen
Institutionen för datalogi och datorsystemteknik
I samma tidskrift
Transportation Research Part C: Emerging Technologies
Teknik och teknologier

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 88 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 263 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf