Invited Session Wed.1.H 3021

Wednesday, 10:30 - 12:00 h, Room: H 3021

Cluster 2: Combinatorial optimization [...]

Routing for public transportation


Chair: Peter Sanders



Wednesday, 10:30 - 10:55 h, Room: H 3021, Talk 1

Matthias Müller-Hannemann
Coping with delays: Online timetable information and passenger-oriented train disposition


In daily operation, railway traffic always deviates from the planned
schedule to a certain extent. Primary initial delays of trains may
cause a whole cascade of secondary delays of other trains over the
entire network.
In this talk, we survey recent results for efficient online timetable
information, robust pretrip route planning, stochastic delay propagation,
and disposition management.
Disposition management solves the decision problem whether
a train should wait for incoming delayed trains or not.
This problem has a highly dynamic nature due to a steady stream of
update information about delayed trains.
We propose a new model for real-time train disposition
aiming at a passenger-friendly optimization and report about experimental
results with a prototypal implementation and test data of German Railways.



Wednesday, 11:00 - 11:25 h, Room: H 3021, Talk 2

Thomas Pajor
Round-based public transit routing

Coauthors: Daniel Delling, Renato Werneck


We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for two criteria: arrival time and number of transfers. Existing algorithms consider this as a graph problem, and solve it using variants of Dijkstra's algorithm. Unfortunately, this leads to either high query times or suboptimal solutions. We take a different approach. We introduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization using multiple cores. Because it does not rely on preprocessing, RAPTOR works in fully dynamic scenarios. Moreover, it can be easily extended to handle flexible departure times or arbitrary additional criteria, such as fare zones. When run on London's complex public transportation network, RAPTOR computes all Pareto-optimal journeys between two random locations an order of magnitude faster than previous approaches, which easily enables interactive applications.



Wednesday, 11:30 - 11:55 h, Room: H 3021, Talk 3

Hannah Bast
Next-generation route planning: Multi-modal, real-time, personalized


Route planning in static road networks or public transportation networks has reached a very high level of sophistication. The next challenges are: (1) Free combination of the various modes of transportation (walking, biking, driving, public transportation, flight, etc.). (2) Acquire and incorporate dynamic updates in real time (traffic jams, delayed trains, cancelled flights, etc.). (3) Provide personalized result diversity for each user (flexible optimization criteria, time-independent result summaries, etc.). I will talk about the state of the art and some recent advances with respect to these.


  There are three major facts that should be watched out for in all payday loans in the United States. The new drug with unique properties was developed to help men to get rid of all sexual disorders, and its name is Cialis Super Force. Now you do not have to buy two different medications to solve sexual problems.