Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Efficient Shortest Paths on Portable Devices

Bachelor Project - Winter 2016/17 and Summer 2017

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).

  • Memory-restricted Routing... - Download
    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 DataSystems, Man, and Cybernetics (SMC) 2018: 3347–3354
     

Further, the students presented the results of this project at the Bachlorpodium 2017.

Project Team

The bachelor project is organized by the Algorithm Engineering group. The following group members and students are participating:

Project Supervisor

Hasso Plattner Institute

Office: A-1.10
Tel.: +49 331 5509-410
E-Mail: Friedrich(at)hpi.de

Advisor

Hasso Plattner Institute

Office: A-1.4
Tel.: +49 331 5509-412
E-Mail: Thomas.Bläsius@hpi.de

Advisor

Office hours: on weekdays usually 9 a.m. to 4 p.m.
Office: A-1.7/8

E-Mail: Martin.Krejca(at)hpi.de

Advisor

Office hours: on weekdays usually 11 a.m. to 5 p.m.
Office: A-1.7/8

E-Mail: Gregor.Lagodzinski(at)hpi.de

Ralf Rothenberger

Advisor

Office hours: on weekdays usually 9 a.m. to 4 p.m.
Office: A-1.13

E-Mail: Ralf.Rothenberger(at)hpi.de

Jan Eube

Participant

Hasso Plattner Institute

E-Mail: Jan.Eube(at)student.hpi.de

Thomas Feldtkeller

Participant

Hasso Plattner Institute

E-Mail: Thomas.Feldtkeller(at)student.hpi.de

Julius Severin

Participant

Hasso Plattner Institute

E-Mail: Julius.Severin(at)student.hpi.de

Fabian Sommer

Participant

Hasso Plattner Institute

E-Mail: Fabian.Sommer(at)student.hpi.de

Justin Trautmann

Participant

Hasso Plattner Institute

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