Master Thesis MSTR-2018-13

BibliographyBarth, Florian: Multi-criteria bicycle routing.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 13 (2018).
43 pages, english.

This thesis considers the problem of finding alternative routes by weighting multiple metrics. This approach has the benefit that it always yields a Pareto optimal path. These routes have to be then checked against a similarity measure to ensure that they are different enough for a user to consider them helpful. The Splitting Algorithm designed in this thesis uses a geometric intuition to explore the possible weightings and find good alternative routes heuristically. To achieve fast query times although many routes need to be calculated and compared, the algorithm builds upon the multi-criteria version of the contraction hierarchies speed-up technique. In an implementation for cyclists with three metrics, the algorithm found up to thirteen routes that share less than 50% of their length and four or five routes in half the cases.

Full text and
other links
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Prof. Stefan
Entry dateMay 24, 2019
   Publ. Computer Science