Bachelor Project 2016/2017 – Efficient Shortest Paths on Portable Devices

Supervisors: Prof. Dr. Tobias Friedrich, Thomas Bläsius, Martin Krejca, Gregor Lagodzinski, Ralf Rothenberger
Link: Courses IT-Systems Engineering

The bachelor project is a cornerstone for the praxis-related study at the Hasso Plattner Institute. Central to this project is a group of students cooperating in developing a solution for a software-project given by an industrial partner. For the bachelor project 2016/2017 our project partner is TomTom Navigation.

Problem and Motivation

The road network graph of Europe contains more than 100 million nodes and half a billion edges. Performing route searches on such a graph in a setup with limited memory, like a Personal Navigation Device or a mobile phone, is a non-trivial task. For this purpose, modern maps are partitioned and stored in blocks (map tiles) according to a geometrical grid. Therefore, the major factor during the computation is the number of blocks of graph data loaded into memory. An A*-search algorithm with strong lower bounds for shortest path distances is important to optimize the number of cache loads.

Precomputed lower bounds for shortest paths between two tiles can be used to modify the order in which nodes are settled and further speed up Dijkstra-like searches. The right use of these properties will help to speed up route search on embedded devices and allow to build applications with a lower memory and energy footprint compared to the ones available today.

Results

The results of the project have been accepted as a conference paper at the IEEE International Conference on Systems, Man, and Cybernetics 2018 (SMC'18).

Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, Justin Memory-restricted Routing With Tiled Map Data. IEEE International Conference on Systems, Man, and Cybernetics (SMC) 2018

[ Abstract ] [ BibTeX ] [ Download ]

Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.

@inproceedings{blasius2018memory, abstract = {Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.}, author = {Bläsius, Thomas and Eube, Jan and Feldtkeller, Thomas and Friedrich, Tobias and Krejca, Martin S. and Lagodzinski, J. A. Gregor and Rothenberger, Ralf and Severin, Julius and Sommer, Fabian and Trautmann, Justin}, booktitle = {IEEE International Conference on Systems, Man, and Cybernetics (SMC)}, keywords = {sys:relevantfor:ae bp16 gregorlagodzinski martinskrejca ralfrothenberger smc student thomasblaesius tobiasfriedrich year2018}, title = {Memory-restricted Routing With Tiled Map Data}, year = 2018 }