Master Thesis MSTR-2021-50

BibliographyBŁhler, Felix: Performance measurements for personalizable route planning for uncorrelated edge costs.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 50 (2021).
60 pages, english.
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.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Prof. Stefan; Barth, Florian
Entry dateNovember 24, 2021
   Publ. Computer Science