Shortest Path Routing in a Road Network:Finding an Easily Implementable Algorithm GivenEfficiency Constraints

Abstract: 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.