# Multimodal Dynamic Journey-Planning +
## 3 The Multimodal Dynamic Timetable Model
### Query Algorithm  
We shall now present our query algorithm, named MDTM-QH, for solving EAP on a MDTM graph, \(G\). An EA query \((S,T,t_{s},M_{Choices})\) is answered by executing a modified [PERSON]'s algorithm on \(G\), starting from the switch node \(\sigma_{S}\) of stop \(S\). Before discussing the details of our algorithm, we first describe the additional data structures used by MDTM-QH with respect to the classic [PERSON]'s algorithm. In particular, for each switch node of a stop, algorithm MDTM-QH maintains a set of _earliest arrival index tables_, whose construction and contents are described below. Each departure node \(d\) is associated with a departure time \(t_{d}(d)\) and an arrival time \(t_{a}(d)\). In general, all the departure nodes with the same departure stop \(S_{d}\) can be ordered either by departure time or arrival time at an arrival stop. The first ordering favors an efficient search on the departure nodes to get the valid routes which have a valid departure time, i.e., a departure time greater than or equal to \(t(\sigma_{S_{d}})\) at which time the traveler is at \(S_{d}\). The second ordering favors an efficient search on the departure nodes on the optimal routes which provide the earliest arrival times to their adjacent stops. The second ordering is already applied within the existing (\(\Gamma_{1}\) and \(\Gamma_{2}\)) departure groups of \(G\). However, we would also like to have the advantage of the first ordering. Therefore, for the purpose of effectively searching the departure nodes that both have valid departure times from stop \(S_{d}\) and earliest arrival times to an adjacent arrival stop \(S_{a}\), we introduce the _earliest arrival index_ tables. Let \(I_{S_{d}}(S_{a},M)\) denote an _earliest arrival index_ table, consisting of departure nodes with departure stop \(S_{d}\), arrival stop \(S_{a}\), and transport mode \(M\). \(I_{S_{d}}(S_{a},M)\) is constructed as follows: Let \(d_{1},d_{2},...,d_{k}\in D_{S_{d}}(S_{a},M)\) be the sequence of the departure nodes, ordered by arrival time at \(S_{a}\), for a trip departing from stop \(S_{d}\) and arriving at stop \(S_{a}\) with transport mode \(M\). Initially, \(I_{S_{d}}(S_{a},M)\) is empty. Node \(d_{1}\) is inserted in \(I_{S_{d}}(S_{a},M)\) and \(t_{max}=t(d_{1})\) is the current max departure time. Afterwards, for \(i=2,...,k\), if \(t_{max}<t(d_{i})\), then \(t_{max}=t(d_{i})\) and \(d_{i}\) is inserted at the end of the \(I_{S_{d}}(S_{a},M)\) table; otherwise, \(d_{i}\) is skipped. If the table contains the departure nodes \(v_{1},...,v_{l}\), \(l\leq k\), and for some \(i\), \(t(\sigma_{S_{d}})\in[t(v_{i}),t(v_{i+1}))\), then \(v_{i}\) is the first departure node to start the search of the earliest arrival time at \(S_{a}\). This allows us to bypass the departure nodes, before \(v_{i}\) in the arrival ordered sequence, with departure times less than \(t(v_{i})\). Table 1 shows the contents of table \(I_{S_{A}}(S_{B},M=\{bus,train\})\), for the example shown in Figure 2. If a traveler has arrived or has started their journey from stop \(S_{A}\) at time \(t(s_{A})=25>20\), then to continue at the adjacent stop \(S_{B}\), the search of valid and optimal path-solutions can start after the departure node 20. Figure 2: The MDTM graph corresponding to the DTM graph of Figure 1. Departure nodes grouping: light blue (brown) are train (bus) connections. The switch–switch arc (dotted black) introduces an unrestricted departure connection between the stops. To reduce the size and the operations in the priority queue of the query algorithm, we inserted in it only the switch nodes and changed the arc relaxation as described below (iteration step). The MDTM-QH algorithm works as follows. InitializationThe switch node \(\sigma_{S_{a}}\) of the origin stop \(S_{o}\) is inserted in the priority queue, with distance \(dist[\sigma_{S_{a}}]=t_{s}\) and time \(t(\sigma_{S_{a}})=t_{s}\).