# Multimodal Dynamic Journey-Planning +
## 2 Preliminaries
### Multimodal Journey  
A _multimodal transport network_ consists of schedule-based public transport along with road and pedestrian path networks, for supporting traveling with both unrestricted departure (e.g., for walking, cycling, and driving) and restricted departure (for embarking on public transport vehicles that follow scheduled timetables). In contrast to a restricted-departure timetable elementary connection, an unrestricted-departure connection \((\sigma_{S_{A}},\sigma_{S_{B}})\) is defined as an arc representing a time-independent traveling path from stop \(S_{A}\) to stop \(S_{B}\).  
A _multimodal itinerary_ is a sequence of trip-paths consisting of unrestricted and restricted-departure connections \(P=(c_{1},c_{2},\ldots,c_{k})\) such that, for each \(i=2,3,\ldots,k\), \(S_{a}(c_{i-1})=S_{d}(c_{i})\) and  
\[\Delta(t_{a}(c_{i-1}),t_{d}(c_{i}))\geq\left\{\begin{array}{ll}0&\text{if }H(c_{i-1})=H(c_{i})\\ transfer(S_{a}(c_{i-1}))&\text{otherwise.}\end{array}\right.\]  
A _multimodal journey query_ is defined by a tuple \((S,T,t_{o},M)\) where \(S\in\Phi\) is a departure stop, \(T\in\Phi\) is an arrival stop, \(t_{o}\) is a minimum departure time from \(S\), and \(M\) represents the desired transport mode(s).  
There are two natural optimization criteria used to answer a timetable query. They consist in finding a multimodal itinerary from \(S\) to \(T\) starting (from \(S\)) at a time after \(t_{o}\) and arriving at \(T\), either with the minimum possible arrival time (_Earliest Arrival--EA_), or with the minimum number of vehicle transfers (_Minimum Number of Transfers--MNT_).  
These two criteria define the following core optimization problems:  
Figure 1: A DTM graph. Switch nodes are drawn in blue. Departure nodes (yellow) are associated with the departure time of their corresponding elementary connection, and are ordered by arrival time at the (arrival) station. Switch arcs are drawn in brown, while vehicle arcs are drawn in green.  
1. The _Earliest Arrival Problem (EAP)_ is the problem of finding a multimodal itinerary from \(S\) to \(T\) starting at a time after \(t_{o}\) and arriving at stop \(T\) as early as possible.
2. The _Minimum Number of Transfers Problem (MNTP)_ is the problem of finding a multimodal itinerary from \(S\) to \(T\) starting at a time after \(t_{o}\) and having as few transfers from one vehicle to another as possible.
3. The _Multicriteria problem (MCP)_ that consists in finding a set of Pareto-optimal multimodal journeys from \(S\) to \(T\) starting at a time after \(t_{o}\) with respect to the EA and MNT criteria.
4. The _Profile problem (PRP)_ is the problem in which given a departure time interval \(I\), one wishes to find all Pareto-optimal journeys from \(S\) to \(T\) with respect to EA and the latest departure time within \(I\).  
Given a timetable \(\mathcal{T}\), a delay occurring on a connection \(c\) is modeled as an increase of \(\delta\) minutes on the arrival time: \(t_{a}^{\prime}(c)=t_{a}(c)+\delta(\bmod\,T_{p})\). The timetable is then updated according to some specific policy which depends on the network infrastructure. The new timetable, called _disposition timetable \(\mathcal{T}^{\prime}\)_, differs from \(\mathcal{T}\) in the arrival and departure times of the vehicles that depend on \(H(c)\) in \(\mathcal{T}\).  
In this work, we consider the simplest policy for handling delays and updating the timetable (no vehicle waits for a delayed one), which is also considered in similar works (see e.g., [10]). Other policies can be found in, for example, [12; 13; 14; 15; 16]. Therefore, when a delay occurs on a connection \(c\), the only time references which are updated are those regarding the departure times of \(H(c)\). Moreover, we assume that the policy does not take into account any possible slack times, and hence the time references are updated by adding \(\delta(\bmod\,T_{p})\).