Authors: Matthias Müller-Hannemann and Mathias Schnee
Abstract: We consider efficient algorithms for timetable information in public transportation systems under multiple objectives like, for example, travel time, ticket costs, and number of interchanges between different means of transport. In this paper we focus on a fully realistic scenario in public railroad transport as it appears in practice while most previous work studied only simplified models.
Bahnhofsuhr mit Zug (C) Pexels Dom.J
Algorithmically this leads to multi-criteria shortest path problems in very large graphs. With several objectives the challenge is to find all connections which are potentially attractive for customers. To meet this informal goal we introduce the notion of relaxed Pareto dominance. Another difficulty arises from the fact that due to the complicated fare regulations even the single-criteria optimization problem of finding cheapest connections is intractable. Therefore, we have to work with fare estimations during the search for good connections.In a cooperation with Deutsche Bahn Systems we realized this scenario in a prototypal implementation called PARETO based on a time-expanded graph model. Computational experiments with our PARETO server demonstrate that the current central server of Deutsche Bahn AG often fails to give optimal recommendations for different user groups. In contrast, an important feature of the PARETO server is its ability to provide many attractive alternatives.
You may download the full article here: Mueller-Hannemann, Schnee: Finding All Attractive Train Connections by Multi-criteria Pareto Search