Benchmark

The benchmark shows the result of computing 1000 random routes for both the time expanded and the time dependent graph with different transfer buffers.

We expect the reasons for the differences in the number of settled labels for the time-dependent and time-expanded approach to be the following: In our implementation of the time-expanded graph, the explored search space consists exactly of those nodes (Note there are arrival-, departure- and transfer-nodes) which can be reached from the start-node before the target-node is reached. On the other hand, our implementation of the time-dependent graph leads to a reduced search space, where those labels are ignored, which do not provide a better path in terms of travel-duration.
For example, if station B can be reached from station A in 2 minutes, and station C can be reached from B in 2 minutes and the transfer-time is exactly 1 minute and there are different trains (T1, T2, T3) arriving and departing at 9:00, 9:02 and 9:04 from A. Then it is - in our terms of optimality - not necessary to arrive at B with T2 at 9:04, because it is sufficient to arrive at B with T1 at 9:02 since one has sufficient time to transfer to T2.
Also note that we expect the number of settled labels to decrease in the time-expanded graph with increasing transfer-time, as only very late OSM nodes are inserted into the priority queue. This results in more and more OSM nodes to be considered and fewer GTFS nodes, which basically means that the search is more and more reduced to a search in the (comparatively small) OSM subgraph.