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
Shortest Path Routing in a Road Network:Finding an Easily Implementable Algorithm GivenEfficiency Constraints
KTH, School of Computer Science and Communication (CSC).
2014 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This thesis, conducted at Norconsult Astando AB, investigates and finds the best performing algorithm for routing in a road network given a set of constraints. The constraintsare mainly performance oriented and also the algorithm must not be too complex to implement. A study of algorithms was conducted and the most promising candidate, Contraction Hierarchies, was selectedfor implementation. Experiments suggest that Contraction Hierarchies perform as theoretically expected. Contraction Hierarchies is recommended as the algorithmthat best satisfies the constraints.

Abstract [sv]

Ruttning i ett vägnät: Hitta en enkelt implementerbar algoritm utifrån prestandakrav. Detta examensarbete, utfört på Norconsult AstandoAB, ämnar att hitta den bäst presterande algoritm för ruttning i ett vägnät utifrån ett antal restriktioner. Restriktionerna är mestadels prestanda men även att algoritmen inte får vara för komplicerad att implementera. Det gjordes en studie av algoritmer för att hitta den bästa kandidaten. Contraction Hierarchies var den mest lovande och utvaldes för implementation. Praktiska experiment antyder att Contraction Hierarchies presterar som teoretiskt förväntat. Contraction Hierarchies rekommenderas som den algoritm som bäst uppfyller alla restriktioner.

Place, publisher, year, edition, pages
2014.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-153944OAI: oai:DiVA.org:kth-153944DiVA: diva2:754334
Examiners
Available from: 2014-11-21 Created: 2014-10-10 Last updated: 2014-11-21Bibliographically approved

Open Access in DiVA

fulltext(1892 kB)546 downloads
File information
File name FULLTEXT01.pdfFile size 1892 kBChecksum SHA-512
8af0696f85dfa01fdddeb80a9fa718d1926c44a2d14fca66bb22808d6d5a64a5fe2fc813494db11ac22fa8a87fa93aab0f733092aaaece5c3c260617d6b61dc2
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

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