Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
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
2016.
Series
TRITA-MAT-E, 2016:02
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-181308OAI: oai:DiVA.org:kth-181308DiVA: diva2:902529
External cooperation
VTI
Subject / course
Optimization and Systems Theory
Educational program
Master of Science - Mathematics
Supervisors
Examiners
Available from: 2016-02-11 Created: 2016-01-30 Last updated: 2016-02-11Bibliographically approved

Open Access in DiVA

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

By organisation
Optimization and Systems Theory
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 480 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: 300 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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