Transit Planner

An experiment on transfer patterns robustness in the presence of real-time updates

Master Team Project


Description

This project extends to the development of an efficient route planner for public transportation networks, which is used to conduct experiments on the reliability of transfer patterns on dynamically modified networks.

Timeframe

Winter 2011 - Summer 2012

Institute

University of Freiburg
Department of Computer Science
Chair of Algorithms and Data Structures

Supervisor

Prof. Dr. Hannah Bast
bast@informatik.uni-freiburg.de

Team

Toronto


Motivation

All state-of-the-art routing algorithms for road networks perform poorly on transit networks. One efficient method to compute optimal routes on transit networks is based on transfer patterns. It provides fast query response times even on huge networks.

However, due to the high time-complexity of the transfer patterns precomputation, dynamic real-time events like delays or connectivity problems could reduce the reliability of this method und thus the usability in real-world applications.


Task

This project is divided into two tasks. The first task is the creation of an efficient route planner for transit networks based on transfer patterns. Using the route planner, experiments on the robustness of transfer patterns on dynamic real-time events are to be conducted.

Because of the long duration of the complete transfer patterns precomputation, only time-efficient partial updates of the network are practical. The experiment should reveal how reliable transfer patterns are at sustaining the optimal routes on dynamic transit delays without a complete precomputation. Such robustness is an important criteria for the practicality of transfer patterns in real-world applications.