# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
In the remainder of the paper, for the sake of brevity, we denote this test by writing either \"the graph has changed\" or not. ### Insertion Phase

In this section, we discuss in details Algorithm ins-d-ptl whose aim is adding to \(G\) vertices and arcs according to the delayed connection in such a way \(G\) is a red-te graph properly representing the updated timetable, and then to update accordingly l (see Algorithm 2). In particular, once Algorithm 1 has been executed, the following four cases can occur, for each connection \(c_{j}\), \(j=m\) to \(k\) in trip trip\({}_{i}=(c_{0},c_{1},\ldots,c_{m},\ldots,c_{k})\) that has been affected by the delay, depending on whether the vertices associated have been removed or not from the graph:

1. \(v_{d}^{c_{j}}\in V\) and \(v_{u}^{c_{j}}\in V\);
2. \(v_{d}^{c_{j}}\
otin V\) and \(v_{u}^{c_{j}}\
otin V\);
3. \(v_{d}^{c_{j}}\
otin V\) and \(v_{u}^{c_{j}}\in V\);
4. \(v_{d}^{c_{j}}\in V\) and \(v_{u}^{c_{j}}\
otin V\). In what follows we describe in detail how Algorithm ins-d-ptl manage each of these cases. #### 5.2.1 Discussion on Case I

In this case, when both vertices have remained in \(G\) (see Line 9 of Algorithm 2), we only check whether some transfer arcs have to be updated. This process is summarized in Algorithm 5 which is called as sub-routine by Algorithm 2. In particular, if \(v_{d}^{c_{j}}\) is the last vertex in \(\textsc{dv}[s]\) (see Line 2 of Algorithm 5--Sub-case Ia), i.e., there is no waiting arc outgoing \(v_{d}^{c_{j}}\) then we compute the subset candidates of vertices in \(\textsc{av}[s]\) that do not have any adjacent transfer arc and would not violate the red-te constraints, i.e., we add a vertex \(v\in\textsc{av}[s]\) to candidates if and only if \(time(v_{d}^{c_{j}})\geq time(v)+\textsc{mtt}_{s}\) and \(v\) does not have any adjacent transfer arc. Then, for each vertex \(v\in\textsc{candidates}\) we add a new arc \((v,v_{d}^{c_{j}})\) to \(A\). Figure 2: The red-te graph obtained after performing Algorithm rem-d-ptl (Algorithm 1) on the graph of Figure 1, as a consequence of a delay \(\delta\) of 10 min occurring on the first connection of Trip \(b\). The time associated to the departure vertex (filled in orange) of said connection is updated, but the vertex and its corresponding transfer arc (drawn in orange) are not removed, since the ordering and the red-te properties are not broken. Arrival and departure vertices of the connections following the one affected by the delay in the same trip are filled in red. Since they break the red-te properties (e.g., 35 becomes larger than 30 in Stop \(\gamma\)) they are removed from the graph, along with the corresponding adjacent arcs, shown via dashed red arrows. A waiting arc, in blue, is added during the removal phase to connect departure vertices that remain in \(\textsc{dv}[Y]\) to restore the red-te properties. If, instead, \(v_{d}^{c_{j}}\) is not the last vertex in \(\textsc{dv}[s]\) (see Line 14 of Algorithm 5--Sub-case I.b), i.e., there exists some waiting arc connecting \(v_{d}^{c_{j}}\) to a vertex \(\textsc{succ}\in\textsc{dv}[s]\), then some of the transfer arcs having \(\textsc{succ}\) as endpoint in \(G\) may need to be updated and connected to \(v_{d}^{c_{j}}\) (i.e., _rewired_ to \(v_{d}^{c_{j}}\)). To this purpose, we first determine the subset \(TA\) of transfer arcs in \(A\) having \(w\) as endpoint and then, for each arc \((v,w)\) in \(TA\), if \(time(v_{d}^{c_{j}})\geq time(v)+\textsc{mtt}_{s}\) we replace arc \((v,w)\) by a new arc \((v,v_{d}^{c_{j}})\). Notice that, for replaced transfer arcs we do not need to update L, since any two vertices that were reachable before such update remain reachable afterward. Moreover, also vertices in \(\textsc{dv}[s]\) remain in ordered form, therefore we do not need to add/replace any waiting arc of \(A\). On the contrary, if some modification has been applied to the topology of \(G\) or to the ordering of the vertices, then we run \(\textsc{inc-bu}\) to obtain an updated version of the 2 hc-r labeling (see Line 11).