# 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.

Transfer buffer /min | Query time /ms | settled nodes | #nodes | #edges | memory /MB | Graph construction /s | |
---|---|---|---|---|---|---|---|

Expanded | 0 | 79 | 154 959 | 886 174 | 2 063 207 | 195 | 6 |

Dependent | 22 | 14 234 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 1 | 78 | 153 065 | 886 174 | 2 063 207 | 195 | 6 |

Dependent | 21 | 15 076 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 2 | 80 | 151 226 | 886 174 | 2 063 207 | 195 | 6 |

Dependent | 22 | 15 190 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 4 | 86 | 147 782 | 886 174 | 2 063 193 | 195 | 6 |

Dependent | 24 | 15 260 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 8 | 84 | 141 555 | 886 174 | 2 063 179 | 195 | 6 |

Dependent | 24 | 15 355 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 16 | 78 | 131 170 | 886 174 | 2 062 882 | 195 | 6 |

Dependent | 24 | 15 450 | 33 324 | 84 705 | 17 | 10 | |

Expanded | 32 | 79 | 115 180 | 886 174 | 2 061 705 | 195 | 6 |

Dependent | 29 | 15 558 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 64 | 62 | 94 321 | 886 174 | 2 058 923 | 195 | 6 |

Dependent | 25 | 15 605 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 128 | 51 | 71 589 | 886 174 | 2 051 750 | 195 | 6 |

Dependent | 26 | 15 433 | 33 324 | 84 705 | 17 | 10 | |

Expanded | 256 | 43 | 58 149 | 886 174 | 2 032 704 | 193 | 6 |

Dependent | 28 | 15 361 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 512 | 31 | 39 432 | 886 174 | 1 969 164 | 189 | 6 |

Dependent | 28 | 15 307 | 33 324 | 84 705 | 17 | 9 | |

Expanded | 1024 | 19 | 17 129 | 886 174 | 1 837 012 | 181 | 6 |

Dependent | 24 | 15 135 | 33 324 | 84 705 | 17 | 9 |

Number of queries: 1000

Dataset: Manhattan, New York City, NY