Efficient Shortest Paths on Portable Devices

Bachelor Project - Winter 2016/17

Supervisors: Prof. Dr. Tobias Friedrich, Dr. Thomas Bläsius, Martin Krejca, Gregor Lagodzinski, Ralf Rothenberger
Links: Courses IT-Systems Engineering, Final Presentation (in German)

^{Photo credit: HPI/K. Herschelmann}

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: 3347-3354

[ Abstract ] [ BibTeX ] [ DOI ] [ 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 = {gregorlagodzinski janeube juliusseverin thomasblaesius martinskrejca year2018 thomasfeldtkeller smc tobiasfriedrich justintrautmann fabiansommer ralfrothenberger}, month = 10, pages = {3347-3354}, title = {Memory-restricted Routing With Tiled Map Data}, year = 2018 }

Participant

Hasso Plattner Institute

E-Mail: Justin.Trautmann(at)student.hpi.de

Efficient Shortest Paths on Portable Devices

Bachelor Project - Winter 2016/17

Problem and Motivation

Results

Project Team

Prof. Dr. Tobias Friedrich

Dr. Thomas Bläsius

Martin Krejca

Gregor Lagodzinski

Ralf Rothenberger

Jan Eube

Thomas Feldtkeller

Julius Severin

Fabian Sommer

Justin Trautmann

Algorithm Engineering

News

20.05.2019 | Paper invited to the IJCAI Sister Conference Best Paper Track

06.05.2019 | Three papers accepted at FCT, CIAC & WAW

25.04.2019 | HPI podcast on algorithms

23.04.2019 | Three papers accepted at GECCO, ICALP‑A & ICALP‑B

12.03.2019 | Paper accepted at SPAA

06.03.2019 | Tutorial on Network Science at STACS

Contact

Apply