# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
``` Input: Graph \(G=(V,A)\), departure vertex \(v_{d}^{c_{j}}\), stop \(s_{s}\)
1 if\(\textsc{DV}[s]\setminus\{v_{d}^{c_{j}}\}\
eq\emptyset\)then
2\(m\gets argmax_{v\in\textsc{DV}[s]}\:time(v)\);
3 if\(time(v_{d}^{c_{j}})\geq time(m)\)then// Add waiting arc
4\(A\gets A\:\cup\{(m,v_{d}^{c_{j}})\}\);
5
6 else
7 Let \(m_{1},m_{2}\in\textsc{DV}[s]\) be such that \(time(m_{1})\leq time(v_{d}^{c_{j}})\leq time(m_{2})\);
8\(A\gets A\:\setminus\{(m_{1},m_{2})\}\); // Remove outdated waiting arc
9\(A\gets A\:\cup\{(m_{1},v_{d}^{c_{j}}),(v_{d}^{c_{j}},m_{2})\}\); // Add new waiting arcs```
Input: Graph \(G=(V,A)\), departure vertex \(v_{d}^{c_{j}}\), successor vertex \(\textsc{SUCC}\), stop \(s_{s}\)
1 if\(\textsc{SUCC}=\infty\)then// (Sub-case I.a)
2 candidates\(\leftarrow\emptyset\);
3 foreach\(v\in\textsc{Av}[s]\)do
4\(\textsc{to\_add}\leftarrow\textit{true}\);
5 foreach\(u\in N_{\textit{out}}(v)\)do// Outgoing transfer arcs (if any)
6 if\(u\in\textsc{dv}[s]\)then// Has transfer arc
7\(\textsc{to\_add}\leftarrow\textit{false}\);
8 break;
9 if\(\textsc{to\_add}\wedge\textit{time}(v_{d}^{c_{j}})\geq\textit{time}(v)+ \textsc{mt}_{s}\)then
10 candidates\(\leftarrow\textsc{candidates}\cup\{v\}\)
11 foreach\(v\in\textsc{candidates}\)do
12\(A\gets A\ \cup\{(v,v_{d}^{c_{j}})\}\)// (Sub-case I.b)
13 else// (Sub-case I.b)
14\(T\leftarrow\emptyset\);
15 foreach\(v\in\textsc{Av}[s]\)do// Outgoing transfer arcs (if any)
16 if\(u=\textsc{succ}\wedge\textit{time}(v_{d}^{c_{j}})\geq\textit{time}(v)+\textsc{mt} _{s}\)then
17\(T\gets T\cup\{(v,u)\}\);
18 foreach\((v,u)\in T\)do
19\(A\gets A\ \setminus\{(v,u)\}\);
20\(A\gets A\ \cup\{(v,v_{d}^{c_{j}})\}\);
```

**Algorithm 5**Algorithm RewireTransferDep. ```
Input: Graph \(G=(V,A)\), arrival vertex \(v_{d}^{c_{j}}\), trip \(\textsc{TRIP}_{i}\), stop \(s_{t}\)
1 min_NODE\(\leftarrow\)\(\underset{v\in\textsc{dv}[t]}{\textit{argmin}}\ \{time(v)\}\);
2\(A\gets A\cup\{(v_{d}^{c_{j}},\textsc{min\_node})\}\);// Add proper transfer arc
3 if\(j>0\)then// Not first connection of the trip
4\(A\gets A\cup\{(v_{d}^{c_{j-1}},v_{d}^{c_{j}})\}\);// Add bypass arc
5 if\(j<k\)then// Not last connection of the trip
6\(A\gets A\cup\{(v_{d}^{c_{j}},v_{d}^{c_{j+1}})\}\) ;// Add bypass arc
```

**Algorithm 6**Algorithm RewireArr. In the removal phase, we first remove from \(G\) vertices and arcs that are associated with the delayed connection that violate the red-te constraints. We say a vertex (arc, respectively) violates the red-te constraints whenever the associated time (the difference of the times of the endpoints, respectively) does not satisfy at least one of the inequalities imposed by the red-te model discussed in Section 2. Note that, vertices and arcs of the above kind can be: (i) departure and arrival vertices of the delayed connection; (ii) departure and arrival vertices following the delayed connection in the same trip; (iii) arcs adjacent to vertices in (i) and (ii). Once the above is done, we might have that \(G\) is no longer a red-te graph, since the removal of the above vertices and arcs can, in turn, induce some other vertex/arc to violate red-te constraints. Hence, we first reflect such removals onto L by running the decremental algorithm dec-bu of Reference [24] and then check if we need to insert into \(G\) some new arcs to let it be again a red-te graph. Accordingly, if this is the case, we add label entries induced by these insertions by using the incremental algorithm INC-bu of Reference [24]. At this point, the graph \(G\) is a red-te graph of a timetable that does not include the delayed connection. Then, if some changes has been applied to \(G\) (and \(L\)) in the above step, we proceed by analyzing the connections following the delayed one in the same trip, one by one, and by removing vertices and arcs that violate the red-te graph. At the end of these iterations, we have that \(G\) is a red-te graph of a timetable that does not include neither the delayed connection nor those following it in the same trip that have violated the red-te constraints because of \(\delta\).