For more than twenty years, Prof. Dr. Karsten Weihe has been cooperating with Deutsche Bahn AG on research into the field of timetable information systems. Since 2001, Prof. Dr. Weihe has been working at the University of Darmstadt with the professional consultancy of Wolfgang Sprick (datagon GmbH). Felix Gündling and Dr. Mathias Schnee, assistants of Prof. Dr. Weihe, have been working on the project which will be introduced here: multimodal travel planning. Additional current research is being undertaken in order to create travel plans which allow a high probability of arriving at the target destination on a fixed date and at a fixed time, as well as off-peak connections early in the morning or late in the evening. All these projects are financed by Deutsche Bahn. In partnership with the University of Darmstadt, datagon have started to cooperate with suppliers of other transportation systems in special aspects of intermodal mobility.
Between 2002 and 2009, we developed MOTIS as a system for multi-criteria travel planning. The list of alternatives proposed by MOTIS for a travel enquiry is comprehensive in the sense that all possible customer preferences are covered which result from varied weightings of total travel time, total travel price and any potential inconveniences (for instance, changes of train). For some years, we have been building on the latter by developing a prototype software system which now comprises multi-criteria travel plans from means of transport which are not just timetable dependent. Our focus is set on the most complex real case scenario where trains, buses, trams or any other form of public transport still form the core of any travel plan, but with the inclusion of individual means of transport that are available at the start, during and at the end of the journey. This allows the enquirer to see options that, in effect, provide a door-to-door service – where he or she journeys from address A in city X to the starting station and from the target station to the final address B in city Y.
Our algorithmic approach is based on a multi-criteria expansion of the well-known Dijkstra algorithm to calculate the shortest path within a network. This is already taught in basic informatics courses, and also forms the basis of the algorithms within sat nav systems. Of course, the algorithm in its simple textbook form is far from sufficient for the complex scenario we envisaged. Our search algorithm is exploring all possibilites and does not exclude any option at the very beginning. Also, during our search for travel alternatives, the process we are using is conservative, i.e. only very unpromising options are excluded from subsequent searches. Multifarious, complex decision-making techniques for controlling the search process and for early elimination of unpromising options had to be developed in order not to exclude options prematurely and, at the same time, to prevent the number of included options from growing exponentially. In this process, time of travel and convenience are criteria unlikely to cause significant problems since they are compatible with the multi-criteria shortest route search logic. However, there are algorithmic challenges involved at the boundaries of the tariff systems of Deutsche Bahn and those of local public transport providers.
The traditional non-public means of transport are already integrated into our system and evaluated: walking, cycling, taking taxis, making trips in own’s own vehicle, and private ride share. An initial basic version of a search for parking space within the vicinity of public transport stations is also integrated. At present, we are working on the integration of all kinds of sharing offers: car sharing, bike sharing, dynamic ride-sharing. Our system is designed to be open, which means that further means of transport can be integrated with reasonable implementation effort, once the necessary data for timetable information are available.
All these means of transport and their combinations are competing with each other in our system. The person making the enquiry may decide which means of transport is suitable for him/her. He/she then obtains a list of travel plans for their enquiry in which several means of transport may be combined in various ways.
As mentioned above, trains plus public local transport are the core of travel plans within our concept, which also includes reasonable walks between two closely-located local public transport stations. It is perfectly reasonable, even within a train connection, to combine the use of the “airliner” bus with a brief walk from the the airport terminal to the target train station in the middle of a train journey. Flights and long-distance buses, as well as every further timetable-dependent means of transport, can be integrated in the same way. At the end of the day, it is only a question of whether or not the data are available.
However, we are entering new territory which requires an approach that allows the various public-transport parts of the journey to be interspersed with individual means of transport within the train connections between different stations. This includes a range of modes of transport – for instance, taking taxis, car sharing, carry-on bicycles or bike sharing. The difference, for example, in the case of the “airliner” is that departure train station and target train station can be selected by the traveller using individual means of transport instead of being fixed by a timetable. This leads to a squared number of combinations of potential departure and target train stations to be included. On the other hand, it appears that the cases with an intermezzo of individual means of transport is something that should be relatively limited and would be easily identifiable. This means that it could be handled separately. In particular, the most complex computations can be outsourced to the data preparing process in order to relieve the search from this effort.
We are cooperating with flinc AG on the integration of dynamic ride sharing. By rerouting the drivers, potential passengers can be picked up at their starting address or dropped off at their target address. Trips with flinc within a train connection, i.e. from station to station, seem possible in principle. The number of possible travel alternatives is, however, growing to a scale which is hard to manage for algorithms. This is because, (1) any arbitrarily-chosen stations, near or far, have to be considered and, (2) any arbitrarily chosen flinc drivers, near or far, are eligible for selection, since even very long route changes may be considered reasonable by the enquirer. An example of this is the following: a driver on the trip from Heidelberg to Stuttgart could take along a passenger from Karlsruhe to Pforzheim without a long detour even if he planned to drive via Heilbronn and not via Karlsruhe.
So what additional knowledge have we acquired so far from our work on a multimodal travel information system? It is still too early for final statements but a tentative, though nevertheless reasonable conclusion, may already be drawn. First and foremost, we can conclude that a multimodal travel enquiry with the algorithmic techniques we have developed is a realistic future possibility.
The response times of our system during comprehensive, realistic simulations is promising, even though many additional options to speed up the search time have not yet even been implemented, not to mention the impact of faster hardware that will be available in the future.
Based both on our experience with the step-by-step integration of new means of transport, and on our preliminary analysis of planned, further steps of integration, we are optimistic that our integration concept is “scalable”. Further means of transport will, of course, come up with new algorithmic questions that need answering, but they will be solvable and response time will increase in a “linear” rather than exponential fashion.
In summary, many steps towards realistic multimodal travel information have been successful, but there is a significant requirement for further research to master the various small and large algorithmic challenges on our way.
We have to mention, though, that we are following an integrated approach that means all data are available in our system. We are very sceptical whether our multimodal travel information system would be sufficiently effective if, instead of accessing one database, the servers of various transport providers had to be involved in the enquiry stages of the travel planning process. For multimodal travel planning to be realizable, there must be agreement from the various transport providers to share their data with the owners of travel information systems in an appropriate form and with adequate usage and license agreements.
Deutsche Bahn, as a current travel supplier which aims to be a future integrated intermodal traffic service provider, is strongly interested in this kind of enquiry system and, thereby, supports research that can permanently validate the usability of these approaches in algorithmic and processual aspects.
Felix Gündling
Dr. Mathias Schnee
Wolfgang Sprick (datagon GmbH)
Prof. Dr. Karsten Weihe