# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
If \(v\) is the vertex under consideration then, for each \((h,\delta_{nv})\in\textsc{l}_{in}(v)\), we add \((h,stoptime_{i}(h)=time(v),transf_{i}(h)=\delta_{nv})\) to \(\textsc{e-sl}_{in}(i)\) only if one of the following conditions hold:

1. there is no entry \((h,stoptime_{i}(h),transf_{i}(h))\) in \(\textsc{e-sl}_{in}(i)\);
2. there exists an entry \((h,stoptime_{i}(h),transf_{i}(h))\) in \(\textsc{e-sl}_{in}(i)\) but \(\delta_{nv}<\textsc{mt}\) where \[\textsc{mt}=\min_{(h,stoptime_{i}(h),transf_{i}(h))\in\textsc{e-sl}_{in}(i)} transfers_{i}(h).\]

Note that the above second conditions are necessary since, differently from the original stop labeling, here a generic hub \(h\) can be added more than once to \(\textsc{e-sl}_{in}(i)\) or \(\textsc{e-sl}_{in}(i)\), since we might have more paths toward \(h\) (or from \(h\)) having different number of transfers. Notice that, for the sake of efficiency, we sort entries in \(\textsc{E-SL}_{out}(i)\) and \(\textsc{E-SL}_{in}(i)\) with respect to the first, second and third fields, in this order, similarly to what is done in Reference [13] for the stop labeling. The detailed procedure for computing the extended stop labeling is shown in Algorithm 10. ```
Input: wred-te graph \(G\), 2 hc-sp labeling \(\textsc{L}\) of \(G\) Output: Extended stop labeling \(\textsc{E-sl}\)
1 foreach\(s_{i}\in\textsc{S}\)do
2\(\textsc{E-SL}_{in}(i)\leftarrow\emptyset\);
3\(\textsc{E-SL}_{out}(i)\leftarrow\emptyset\);
4 foreach\(v\in V\)do
5\(Visit[v]=0\);
6\(MT[v]=\infty\);
7 foreach\(v\in\textsc{AV}[i]\) in increasing order of arrival timedo
8 foreach\((h,\delta_{hv})\in\textsc{L}_{in}(v)\)do
9 if\(Visit[v]=0\)then
10\(\textsc{E-SL}_{in}(i)\leftarrow\textsc{E-SL}_{in}(i)\cup\{(h,time(v),\delta_{ hv})\}\);
11\(MT[v]\leftarrow\delta_{hv}\);
12\(Visit[v]\gets 1\);
13
14 elseif\(MT[v]>\delta_{hv}\)then
15\(\textsc{E-SL}_{in}(i)\leftarrow\textsc{E-SL}_{in}(i)\cup\{(h,time(v),\delta_{ hv})\}\);
16\(MT[v]\leftarrow\delta_{hv}\);
17
18 Sort \(\textsc{E-SL}_{in}(i)\) with respect to. first, second and third field in each label entry;
19 foreach\(v\in V\)do
20\(Visit[v]=0\);
21\(MT[v]=\infty\);
22
23 foreach\(v\in\textsc{dv}[i]\) in decreasing order of departure timedo
24 foreach\((h,\delta_{vh})\in\textsc{L}_{out}(v)\)do
25 if\(Visit[v]=0\)then
26\(\textsc{E-SL}_{out}(i)\leftarrow\textsc{E-SL}_{out}(i)\cup\{(h,time(v),\delta_{ hv})\}\);
27\(MT[v]\leftarrow\delta_{vh}\);
28\(Visit[v]\gets 1\);
29
30 elseif\(MT[v]>\delta_{vh}\)then
31\(\textsc{E-SL}_{out}(i)\leftarrow\textsc{E-SL}_{out}(i)\cup\{(h,time(v),\delta_{ vh})\}\);
32\(MT[v]\leftarrow\delta_{hv}\);
33
34 Sort \(\textsc{E-SL}_{in}(i)\) with respect to. first, second and third field in each label entry;
35 return\(\textsc{E-sl}\);
```
**Algorithm 10**Algorithm e-sl Computation. ### Answering to Multi-criteria Queries via Extended Stop Labeling

For answering a multi-criteria query \(\textsc{mc-ea}(s_{i},s_{j},\tau)\) via extended stop labeling, we proceed as follows. Note that \(\textsc{E-SL}_{out}(i)\) and \(\textsc{E-SL}_{in}(j)\) are arrays sorted with respect to ids, the algorithm as a first step finds the vertex \(v\) in \(\textsc{E-SL}_{out}(i)\) (\(\textsc{E-SL}_{in}(j)\), respectively) whose time is greater than or equal to \(\tau\). Assume that said vertex is in position \(p\) (\(q\), respectively) in such arrays. Then, a linear sweep, starting from location \(p\), is performed on \(\textsc{SL}_{out}(i)\) to find the first entry \((v,stoptime_{i}(v),transfers_{i}(v))\) satisfying the condition that \(stoptime_{i}(v)\geq\tau\). Let us assume this entry is stored in location \(p^{\prime}\geq p\). This part of the computation is known as the process of computing _relevant hubs_ and it is followed by the computation of all hubs that are both \(\textsc{E-SL}_{out}(i)\) and \(\textsc{E-SL}_{in}(j)\), storedat locations greater than \(p^{\prime}\) and \(q\) in \(\textsc{e-sl}_{out}(i)\) and \(\textsc{e-sl}_{in}(j)\), respectively.