# Multimodal Dynamic Journey-Planning +
## 3 The Multimodal Dynamic Timetable Model
### Query Algorithm
During the algorithm execution, provided that the traveler is already at \(S_{o}\) at time \(t_{s}\) the minimum transfer time of \(S_{o}\) is set to \(transfer(S_{o})=0\). IterationAt each step, a switch node \(\sigma_{S_{x}}\) is extracted from the priority queue. The node \(\sigma_{S_{x}}\) is settled, having got the earliest arrival time for the optimal journey departing from \(S_{o}\) at time \(t_{s}\) and arriving to \(\sigma_{S_{x}}\) at time \(t(\sigma_{S_{x}})=dist[\sigma_{S_{x}}](\text{mod }T_{p})\). Then, the algorithm relaxes the outgoing arcs of \(\sigma_{S_{x}}\) following a node filtering and blocking process:  
1. Using the existing grouping of departure nodes (\(\Gamma_{1}\) and \(\Gamma_{2}\)), the departure node groups corresponding to non-selected transportation modes are skipped. 2. Using the earliest arrival index tables, the algorithm can skip the departure nodes of stop \(S_{x}\) that have an earlier than \(dist[\sigma_{S_{x}}]\) departure time, or they provide non-optimal arrival times to the next adjacent stops. In particular, after \(\sigma_{S_{x}}\) is extracted, then for each adjacent arrival stop \(S_{a}\) of stop \(S_{x}\) and for each enabled transport mode \(M\in M_{choices}\): 1. A binary search is performed on the index table \(I_{S_{x}}(S_{a},M)\) for getting the first departure node \(d_{r}\) with \(t(d_{r})>t(\sigma_{S_{x}})\) that provides the earliest arrival time at stop \(S_{a}\). 2. An arc relaxation step is performed based on those departure nodes. Let the sequence of the outgoing switch arcs of \(\sigma_{S_{x}}\) be \(e_{1},e_{2},...,e_{r-1},e_{r},...,e_{k}\), which corresponds to travel using the transport mode \(M\) and arriving at the stop \(S_{a}\). Let \(e_{i}=(\sigma_{S_{x}},d_{i})\), \(i=1,...k\), and let the node \(d_{r}\) be the departure node that is returned by \(I_{S_{x}}(S_{a},M)\). Within the current time period \(T_{p}\), arcs \(e_{1},e_{2},...,e_{r-1}\) can be safely skipped, because they provide earlier departures or non-optimal arrival paths from \(S_{x}\) to \(S_{a}\). The first arc that is relaxed is \(e_{r}\). Provided that the next switch arcs and their departure node heads are ordered by arrival time, the algorithm relaxes the arcs \(e_{r},...,e_{k},e_{1},...,e_{r-1}\) (relaxation of arcs after \(e_{k}\) might be required, since the journey may continue on the next day) and it stops as soon as it falls over a departure node \(d_{i}\) with (a) \(\Delta(t(\sigma_{S_{x}}),t(d_{i}))>transfer(S_{x})\) and (b) \(dist[d_{i}]+w(d_{i},\sigma_{S_{a}})>dist[\sigma_{S_{a}}]+transfer(S_{a})\). The first condition ensures the minimum transfer time for the traveler in using a different vehicle to continue his/her travel. The second condition ensures that we will not miss optimal paths in \(S_{a}\) with no transfer. In all cases, if the departure node head \(d_{i}\) of the switch arc \(e_{i}\) is visited for the first time, or it has a greater distance assigned during a previous step, then we set \(dist[d_{i}]=dist[\sigma_{S_{x}}]+\Delta(t(\sigma_{S_{x}}),t(d_{i}))\) and \(w(\sigma_{S_{x}},d_{i})=dist[d_{i}]-dist[\sigma_{S_{x}}]\). When the distance is updated, the algorithm also relaxes the outgoing arcs of the departure node \(d_{i}\). For its outgoing arc \((d_{i},\sigma_{S_{x}})\), if \(\sigma_{S_{x}}\) is visited for the first time or it has, from a previous step, a greater distance, then we set \(dist[\sigma_{S_{a}}]=dist[d_{i}]+w(d_{i},\sigma_{S_{a}})\). If there is also a vehicle (departure-departure) arc \((d_{i},d_{j})\), then for the associated vehicle we also relax the outgoing arcs of the departure nodes \(d_{j},...,d_{i}\) at the next stops at which the vehicle passes along the same route. In that case, we can stop if we fall over a departure which has an outgoing arc to a switch node which has not yet been visited or extracted from the priority queue. The algorithm finishes when the switch node \(\sigma_{S_{T}}\) of the destination stop \(S_{T}\) is settled.