Bachelor Thesis BCLR-2022-55

BibliographyPang, Xin: Android Offline Route Planner with Contraction Hierarchies.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 55 (2022).
41 pages, english.

Navigation and finding a route from one point to another with a smartphone is a common need in modern life. In particular, one often finds oneself in an unknown area with no internet connection. At this point, a map application with offline routing functionality could be very useful. In this Bachelor thesis, an Android-based offline route planner application is implemented. Furthermore, the concept of Contraction Hierarchies (CH) is used to accelerate the query time over the classic Dijkstra algorithm. The correctness and efficiency of Dijkstra with CH are evaluated against the classic Dijkstra algorithm. When computing the shortest path in offline mode, we are working on a user-defined sub-graph, that could lead to problems when CH is used. The shortcuts in the shortest path may go across the sub-graph and therefore be ignored by the routing algorithm. At this point, some of its consisting edges will also be ignored, even if they are actually in the sub-graph. This sometimes leads to sub-optimal results or sometimes no result, even though there is indeed a path between source and target in the sub-graph. To solve such a problem, the classic Dijkstra algorithm is used to guarantee the correctness of the offline query. However one has to be able to tell whether such a problem occurred when the CH-query yields no results or possible sub-optimal results. This problem is also been addressed in this thesis.

Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Prof. Stefan, Weitbrecht, Felix
Entry dateOctober 27, 2022
   Publ. Computer Science