# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 7 Experimental Study
### Experimental Setup
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{2}{c}{**(Multi-Criteria) d-ptl**} & \multicolumn{2}{c}{**(Multi-Criteria) ptl**} & \\ \cline{3-6}  & \multicolumn{2}{c}{**Avg. Update Time**} & \multicolumn{2}{c}{**Avg. Reprocessing Time**} & \\ \cline{3-6}
**Network** & \multicolumn{2}{c}{**(seconds)**} & \multicolumn{2}{c}{**(seconds)**} & \multicolumn{2}{c}{**Speed-up**} \\ \cline{2-6}  & \multicolumn{2}{c}{**L**} & \multicolumn{2}{c}{**e-sl**} & \multicolumn{2}{c}{**L**} & \multicolumn{2}{c}{**e-sl**} & \\ \cline{2-6}  & \multicolumn{2}{c}{**incpll**} & \multicolumn{2}{c}{**DAG-decpll**} & & \\ \hline Palermo & 210.37 & 135.86 & 3.01 & 7807.14 & 3.39 & 22.36 \\ Barcelona & 25.19 & 2.50 & 5.65 & 14,156.90 & 7.62 & 424.85 \\ Luxembourg & 617.44 & 348.92 & 6.57 & 43,275.70 & 11.50 & 44.49 \\ Venice & 167.67 & 3.10 & 3.50 & 19,146.60 & 5.69 & 109.90 \\ Prague & 597.93 & 22.92 & 10.16 & 29,435.90 & 20.84 & 40.86 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparison between d-ptl in the multi-criteria setting, in terms of computational time. The first column shows the considered network while the 2 nd, the 3 rd, and the 4 th columns show the average time taken by d-ptl to update the labeling and the extended stop labeling, respectively, after a delay occurs in the network. The time taken to update the labeling, in this case, is divided in two fields to highlight which of the two components of d-ptl is more time consuming. The 5 th and the 6 th columns show the average time taken by ptl to update the wred-te graph and recompute from scratch the labeling and the extended stop labeling, respectively, after a delay occurs in the network. Finally, the 7 th column shows the speed-up, that is the ratio of the sum of the values in the 2 nd, 3 rd and 4 th columns to the sum of the values in the 5 th and the 6 th columns. consideration that can be done by analyzing the data in Table 8 is that the newly proposed extended stop labeling is at least as effective as the original stop labeling in accelerating the query algorithm and reducing the corresponding query time in the multi-criteria case (see Reference [13] for a detailed comparison with the reduction provided by the original stop labeling). To summarize, all the above observations and data give a strong evidence of the following facts:  
* d-ptl is a very effective and practical option for journey planning when dynamic, delay-prone networks have to be handled, especially when they are of very large size and yet require fast query answering;
* dag-decpll is a prominent solution to update 2 hc-sp labelings in DAGs, faster than algorithm decpll, which is designed for general graphs;
* the newly proposed extended stop labeling is an effective compact version of the data structures used by ptl in the multi-criteria case that allows a significant reduction in the average query time. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & \multicolumn{2}{c}{**(Basic) d-ptl} & \multicolumn{2}{c}{**(Basic) ptl**} \\
**Network** & \multicolumn{2}{c}{**Avg. Query Time**} & \multicolumn{2}{c}{**Avg. Query Time**} \\  & \multicolumn{2}{c}{**(milli-seconds)**} & \multicolumn{2}{c}{**(milli-seconds)**} \\ \cline{2-4}  & **eaq** & **PQ** & **eaq** & **PQ** \\ \hline London & 0.01 & 0.10 & 0.01 & 0.14 \\ Madrid & 0.03 & 0.35 & 0.03 & 0.34 \\ Rome & 0.04 & 0.18 & 0.04 & 0.19 \\ Melbourne & 0.05 & 0.26 & 0.06 & 0.27 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Comparison between d-ptl and ptl in the basic setting, in terms of query time. The first column shows the considered network. The 2 nd and 4 th columns (3 rd and 5 th, respectively) show the average computational time for performing an earliest arrival (profile, respectively) query. In particular, columns 2 nd and 3 rd refer to average query times obtained from the labelings updated via d-ptl, while columns 4 th and 5 th refer to those obtained from the labelings recomputed from scratch via ptl.