Change search
ReferencesLink to record
Permanent link

Direct link
Solving the Train Timetabling Problem by using Rapid Branching
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Användning av Rapid Branching vid tidtabelläggning för järnväg (Swedish)
Abstract [en]

The topic of this thesis is the implementation of rapid branching to find an integer solution for the train timetabling problem. The techniques that rapid branching are based on are presented. The important aspect of rapid branching are discussed and then the algorithm is applied to some artificial problems. It is shown that rapid branching can be both faster and slower than a standard integer solver depending on the problem instance. For the most realistic set of the examined instances, rapid branching turned out to be faster than the standard integer solver and produce satisficingly high quality solutions.


Abstract [en]

Den här uppsatsen handlar om en implementering av rapid branching för att hitta en heltalslösning till optimeringsproblemet vid tidtabelläggning för järnvägar. Rapid branching är en algoritm skapad för att fungera bra på storskaliga heltals-optimeringsproblem. I uppsatsen beskrivs några sätt att skapa egen tidtabelläggnings problem och sedan jämförs rapid branching med en vanlig heltalslösare för de problemen. Genom att göra detta visas att algoritmen rapid branching kan vara både snabbare och långsammare än att använda en konventionell heltalslösare. För den mest realistiska instansen av tidtabelläaggning problemet visade det sig att rapid branching var snabbare än heltalslösaren samt att den funna lösningen var av satisfierande hög kvalitet.

Place, publisher, year, edition, pages
TRITA-MAT-E, 2016:02
National Category
URN: urn:nbn:se:kth:diva-181308OAI: diva2:902529
Subject / course
Optimization and Systems Theory
Educational program
Master of Science - Mathematics
Available from: 2016-02-11 Created: 2016-01-30 Last updated: 2016-02-11Bibliographically approved

Open Access in DiVA

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

By organisation
Optimization and Systems Theory

Search outside of DiVA

GoogleGoogle Scholar
Total: 122 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: 140 hits
ReferencesLink to record
Permanent link

Direct link