# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 7 Experimental Study
### Experimental Setup
For more details about GTFS, see [[https://gtfs.org/](https://gtfs.org/)]([https://gtfs.org/](https://gtfs.org/)) and [[https://developers.google.com/transit/gtfs/](https://developers.google.com/transit/gtfs/)]([https://developers.google.com/transit/gtfs/](https://developers.google.com/transit/gtfs/)). Details on the used inputs for basic ptl are given in Table 2 while those of the inputs considered for the multi-criteria setting are given in Table 3.  
We remark here that we were forced to use smaller inputs in the latter case with respect to the basic one, since: (i) the preprocessing phase is much more time consuming with respect to basic case; and (ii) the labelings require several GB of main memory to be stored. Hence, we were unable to test on the same large instances considered for the basic setting due to the limitations of our hardware. In each table we report, for each network, the number of stops, the size of the corresponding red-te graph (wred-te graph, respectively) in terms of vertices and arcs, the time for preprocessing the network to compute the labelings L and SL (either 2 hc-r and stop labeling or 2 hc-sp and extended stop labeling, respectively). Finally, we report of both L and SL, in megabytes. In both cases we observe that d-ptl is able to update the labeling (either 2 hc-r or 2 hc-sp) and the (extended) stop labeling in a time that is always more than an order of magnitude smaller than that taken by the recomputation from scratch via ptl (up to more than 600 times smaller). This is true in both the basic and the multi-criteria cases. In this latter case, we notice that the newly proposed decremental algorithm dag-decpll is very effective, since it is tailored for DAGs, and is always faster than the general incremental algorithm incpll, which is designed to work for any graph. This is somehow a novel result with respect to Reference [21], where decpll is always by far slower than incpll, that might drive further investigation on updating 2 hc-sp labeling in general graphs. Furthermore, the experiments show that graphs and labelings updated via d-ptl and those recomputed from scratch via ptl are equivalent in terms of both query time and space overhead (cf Tables 6-9). In particular, both sizes and query times are very similar, as expected, thus suggesting that the use of d-ptl does not induce any degradation in the performance of the data structures. This is most likely due to the fact that d-ptl preserves by design the minimality of the labeling, an important property that has been shown to be tied to performance in labelings [20; 21; 26]. On top of that, a further \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{2}{c}{**(Basic) d-ptl} & \multicolumn{2}{c}{**(Basic)** ptl} & \\ \cline{3-6}
**Network** & \multicolumn{2}{c}{**Avg. Update Time**} & \multicolumn{2}{c}{**Avg. Reprocessing Time**} & \\  & \multicolumn{2}{c}{**(seconds)**} & \multicolumn{2}{c}{**(seconds)**} & \multicolumn{2}{c}{**Speed-up**} \\ \cline{2-6}  & \multicolumn{2}{c}{L} & SL & L & SL & \\ \hline London & 8.64 & 2.48 & 4417.65 & 5.50 & 397.77 \\ Madrid & 17.47 & 7.76 & 10,495.40 & 14.20 & 416.55 \\ Rome & 12.36 & 14.49 & 16,847.00 & 29.50 & 628.55 \\ Melbourne & 4.08 & 7.25 & 3807.00 & 11.50 & 337.03 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison between d-ptl and ptl in the basic setting, in terms of computational time. The first column shows the considered network while the 2 nd and the 3 rd columns show the average time taken by d-ptl to update the labeling and the stop labeling, respectively, after a delay occurs in the network. The 4 th and the 5 th columns show the average time taken by ptl to recompute from scratch the labeling and the stop labeling, respectively, after a delay occurs in the network. Finally, the 6 th column shows the speed-up, that is the ratio of the sum of the values in the 2 nd and the 3 rd columns to the sum of the values in the 4 th and the 5 th columns.