# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
#### 5.2.2 Discussion on Case II

In this case, occurring when both vertices have been removed from \(V\) (see Line 13), we know that the affected connection has no counterpart in \(G\) in terms of departure and arrival vertices. Thus, to make \(G\) reflect the updated network as a correct red-te model, we proceed as follows. First, we add a vertex \(v_{d}^{c_{j}}\) to \(V\) and to \(\textsc{dv}[s]\) and set its associated time to be equal to the new departure time of the (delayed) connection. After that, we add arcs adjacent to \(v_{d}^{c_{j}}\), depending on the presence of other vertices in \(\textsc{dv}[s]\) and \(\textsc{av}[s]\) and on their times. In particular, if \(time(v_{d}^{c_{j}})\geq time(v)\)\(\forall\)\(v\in\textsc{dv}[s]\) and \(\textsc{dv}[s]\setminus\{v_{d}^{c_{j}}\}\
eq\emptyset\), i.e., there is no waiting arc outgoing vertex \(m=argmax_{v\in\textsc{dv}[s]}time(v)\) and there exists another departure vertex besides \(v_{d}^{c_{j}}\) in \(\textsc{dv}[s]\), we need to add a waiting arc incoming into \(v_{d}^{c_{j}}\), in particular we insert arc \((m,v_{d}^{c_{j}})\) into \(A\). On the other hand, if there exist some vertices \(m_{1},m_{2}\in\textsc{dv}[s]\) such that \(time(m_{1})\leq time(v_{d}^{c_{j}})\leq time(m_{2})\), then we remove waiting arc \((m_{1},m_{2})\) and add two new waiting arcs \((m_{1},v_{d}^{c_{j}})\) and \((v_{d}^{c_{j}},m_{2})\) to \(A\). It is worth to remark here that \(v_{d}^{c_{j}}\) cannot be such that \(time(v_{d}^{c_{j}})<time(v)\)\(\forall\)\(v\in\textsc{dv}[s]\) since otherwise the original vertex \(v_{d}^{c_{j}}\) would have not been removed by Algorithm 1. The pseudo-code of this part of the insertion phase is shown in Algorithm 4 which is again executed as sub-routine of Algorithm 2. Regarding transfer arcs, after \(v_{d}^{c_{j}}\) is inserted we execute Algorithm 5, as already discussed for case I. Finally, we run \(\textsc{inc-bu}\) to update the 2 hc-r labeling L (see Line 17). Once vertex \(v_{d}^{c_{j}}\) has been handled, we focus on the arrival stop \(s_{t}\) and insert a vertex \(v_{a}^{c_{j}}\) into \(V\) and \(\textsc{av}[t]\), and a connection arc \((v_{d}^{c_{j}},v_{a}^{c_{j}})\) to \(A\). Then, to properly set transfer arcs induced by such connection arc, we search for the vertex \(v\) in \(\textsc{dv}[t]\) such that: (i) \(time(v)\geq time(v_{a}^{c_{j}})+\delta\) and (ii) \(time(v)\) is minimum among vertices satisfying (i). If such a vertex \(v\) exists, then we add arc \((v_{a}^{c_{j}},v)\) to \(A\). Moreover, to properly set bypass arcs, if \(j\geq 1\) we add an arc \((v_{a}^{c_{j-1}},v_{a}^{c_{j}})\), where we remark that \(v_{a}^{c_{j-1}}\) is the arrival vertex of connection \(c_{j-1}\) of \(\textsc{trip}_{i}\). Similarly, \(j\leq k-1\) we add an arc \((v_{a}^{c_{j}},c_{j+1})\) where \(v_{a}^{c_{j+1}}\) is the arrival vertex of connection \(c_{j+1}\) of \(\textsc{trip}_{i}\) (see Algorithm 6 for the pseudo-code of this phase). Again, we run \(\textsc{inc-bu}\) to update L (see Line 20). #### 5.2.3 Discussion on Case III

In this case, when \(v_{d}^{c_{j}}\) has been removed while \(v_{a}^{c_{j}}\) is in \(V\) (see Line 21 of Algorithm 2), we first add a vertex \(v_{d}^{c_{j}}\) to \(V\) and to \(\textsc{dv}[s]\) and a connection arc \((v_{d}^{c_{j}},v_{a}^{c_{j}})\) to \(A\). This is followed by the wiring of suited transfer and waiting arcs to \(v_{d}^{c_{j}}\), in order to preserve the red-te properties. As in the previous cases, this is achieved by Algorithms 4 and 5, discussed above. Algorithm \(\textsc{inc-bu}\) is also run to reflect changes on the 2 hc-r labeling (see Line 26). #### 5.2.4 Discussion on Case IV

In this case, occurring when \(v_{d}^{c_{j}}\) is part of \(V\) while \(v_{a}^{c_{j}}\) has been removed by the removal phase (see Line 27), we insert a vertex \(v_{a}^{c_{j}}\) into \(V\) and \(\textsc{av}[t]\), and the corresponding connection arc \((v_{d}^{c_{j}},v_{a}^{c_{j}})\) into \(A\). This is followed by the addition of bypass and transfer arcs adjacent to \(v_{a}^{c_{j}}\), achieved again by Algorithm 6.