Welcome to the Minimum Expected Arrival Time demo. The goal of this website is to illustrate recent results in robust train journey planning using a live-demo. For those of you that want to start right away, just click here. The remainder of this page will describe some of the details.
The main problem with current journey planners is that they assume that no unexpected delays can occur. However, in practice delays do occur. We want to show passengers in advance what alternative trains exist in case they miss a connecting train. This looks as following:
The image above depicts a decision graph from Karlsruhe to Berlin. The boxes represent stops and the arrows are trains. As can be seen a transfer in Hanover is needed. It is not certain that the train incomming from Karlsruhe will be on time and therefore it is uncertain whether the passenger will be able to get the first direct train to Berlin. However, if he misses the connection, he knows that only 5 minutes later the next train will depart, using more transfers on a different route, and is therefore a lot less worried. If the user also misses this backup train, then unfortunately for him, his best option is to wait an hour in Hanover.
Notice that in the example above we only included train departure times. In the demo you can click on a stop to get details (such as names) about all departing trains.
All journey planners known to us compute sequences of trains (i.e., first take train A, then train B, then train C). Instead of computing decision graphs one could try to compute a robust train sequence. However, a sequence is either robust (i.e., has huge buffer times) or is very risky (i.e., has nearly no buffer times). Often you will not find a sequence that is both robust and fast. Decision graphs do not have this problem. We can include risky connections in the diagram as long as we also include robust backup connections. We tell the user to try out the risky connection. If he misses it he should use the safe backup.
The goal of our work is to compute routes that are robust against delays in train journeys. The first source of delays that most people think of are train delays. However, note that this is not the only significant source. Often passengers need more time to get from platform to platform than expected. This can have many reasons: Some passengers might walk slower than others, some might get lost, some might go to the toilette, again others might buy a coffee at some shop in the station. All of these small delays can lead to passengers missing connections even if all trains are on time. It is not always the operators fault if a passenger misses a train.
The data is based on an older dataset that was given to us by Deutsche Bahn for research purposes. We are not allowed to give the data to other researchers without explicit permission of Deutsch Bahn. The dataset used in the demo is outdated and we do not plan to update it. The objective of this demo is show what is possible to do with the algorithms we developed. The demo is not supposed to be a journey planner that should be used in productive use. If you plan on trying out one of the proposed routes then be sure to check on the official Deutsch Bahn website whether the proposed trains actually drive.
The reason lies within the way the demo loads its data. It extracts all trains regardless of their days of operation and merges them into a single day. It then removes duplicated trains to obtain a single day of maximum operation. This day is then copied 4 times and this is the instance used in the demo. As all days in this setting are the same we only allow queries to start within the first day.
At first this method sounds awkward, but recall that this demo was build for research purposes and not for productive use. One of our goals was to do stress tests and see how the algorithm reacts. Doing this on a day with too few trains can distort the results. To avoid this we use days of maximum operation. These artificial days have more trains than any real day and thus we can be certain that if the algorithms manage to handle these, then no real day will be a problem.
The demo has several parameters:
We first generate a decision graph using a variant of the Connection Scan algorithm (CSA) and then use the "dot"-layout algorithm from the GraphViz project. The demo reports the running time spent in the Connection Scan algorithm and in the "dot"-layout engine separately.