Performance measurements for personalizable route planning for uncorrelated edge costs

Abstract

Nowadays, ordinary route planners compute paths by choosing the shortest or fastest route. However, there exist additional metrics from which users with varying preferences could benefit. Personalized route planning offers the possibility to combine different metrics with personal preferences. Nevertheless, personalized route planning has mainly been tested with correlated metrics. But when including uncorrelated metrics, the computing time increases significantly. Previous work found that the speedup technique “Customizable Route Planning” can lead to feasible speedups for single metric calculations. Thus, in this work, we investigate how this speedup technique for Dijkstra improves the query performances of “Personalizable Route Planning” compared to “Personalizable Contraction Hierarchies”. Furthermore, we study the performances on uncorrelated metrics. We introduce a graph structure to compare the personalized speedup techniques “Personalizable Contraction Hierarchies”, “Personalizable Customizable Route Planning” and “Personalizable Route Planning”. Three graph partitioning algorithms have been implemented to realize “Customizable Route Planning”: K-means, Gonzales, and Merge. Our experiments show that Merge works well in combination with “Personalizable Contraction Hierarchies” preprocessing. We found that “Personalizable Customizable Route Planning” is a good alternative, as it uses much fewer edges for finding the costs of the shortest path. For uncorrelated metrics, “Personalizable Customizable Route Planning” and “Personalizable Route Planning” achieved speedups higher than “Personalizable Contraction Hierarchies”. Our contribution comprises a novel graph structure for comparing different Dijkstra variants. With our experiments, we provide a deeper understanding of the personalized route planning problem. Additionally, we propose improvements for “Personalizable Contraction Hierarchies” for less contracted graphs with uncorrelated metrics.

Heutzutage berechnen gewöhnliche Routenplaner Strecken, indem sie dabei die kürzeste oder schnellste Route auswählen. Es existieren jedoch zusätzliche Metriken, von welchen Nutzer mit unterschiedlichen Präferenzen profitieren könnten. Die personalisierte Routenplanung bietet die Möglichkeit, verschiedene Metriken anhand persönlicher Präferenzen zu kombinieren. Allerdings wurde die personalisierte Routenplanung bisher hauptsächlich auf korrelierten Metriken getestet. Werden jedoch unkorrelierte Metriken miteinbezogen, erhöht sich die Berechnungszeit erheblich. Frühere Arbeiten haben gezeigt, dass die Beschleunigungstechnik „Customizable Route Planning“ zu brauchbaren Beschleunigungen für einzelne Metrikberechnungen führen kann. Deshalb untersuchen wir in dieser Arbeit, wie diese Beschleunigungstechnik für Dijkstra die Abfrageleistungen von „Personalizable Route Planning“ im Vergleich zu „Personalizable Contraction Hierarchies“ verbessert. Zusätzlich untersuchen wir die Abfrageleistungen auf unkorrelierten Metriken. Wir führen eine Graphstruktur ein, um die personalisierten Beschleunigungstechniken „Personalizable Contraction Hierarchies“, „Personalizable Customizable Route Planning” und „Personalizable Route Planning“ zu vergleichen. Drei Graphpartitionierungsalgorithmen wurden implementiert um „Customizable Route Planning“ zu realisieren: K-means, Gonzalez, und Merge. Unsere Experimente zeigen, dass Merge in Kombination mit dem „Personalizable Contraction Hierarchies“-Preprocessing zu guten Ergebnissen führt. Wir haben herausgefunden, dass „Personalizable Customizable Route Planning“ eine gute Alternative ist, da weniger Kanten für die Ermittlung der Kosten des kürzesten Pfades verwendet werden. Für unkorrelierte Metriken erreichten „Personalizable Customizable Route Planning“ und „Personalizable Route Planning“ höhere Geschwindigkeitssteigerungen als „Personalizable Contraction Hierarchies“. Unser Beitrag umfasst eine neuartige Graphenstruktur, die es ermöglicht, verschiedene Dijkstra-Varianten zu vergleichen. In unseren Experimenten vermittlen wir damit ein tieferes Verständnis des Problems der personalisierten Routenplanung. Zusätzlich schlagen wir Verbesserungen für „Personalizable Contraction Hierarchies“ auf weniger kontrahierten Graphen mit unkorrelierten Metriken vor.