# Multimodal Dynamic Journey-Planning +
## 2 Preliminaries
### The Dynamic Timetable Model  
The _dynamic timetable model_ (DTM) is a new model introduced in [10], aiming at efficiently updating the timetable after a vehicle delay.  
Given a timetable \(\mathcal{T}=(\mathcal{H},\Phi,\mathcal{C})\), the directed graph \(G=(V,E)\) representing DTM is defined as follows:  
1. For each stop \(S\) in \(\Phi\), a _switch node_\(\sigma_{S}\) is added to \(V\), representing an arrival or start time event of any traveler at stop \(S\).
2. For each elementary connection \(c=(h,S_{d},S_{a},t_{d},t_{a})\in\mathcal{C}\), a _departure node_\(d_{c}\) (representing the time event \(t_{d}\)) is added to \(V\), and a _connection arc_\((d_{c},\sigma_{S_{a}})\), connecting \(d_{c}\) to the switch node \(\sigma_{S_{a}}\) of (the immediate next stop) \(S_{a}\), is added to \(E\).
3. For each elementary connection \(c=(h,S_{d},S_{a},t_{d},t_{a})\in\mathcal{C}\), a _switch arc_ arc \((\sigma_{S_{d}},d_{c})\), connecting the switch node \(\sigma_{S_{d}}\) of the departure stop \(S_{d}\) to the departure node \(d_{c}\) of \(c\) at \(S_{d}\), is added to \(E\).
4. For each vehicle \(h\in\mathcal{H}\) which travels through the itinerary \((c_{1},c_{2},\ldots,c_{k})\), an arc (_vehicle arc_), connecting the departure node \(d_{c_{i}}\) of \(c_{i}\) with the departure node \(d_{c_{i+1}}\) of \(c_{i+1}\), is added to \(E\), for each \(i=1,2,\ldots,k-1\).  
The timetable routes are periodic, with period \(T_{p}\) (typically \(T_{p}=1440=24\times 60\)). Any transfer and travel time is assumed to last less than \(T_{p}\). Given two time instances \(t_{1}\) and \(t_{2}\), such that \(t_{1}\leq t_{2}\), the (cyclic) time difference between them is denoted by \(\Delta(t_{1},t_{2})=t_{2}-t_{1}(\bmod\ T_{p})\).  
Every node and arc of \(G\) is associated with a time and weight, respectively. In particular, the associated (with nodes) time references \(t:V\to\mathbb{R}_{\geq 0}\) and the (arc) weight function \(w:E\to\mathbb{R}_{\geq 0}\) are defined as follows. The time-point \(t(v)\in[0,T_{p})\) of a departure node \(v\in V\) is fixed, and it denotes the scheduled departure time of the associated public transportation vehicle. The time-point \(t(v)\in[0,T_{p})\) of a switch node \(v\in V\) of stop \(S\in\Phi\) varies and represents any possible start or arrival time at the stop \(S\). The weight of each non-switch (i.e., connection and vehicle) arc \(e=(u,v)\in E\) is fixed and set to \(w(e)=\Delta(t(u),t(v))\). The weight of the rest (i.e., switch) arcs \(e\in E\) varies, and its default value is infinity.  
For each connection \(c=(h,S_{d},S_{a},t_{d},t_{a})\), the quantity \(t_{a}(d_{c})\) or \(t_{a}(c)\) denotes the arrival time \(t_{d}+w(d_{c},\sigma_{S_{a}})\) at stop \(S_{a}\), departing from \(S_{d}\) via the departure node \(d_{c}\), at time \(t(d_{c})=t_{d}\). For each stop, the departure nodes are ordered by their \(t_{a}(d_{c})\) values (arrival times at their arrival stop \(S_{a}\)). Moreover, for each switch node \(\sigma_{S}\), we store the stop \(S\) it is associated with, while for each departure node \(d_{c}\), we maintain both the departure time reference \(t_{d}(c)\) and the vehicle \(H(c)\) of connection \(c\) which \(d_{c}\) is associated with.  
Figure 1 shows a DTM graph. Departures of station \(A\), labeled 20 and 35, concern train connections, while the rest concern bus connections.