Change search
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
Sannolikhetsbaserad reseplanering – nya algoritmer för bytestidsoptimering.
KTH, School of Computer Science and Communication (CSC).
2012 (Swedish)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The thesis explores a probabilistic view on travel planning, focusing on calculating better transfer times for journeys combining high and low frequency traffic. Two new algorithms that take the whole journey into account when calculating transfers and transfer times are defined and analyzed regarding time complexity and practical usability. Both algorithms make use of statistical data to model delays and cancelled trips so as to ensure that the passenger reaches the destination in time with a probability higher than a set threshold value.

The first algorithm is simple and the function used to model deviations in arrival and departure times can easily be replaced. It is however deemed too slow for most practical applications.

The second algorithm improves on the first and is argued to be fast enough to be usable in practice. It also has few rules and settings that need to be manually maintained and treats transfers within a stop and between stops in a similar way. Problems with the algorithm, the most important how to present the result to the user, are discussed and some solutions are sketched. Much work would indeed be required to turn the algorithm into a commercially competitive travel planner. It does however provide some interesting characteristics not present in any travel planner known by the author.

Abstract [sv]

Detta examensarbete undersöker reseplanering ur en sannolikhetsbaserad infallsvinkel, med fokus på bättre beräkningar av bytestider vid resor som kombinerar hög- och lågfrekvent trafik. Två nya algoritmer som med hänsyn till totalresan beräknar byten och bytestider definieras och analyseras avseende tidskomplexitet och praktisk användbarhet. Båda algoritmerna utnyttjar statistiska data för att modellera förseningar och inställda turer. Algoritmerna säkerställer att resenären når destinationen i tid med en sannolikhet högre än ett bestämt tröskelvärde.

Den första algoritmen är enkel och den funktion som modellerar avvikelser i ankomst- och avgångstider kan lätt bytas ut. Den bedöms dock vara för långsam för att vara praktiskt användbar i de flesta fall.

Den andra algoritmen, som är en utveckling av den första, är snabb nog att vara praktiskt tillämpbar. Den har få regler och inställningar som kräver manuellt underhåll och hanterar byten mellan och inom hållplatser på ett jämförbart sätt. Problem med algoritmen, inte minst kring hur en framsökt resa presenteras för användaren, tas upp och diskuteras och vissa lösningar skisseras. Mycket arbete skulle dock krävas för att förvandla algoritmen till en kommersiellt konkurrenskraftig reseplanerare. Den uppvisar dock vissa intressanta egenskaper som alla reseplanerare som författaren känner till saknar.

Place, publisher, year, edition, pages
2012.
Series
Trita-CSC-E, ISSN 1653-5715 ; 2012:037
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-130996OAI: oai:DiVA.org:kth-130996DiVA: diva2:654442
Educational program
Master of Science in Engineering - Computer Science and Technology
Uppsok
Technology
Supervisors
Examiners
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

Other links

http://www.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/2012/rapporter12/weiland_marcus_12037.pdf
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 31 hits
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