Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Computing Strategic Routes

Bachelor Project - Winter 2019/20

Background

With over 50 million cars registered in Germany, traffic is an everyday challenge for millions of travellers. However, if everybody is driving the same route, traffic congestion leads to longer travel times for everyone involved. This can be tackled by strategic routing, where (re)routing recommendations are distributed by traffic authorities and taken into account by the drivers' navigation systems. This central coordination will lead to faster, greener and safer traffic.

To this end, we want to help develop new smart traffic and navigation services. By analyzing real-time traffic data and predicting the traffic situation, we can avoid that road users get stuck regularly in traffic through real-time coordinated traffic management and navigation advice. This rerouting can be achieved, for instance, by offering toll discount vouchers to encourage drivers to choose an alternative route.

Challenge

Our industry partner TomTom is involved in the project Socrates 2.0, which is a pan-European project that brings together road authorities, service providers and car manufacturers. The cities involved in this project collect traffic data which can be used for computing strategic routes. Therefore, the cities want to manually predefine traffic density scenarios which are then executed. The rerouting recommendations should be chosen such that the general traffic flow is optimized.

The travelling speed depends in a non-linear fashion on the traffic density. This makes the optimization difficult and interesting since by rerouting cars, one can achieve free flow on the roads.

Vision

We want to develop new algorithms for choosing optimal strategic routes. There is a variety of models to formalize different aspects of traffic and navigation, such as the relation between traffic density and travelling speed (cf. the above plot). Together with our project partner, we will choose suitable models to develop algorithms for finding the optimal rerouting to improve the overall traffic flow. We will compare our achieved results with the outcome of the recommendations made by the city of Amsterdam. The scientific method will be two-fold: (1) an empirical study of different methods on real-world data and (2) a thorough analysis of the theoretical limitations.

Alternative routes provided by navigation systems are one way of implementing strategic routing.

Industry Partner Contribution

TomTom is a Dutch multinational developer & creator of navigation technology and consumer electronics, founded in 1991 and headquartered in Amsterdam. Besides their location in Amsterdam, TomTom is strongly represented in Berlin and opened a traffic centre with their complete portfolio in 2016. We will work together with the team in Berlin. Through their involvement in the Socrates 2.0 project, the company will provide the team with real-world traffic data. During the project, they will support the team with the required background in navigation and traffic systems as well as providing different approaches for tackling this exciting challenge.

Our Contribution

The research group will work closely with you on the project and will provide expertise in algorithm engineering, graph theory and game theory. We will help you develop theoretical models to investigate the provided data and quality of solution approaches. As in previous bachelor and master projects of our group, we plan to write a joint scientific publication about our research findings.

Your Contribution

In your work as a team, you will develop and customize a bundle of algorithms for solving the problem at hand. For exploring industrial-size traffic datasets, you will create the necessary code infrastructure and efficient algorithms for strategic routing models. Besides the team experience in an industrial context, you will learn about efficient data processing and the practical use of graph theory and other related fields.

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

Project Supervisor

Hasso Plattner Institute

Office: A-1.5
Tel.: +49 331 5509-419
E-Mail: Pascal.Lenzner(at)hpi.de

Project Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.4
Tel.: +49 331 5509-412
E-Mail: Thomas.Blaesius(at)hpi.de
Links: Homepage, Publications

Advisor

Hasso Plattner Institute

Office: A-1.7/8
Tel.: +49 331 5509-413
E-Mail: Philipp.Fischbeck@hpi.de

Advisor

Hasso Plattner Institute

Office: A-1.7/8
Tel.: +49 331 5509-415
E-Mail: Louise.Molitor@hpi.de