Multi-criteria bicycle routing

Abstract

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.

Diese Arbeit beschäftigt sich mit dem Finden von Alternativrouten durch das Gewichten mehrerer Metriken. Dies hat den Vorteil, dass immer Pareto-optimale Routen gefunden werden. Die Routen werden dann durch ein Ähnlichkeitsmaß geprüft, um sicherzustellen, dass sie unterschiedlich genug sind, um für einen Benutzer hilfreich zu sein. Der Splitting Algorithmus, der in dieser Arbeit entworfen wurde, nutzt eine geometrische Anschauung, um auf heuristische Weise die möglichen Gewichtungen zu explorieren und gute Alternativrouten zu finden. Um kurze Laufzeiten zu erreichen, obwohl viele Routen berechnet und verglichen werden müssen, baut der Algorithmus auf der multi-kriteriellen Variante der Contraction Hierarchy speed-up Technik auf. In einer Implementierung für Fahrradrouten mit drei Metriken fand der Algorithmus bis zu dreizehn Routen, die weniger als 50% ihrer Distanz gemein hatten und vier oder fünf Routen in der Hälfte aller Fälle.