Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time

We study the problem of computing delay-robust routes in timetable networks. Instead of a single path we compute a decision graph containing all stops and trains/vehicles that might berelevant. Delays are formalized using a stochastic model. We show how to compute a decisiongraph that minimizes the expected arrival time while bounding the latest arrival time over allsub-paths. Finally we show how the information contained within a decision graph can compactlybe represented to the user. We experimentally evaluate our algorithms and show that the running times allow for interactive usage on a realistic train network.