Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

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

Supervisor: Prof. Dr. Tobias Friedrich
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.

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

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

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