---

Real-time timetable information with dynamic updates

Screenshot von MOTIS

The search for train connections in state-of-the-art commercial timetable information systems is based on a static schedule. Unfortunately, public transportation systems suffer from delays for various reasons. Thus, dynamic changes of the planned schedule have to be taken into account.
Real-time train information with dynamic updates means that we can answer passenger queries instantly, i.e. ``real-time'' here means without noticeable delay. On a typical day of operation in Germany, an online system has to handle about 6 million forecast messages about (mostly small) changes with respect to the planned schedule and the latest prediction of the current situation. Note that this high number of changes also includes cases where delayed trains catch up some of their delay.

We have developed an approach which takes a stream of delay information and schedule changes on short notice (partial train cancellations, extra trains) into account. Primary delays of trains may cause a cascade of so-called secondary delays of other trains which have to wait according to certain policies for delays between connecting trains.
We have introduced the concept of a dependency graph to efficiently calculate and update all primary delays and forecast secondary delays. This delay information is then incorporated into a time-expanded search graph which also has to be updated dynamically. These update operations are quite complex, but turn out to be not time-critical in a fully realistic scenario.

This approach has been successfully integrated into the multi-criteria timetable information system MOTIS (developed in previous work) and can handle massive delay data streams instantly.

Details have been published in a special issue ``Robust and Online Large-Scale Optimization'' (edited by R. Ahuja, R.-H. Möhring, and C.~Zaroliagis) under the title Efficient Timetable Information in the Presence of Delays   .

Zum Seitenanfang