# Multimodal Dynamic Journey-Planning +
## 3 The Multimodal Dynamic Timetable Model
### The Profile Query Algorithm  
Let \((S,T,D,M)\) be a profile query, where we need to compute all Pareto-optimal journeys from \(S\) to \(T\), given a departure time interval \(D=[dstart,dend]\), departing from \(S\) within the time interval \(D\) and arriving at \(T\), using any chosen transport mode, including walking (with free departure) or/and public transit (with non-free departures/arrivals). The domination rule is in relation to the earliest arrival time and latest departure time. The output solution is a set of departing time subintervals and their corresponding \(S\to T\) journeys that provide the minimum travel time.  
Our algorithm, called PrMDTM-QH-ALT, consists of two phases.  
In the first phase, the shortest path tree \(R_{W}\) from \(S\), using the slowest transport mode, i.e., walking, is computed. To achieve this, we run the MDTM-QH-ALT algorithm with root \(S\) and destination \(T\), using only walking, skipping any boarding, and stopping when all switch nodes \(\sigma\) with \(dist_{W}(\sigma_{S},\sigma)+\pi_{\sigma_{T}}(\sigma)\leq dist_{W}(\sigma_{S}, \sigma_{T})\) are explored and settled, where \(dist_{W}\) denotes the walking distance metric, and \(\pi_{\sigma_{T}}(\sigma)\leq dist_{W}(\sigma,\sigma_{T})\). Let \(J\in R_{W}\cap\Phi\) be the set of the candidate shortest path stops for the requested profile query.  
In the second phase, the size of \(J\) is being considered. If \(J\) is empty, it means that there is no candidate stop for any departure time-point, and thus the shortest path by walk in the computed \(R_{W}\) is the dominated solution in \(D\). Otherwise, the \(S\to T\) shortest journeys may include at least one of the candidate stops in \(J\). Starting with departure time \(t=dstart\), the MDTM-QH-ALT algorithm is executed, having the following preceding initialization step: the distances of the nodes \(v\in R_{W}\) are updated with respect to the departure time \(t\), obtaining the corresponding arrival times. Those nodes \(v\in R_{W}\) are marked as already visited by the algorithm, and each candidate stop node in \(J\) is inserted into the priority queue.  
The iteration steps of the algorithm are as follows. If the computed shortest journey from \(S\) at \(t\) towards \(T\) has at least one boarding, then a public transit itinerary has been used. Let \(arr_{t}\) be the earliest arrival time computed. In order to determine the latest departure \(t_{next}=v+t\geq t\), \(v\geq 0\), that the traveler can reach \(T\) at the earliest arrival time \(arr_{t}\), a backward query algorithm has to be performed [19]. Specifically, the latest departure time at \(S\) is computed by running a backward MDTM-QH-ALT algorithm, where the root is \(T\), the incoming arcs of each settled node are traversed, and the stopping condition is the settlement of \(S\). The computed journey \(p_{ea}(arr_{t})\) provides a fixed minimum arrival time \(a_{min}\) in \([d_{start},d_{start}+v]\), with \(v\) being the maximum waiting time in \(S\) departing at \(d_{start}\) and the waiting time in \(S\) becoming zero if the departing time is at \(d_{start}+v\). Subsequently, we continue in the remaining interval \([d_{start}+v+e,d_{end}]\), where \(e>0\) denotes that the traveler cannot use the previously computed \(p_{ea}(a_{min})\) path because it is invalid--that is, at least one boarding is past, and thus the next reachable boardings in \([d_{start}+v+e,d_{end}]\) need to be found. The next departure time-point \(t\) is set to \(d_{start}+v+e\), and the process is repeated until \(t\) reaches the last time-point, \(dend\). Finally, any computed journeys having travel times greater than \(dist_{W}(S,T)\) are discarded and replaced by the first-phase-computed shortest \(S\to T\) path by walking.