# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 2 Background  
The journey planning problem takes as input a timetable that contains data concerning stops, vehicles (e.g., trains, buses or any means of transportation) connecting stops and departure and arrival times of vehicles at stops. More formally, a timetable \(\mathcal{T}\) is defined by a triple \(\mathcal{T}=(\mathcal{Z},\mathcal{S},\mathcal{C})\), where \(\mathcal{Z}\) is a set of vehicles, \(\mathsf{S}\) is a set of stops (often in the literature also referred to as stations) and \(\mathcal{C}\) is a set of elementary connections whose elements are 5-tuples of the form \(c=(Z,s_{i},s_{j},t_{d},t_{a})\). Such a tuple is interpreted as vehicle \(Z\in\mathcal{Z}\) leaves departure stop \(s_{i}\in\mathsf{S}\) at departure time \(t_{d}\), and the immediately next stop of vehicle \(Z\) is stop \(s_{j}\in\mathsf{S}\) at time \(t_{a}\) (i.e., \(t_{a}\) is the arrival time of \(Z\) at arrival stop \(s_{j}\in\mathsf{S}\)). Departure and arrival times are integers in \(\{0,1,\ldots,t_{max}\}\) representing times in minutes after midnight, where \(t_{max}\) is the largest time allowed within the timetable (typically \(t_{max}=(n\cdot 1440-1)\), where \(n\) is the number of days that are represented by the timetable). We assume \(|\mathcal{C}|\geq\max\{|\mathsf{S}|,|\mathcal{Z}|\}\), that is we do not consider vehicles and stops that do not take part to any connection. In the realistic scenario, each stop \(s_{i}\in\mathsf{S}\) has an associated minimum transfer time, denoted by \(\textsc{{mt}}_{i}\), that is the time, in minutes, required for moving from one vehicle to another inside stop \(s_{i}\). **Definition 1** (Trip). : _A trip is a sequence \(\textsc{{trip}}=(c_{1},c_{2},\ldots,c_{k})\) of \(k\) connections that: (i) are operated by the same vehicle; (ii) share pairtively departure and arrival stop, that is, formally, we have \(c_{i^{\prime}-1}=(Z,s_{i},s_{j},t_{d},t_{a})\) and \(c_{i^{\prime}}=(Z,s_{j},s_{k},t^{\prime}_{d},t^{\prime}_{a})\) with \(t^{\prime}_{d}>t_{d}\) for any \(i^{\prime}\in[2,k]\)._  
Clearly, connections in a trip are ordered in terms of the associated departure times, hence we say connection \(c_{j}\) follows connection \(c_{j-1}\) in a trip trip whenever the departure time of the former is larger than that of the latter. Similarly, we say connection \(c_{j}\) precedes connection \(c_{j+1}\) in a trip trip. **Definition 2** (Journey). : _A journey \(J=(c_{1},c_{2},\ldots c_{n})\) connecting two stops \(s_{i}\) and \(s_{j}\) is a sequence of \(n\) connections that: (i) can be operated by different vehicles; (ii) allows reaching a given target stop starting from a distinguished source stop at a given departure time \(\tau\geq 0\), that is, the departure stop of \(c_{1}\) is \(s_{i}\), the arrival stop of \(c_{n}\) is \(s_{j}\) and the departure time of \(c_{1}\) is larger than or equal to \(\tau\); (iii) is formed by connections that satisfy the time constraints imposed by the timetable, namely that if the vehicle of connection \(c_{i}\) is different with reference to that of \(c_{i+1}\) at a certain stop \(s_{h}\), then the departure time of \(c_{i+1}\) must be larger than the arrival time of \(c_{i}\) plus \(\textsc{mtt}_{h}\)._  
As well as trips, journeys are implicitly ordered by time according to departure times of the connections. The traveling time of a journey is given by the difference between arrival time of its last connection and \(\tau\). An earliest arrival query \(\textsc{ea}(s_{i},s_{j},\tau)\) asks, given a triple \(s_{i},s_{j},\tau\) consisting of a source stop \(s_{i}\), a target stop \(s_{j}\), and a departure time \(\tau\geq 0\), to compute a quickest journey, that is, a journey that starts at any \(t\geq\tau\), connects \(s_{i}\) to \(s_{j}\), and minimizes traveling time. In what follows we provide two useful definitions that are necessary to introduce the notion of profile query. **Definition 3** (Time-Dominated Journey). : _Let \(I^{\prime}\) and \(I^{\prime\prime}\) be two journeys, both connecting two stops \(s_{i}\) and \(s_{j}\).