1213141516171817 of 18
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
Parallel algorithms for real-time railway rescheduling
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
2019 (English)Licentiate thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Sweden: Blekinge Institute of Technology , 2019. , p. 184
Series
Blekinge Institute of Technology Licentiate Dissertation Series, ISSN 1650-2140 ; 9
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-18511ISBN: 978-91-7295-378-9 (print)OAI: oai:DiVA.org:bth-18511DiVA, id: diva2:1340183
Presentation
2019-09-09, J1640, Campus Gräsvik, Karlskrona, 13:00 (English)
Opponent
Supervisors
Available from: 2019-08-02 Created: 2019-08-02 Last updated: 2019-08-23Bibliographically approved
List of papers
1. Passenger-oriented Railway Traffic Re-scheduling: A Review of Alternative Strategies utilizing Passenger Flow Data
Open this publication in new window or tab >>Passenger-oriented Railway Traffic Re-scheduling: A Review of Alternative Strategies utilizing Passenger Flow Data
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Developing and operating seamless, attractive and efficient public transport services in a liberalized market requires significant coordination between involved actors, which is both an organizational and technical challenge. During a journey, passengers often transfer between different transport services. A delay of one train or a bus service can potentially cause the passenger to miss the transfer to the subsequent service. If those services are provided by different operators and those are not coordinated and the information about the services are scattered, the passengers will suffer. In order to incorporate the passenger perspective in the re-scheduling of railway traffic and associated public transport services, the passenger flow needs to be assessed and quantified. We therefore perform a survey of previous research studies that propose and apply computational re-scheduling support for railway traffic disturbance management with a passenger-oriented objective. The analysis shows that there are many different ways to represent and quantify the effects of delays on passengers, i.e.“passenger inconvenience”. In the majority of the studies, re-scheduling approaches rely on historic data on aggregated passenger flows, which are independent of how the public transport services are re-scheduled. Few studies incorporate a dynamic passenger flow model that reacts based on how the transport services are re-scheduled. None of the reviewed studies use real-time passenger flow data in the decision-making process. Good estimations of the passenger flows based on historic data are argued to be sufficient since access to large amounts of passenger flow data and accurate prediction models is available today.

Keywords
Train re-scheduling, Passenger satisfaction, Passenger flow dynamics, Delay management
National Category
Infrastructure Engineering Computer Sciences
Identifiers
urn:nbn:se:bth-14114 (URN)
Conference
7th International Conference on Railway Operations Modelling and Analysis, Lille
Projects
TRANS-FORMFLOAT
Available from: 2017-04-19 Created: 2017-04-19 Last updated: 2019-08-15Bibliographically approved
2. A parallel algorithm for train rescheduling
Open this publication in new window or tab >>A parallel algorithm for train rescheduling
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
Keywords
Railway traffic; Rescheduling; Parallel depth-first search; Optimization
National Category
Engineering and Technology
Identifiers
urn:nbn:se:bth-16868 (URN)10.1016/j.trc.2018.07.003 (DOI)000447112500032 ()
Projects
TRANS-FORM
Funder
Swedish Research Council Formas
Note

open access

Available from: 2018-08-15 Created: 2018-08-15 Last updated: 2019-08-15
3. Exploring the Potential of GPU Computing in Train Rescheduling
Open this publication in new window or tab >>Exploring the Potential of GPU Computing in Train Rescheduling
2019 (English)In: Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis, Norrköping, 2019., 2019Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-18510 (URN)
Conference
8th International Conference on Railway Operations Modelling and Analysis
Available from: 2019-08-02 Created: 2019-08-02 Last updated: 2019-08-15Bibliographically approved
4. A parallel algorithm for multi-objective train rescheduling
Open this publication in new window or tab >>A parallel algorithm for multi-objective train rescheduling
(English)Manuscript (preprint) (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-18542 (URN)
Available from: 2019-08-15 Created: 2019-08-15 Last updated: 2019-09-06Bibliographically approved

Open Access in DiVA

fulltext(8929 kB)12 downloads
File information
File name FULLTEXT05.pdfFile size 8929 kBChecksum SHA-512
a58fd2aa30448f7b0d377925a7dd9f01e582687550583dd05a9f35fc1bee5986992f01586b1296410deea5385c115aa6574c6c27536cc1e8731fb5c8ddb6b66f
Type fulltextMimetype application/pdf

Authority records BETA

Josyula, Sai Prashanth

Search in DiVA

By author/editor
Josyula, Sai Prashanth
By organisation
Department of Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 57 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 519 hits
1213141516171817 of 18
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