Change search
ReferencesLink to record
Permanent link

Direct link
Re-scheduling the Railway Traffic using Parallel Simulated Annealing and Tabu Search: A comparative study
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Context: This study has been conducted in the area of train rescheduling. One of the most common types of disturbance scenarios are trains which have deviated from their originally planned arrival or departure times. This type of disturbance is of today handled manually by the train dispatcher, which in some cases can be cumbersome and overwhelmingly complex to solve. Therefore, there is an essential need for a train re-scheduling decision support system.

Objectives: The aim of the study is to determine if parallel adaptations of simulated annealing(SA), and tabu search(TS) are able to find high quality solutions for the train re-scheduling problem. The study also aims to compare the two proposed meta-heuristics in order to determine the more adequate algorithm for the given problem.

Methods: To answer the research question sequential and parallel versions of the algorithms were implemented. Further the research methodology of choice was experiment, were the meta-heuristics are evaluated based on 10 disturbance scenarios.

Results: Parallel simulated annealing(PSA) is overall the better performing algorithm, as it is able to reduce the total delay by 585 seconds more than parallel tabu search(PTS) for the 10 disturbance scenarios. However, PTS is able to solve more conflicts per millisecond than PTS, when compared to their sequential versions.

Conclusions: We conclude that both the parallel versions perform better than their sequential versions. Further, PSA is clearly able to outperform PTS in terms of minimizing the accumulated delay. One observation is that the parallel versions are not reaching their max efficiency per thread, this is assumed to be caused by the RAM. For future work we propose further investigation of why we are not reaching the max efficiency per thread, and further improvement of algorithm settings.

Place, publisher, year, edition, pages
Keyword [en]
Parallel Computing, tabu search, simulated annealing, train re-scheduling
National Category
Computer Science
URN: urn:nbn:se:bth-10375OAI: diva2:839041
Subject / course
DV2524 Degree Project in Computer Science for Engineers
Educational program
DVACI Master of Science in Computer and Electrical Engineering
Available from: 2015-07-03 Created: 2015-07-01 Last updated: 2015-07-09Bibliographically approved

Open Access in DiVA

fulltext(1078 kB)119 downloads
File information
File name FULLTEXT02.pdfFile size 1078 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer Science

Search outside of DiVA

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

Total: 362 hits
ReferencesLink to record
Permanent link

Direct link