Conclusion

The results show clearly that the transfer patterns computed for the unbiased transit network allow for correct routing on a delayed network. Even for scenarios with high share of delay and high average delay the failure rate of the transfer pattern based routing is sufficiently low to be negelectable in real-world applications. Exemplary reviews of the failing queries have also shown that most of the non-optimal transfer patterns paths would not be necessarily perceived as irrational routes by travelers.

The results support the idea of transfer pattern routing: There are only a limited number of good trip plans for any pair of stops. If the favorite trip is delayed or cancelled, there are only few alternatives, one of which is simply waiting for the next trip of the same line. This is especially true for short-distance transits. For long-distance transits this is not always the case. E.g. when travelling through multiple cities and experiencing a major delay on the favorite trip, a feasible alternative can differ essentially from the usual route. It could even lead through different cities. However, such cases are handled well by the redundancies introduced through hub stations, since any long trip probably leads through a hub.

Transfer patterns are robust to delay because of the redundant information obtained during the precomputation for each stop. The building process of the query graph creates additional routes that are suboptimal in the original network maybe optimal in the delayed network.

We have shown that real-time updates in the network do not necessarily require a full recompuation of the transfer patterns. It suffices to temporarily change the direct connection database. This has low computational effort, so Transfer Pattern Routing can adapt fast to real-time updates without suffering quality of shortest path queries.

Future work

Our experiments have been conducted on artificial data. We assumed the delay of routes is independently distributed over all lines, and has a constant amount starting at one stop of a line. In real applications, this is not true. Lines depend on each other. A crashed bus may block an entire route for some hours, delaying other trips as well. Moreover, once delayed a transit vehicle probably sums up more delay because it runs out of its usual schedule. It remains to repeat our experiments on real-world data for delay. However, such data is not available by the time of writing.

Transfer patterns allow for almost correct routing in the presence of delay due to the redundant information of shortest paths between stops independent of the departure time. Another topic for future research is if the robustness to real-time updates can be improved further by increasing that redundancy. In other words, during precomputation not only the shortest path, but for example the best 5% of paths are used to create the transfer pattern.