# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 8 Conclusions  
In this paper we have studied the journey planning problem in the context transit networks, with a specific focus on tolerance to disruptions and scalability. The problem asks to answer to various types of queries, seeking journeys exhibiting optimality with respect to. different metrics, on suitable data structures representing _timetables_ of _schedule-based transportation system_ (consisting of buses, trains, and trains, for example). We have analyzed the state-of-the-art solution, in terms of query time, for this problem, that is _Public Transit Labeling_ (ptl). We have attacked what can be considered the main limitation of this preprocessing-based approach, that is not being natively designed to tolerate updates in the schedule, which are instead very frequent in real-world applications. We have hence introduced a new framework, called d-ptl, that extends ptl to function under delays. In particular, we have provided a new algorithm able to update the employed data structures efficiently whenever a delay affects the network, without performing any recomputation from scratch. We have demonstrated the effectiveness of our new solution through an extensive experimental evaluation conducted on real-world networks. Our experiments show that the time required by the new algorithm is, on average, always at least an order of magnitude smaller than that required by the recomputation from scratch, in \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{2}{c}{**(Multi-criteria)** d-ptl} & \multicolumn{2}{c}{**(Multi-criteria)** ptl} \\ \multirow{2}{*}{**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-5}  & **mc-ea** & **mc-ea** & **with** e-sl** & **mc-ea** & **mc-ea** & **with** e-sl** \\ \hline Palermo & 1.25 & 0.52 & 1.25 & 0.53 \\ Barcelona & 0.09 & 0.01 & 0.08 & 0.01 \\ Luxembourg & 2.64 & 1.10 & 2.66 & 1.10 \\ Venice & 0.81 & 0.06 & 0.76 & 0.06 \\ Prague & 2.93 & 0.03 & 3.54 & 0.35 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Comparison between d-ptl and ptl in the multi-criteria setting, in terms of query time. The first column shows the considered network. The 2 nd and the 4 th (3 rd and 5 th, respectively) columns show the average computational time for performing a multi-criteria query by the two approaches without (with, respectively) extended stop labelings. 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 labeling recomputed from scratch, respectively. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{3}{*}{**Network**} & \multicolumn{2}{c}{**(Multi-Criteria)** d-ptl} & \multicolumn{2}{c}{**(Multi-Criteria)** ptl} \\ \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{**Avg. Space**} & \multicolumn{2}{c}{**Avg. Space**} \\  & \multicolumn{2}{c}{**(MB)**} & \multicolumn{2}{c}{**(MB)**} \\ \cline{2-5}  & \multicolumn{1}{c}{l} & \multicolumn{1}{c}{e-sl} & \multicolumn{1}{c}{l} & \multicolumn{1}{c}{e-sl} \\ \hline Palermo & 4764 & 372 & 4737 & 373 \\ Barcelona & 4253 & 360 & 4219 & 360 \\ Luxembourg & 30,557 & 1129 & 30,519 & 1126 \\ Venice & 7443 & 190 & 7413 & 190 \\ Prague & 4250 & 694 & 4251 & 695 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Comparison between d-ptl in the multi-criteria setting, in terms of space overhead. The first column shows the considered network. The 2 nd and the 3 rd columns show the average size of the 2 hc-sp labeling and the extended stop labeling, respectively, when updated via d-ptl, while the 4 th and the 5 th columns show the average size of the 2 hc-sp labeling and the extended stop labeling, respectively, when recomputed from scratch.