liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Algorithm for inserting a single train in an existing timetable
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The purpose with this report is to develop a network based insertion algorithm and evaluate it on a real-case timetable. The aim of the algorithm is to minimize the effect that that train implementation cause on the other, already scheduled traffic. We meet this purpose by choosing an objective function that maximizes the minimum distance to a conflicting train path. This ensures that the inserted train receives the best possible bottleneck robustness. We construct a graph problem, which solve with a modified version of Dijkstra’s algorithm. The complexity of the algorithm is Ο(s^2 t log⁡(s^2 t). We applied the algorithm on a Swedish timetable, containing 76 stations. The algorithm performs well and manage to obtain the optimal solution for a range of scenarios, which we have evaluated in various experiments. Increased congestion seemed to reduce the problem size. The case also show that a solution’s robustness decreases with increasing total number of departures. One disadvantage with the algorithm is that it cannot detect the best solution among those using the same bottleneck. We propose a solution to this that we hope can be implemented in further studies.

Place, publisher, year, edition, pages
2017. , p. 62
Keywords [en]
Timetabling, Label-setting algorithm, Robustness, Macroscopic model, Congested network, Train scheduling
National Category
Transport Systems and Logistics
Identifiers
URN: urn:nbn:se:liu:diva-141192ISRN: LiU-ITN-TEK-A--17/046--SEOAI: oai:DiVA.org:liu-141192DiVA, id: diva2:1144316
Subject / course
Transportation Systems Engineering
Uppsok
Technology
Supervisors
Examiners
Available from: 2017-09-26 Created: 2017-09-26 Last updated: 2017-09-26Bibliographically approved

Open Access in DiVA

Algorithm for inserting a single train in an existing timetable(2291 kB)208 downloads
File information
File name FULLTEXT01.pdfFile size 2291 kBChecksum SHA-512
6a8eddc47033b258603231adc9c5514c2e204a6b8ba2aa258701b471732eb454081cced7540c4e9d72759095220dd6dcb4c368db4ab206a8b3560213929df711
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Ljunggren, FredrikPersson, Kristian
By organisation
Communications and Transport SystemsThe Institute of Technology
Transport Systems and Logistics

Search outside of DiVA

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

urn-nbn

Altmetric score

urn-nbn
Total: 1106 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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