Practical Course: Route Planning

• Lecturers: Thomas Bläsius, Adrian Feilhauer, Moritz Laupichler, Michael Zündorf
• Registration: Register by sending your name and matriculation number via email to Michael Zündorf
• Slots: 9
• Studiengang: Master Computer Science and Master Informationswirtschaft. Can be counted towards the Bachelor's in Computer Science. Further options upon request.
• Credits: 6 ECTS

Attendance is mandatory for all dates. Since slots are limited, we reserve the right to reassign slots if you are absent without excuse.

Determining optimal routes in transportation networks is a common problem. Whereas travel routes were previously planned using maps at the kitchen table, today computer-assisted route planning is widely established among the general population: the best train connections are found online, and mobile devices are frequently used for route planning in road networks.

A common approach to solve this problem is to model the transportation network as a graph. An optimal connection then corresponds to the shortest path in this graph. Although Dijkstra’s algorithm provably solves this problem optimally, due to the large volume of data (road networks of continental scale have several million nodes and edges), this approach is too slow even on modern server hardware and thus not practical.

For this reason, route planning is a very active and diverse research area within algorithm engineering. Beyond the fundamental question of faster methods for computing routes on road networks, aspects such as all-pairs shortest paths, alternative routes, timetable queries, or dynamic techniques that can handle traffic jams or delays in real time are of particular interest.

This practical course aims to provide interested students the opportunity to implement and experimentally evaluate state-of-the-art techniques in the field of route planning. In addition to the correctness of the implemented algorithms, a focus lies on performance (time and memory consumption). The course complements the lecture Algorithmen für Routenplanung, which takes place during the summer semester. A brief introduction to the essential fundamentals at the beginning also allows students without specialized prior knowledge to participate.

In the first in-person session, a theoretical foundation of the material will be provided; in addition, there will be an opportunity for practical familiarization with the topic and the libraries used through several warm-up exercises. Subsequently, teams of three (in exceptional cases two) students, individually supervised by staff members, will work on one or more larger tasks. Approximately at the midpoint and end of the semester, each group will present their progress in a presentation. Finally, a written report of the results is to be prepared using LaTeX.

Basic knowledge in algorithm engineering and graph theory, as well as fundamental skills in C++ (or related languages), are recommended for participation in the practical course (any missing knowledge will be addressed through preparatory exercises; however, any additional time required will not be reflected in the ECTS credits). Attendance of the lecture Algorithmen für Routenplanung is not mandatory.