# Time-Dependent Alternative Route Planning: Theory and Practice +
## 2 Preliminaries  
A time-dependent _road network_ can be modeled as a _directed graph_\(G=(V,E)\), where each node \(v\in V\) represents either an intersection point along a road, or vehicle departure/arrival event with zero waiting-time, and each edge \(e\in E\) represents uninterrupted road segments between nodes. Let \(|V|=n\), \(|E|=m\). Given a time period \(T\) and any edge \(e=uv\in E\), if we consider any _departure-time_\(t_{u}\in[0,T)\) from the tail \(u\), then \(D[uv](t_{u})\) is the corresponding traversal-time for the arc \(uv\), determined by the evaluation of a _continuous_, _piecewise-linear_ (pwl) function \(D[uv]:[0,T)\mapsto\mathbb{R}_{\geq 0}\). Analogously, \(t_{v}=Arr[uv](t_{u})=t_{u}+D[uv](t_{u})\) is the corresponding function providing the _arrival-time_ to the head \(v\) or \(uv\) for different departure times from the tail \(u\). We additionally make the (typical for road networks) _strict FIFO property_ assumption: each arc-traversal-time function \(D[uv]\) has a minimum slope greater than \(-1\). Equivalently, we assert that the arc-arrival-time functions \(Arr[uv]\) are strictly increasing. This property implies that there is no reason to wait at the tail \(u\) of \(uv\) before traversing it towards the head \(v\), provided that we are interested in the earliest-arrival-times. Given a departure time \(t\in[0,T)\), and a path \(\pi=\langle x_{0}x_{1},x_{1}x_{2},\ldots,x_{k-1}x_{k}\rangle\) (as a sequence of arcs),  
\[Arr[\pi](t)=Arr[x_{k-1}x_{k}](Arr[x_{k-2}x_{k-1}](\cdots(Arr[x_{1}x_{2}](Arr[ x_{0}x_{1}](t)))\ \cdots))\]  
is the _path-arrival-time_ function, defined by applying function composition on the arc-arrival-time functions of \(\pi\)'s constituent arcs. In addition, \(D[\pi](t)=Arr[\pi](t)-t\) is the corresponding _path-travel-time_ function. Let \(\mathcal{P}_{u,v}\) be the set of all \(uv\)-paths in \(G\), i.e., originating at \(u\) and ending at \(v\). Then, \(\forall t\in[0,T)\), \(Arr[u,v](t)=\min_{\pi\in\mathcal{P}_{u,v}}\{Arr[\pi](t)\}\) is the _earliest-arrival-time_ function, from \(u\) to \(v\). Analogously, \(D[u,v](t)=Arr[u,v](t)-t\) is the corresponding _minimum-travel-time_ (or shortest-path-length) function, and \(P[u,v](t)\) is the corresponding _time-dependent-shortest-path_ function, providing the minimum-travel-time paths w.r.t. the departure time \(t\) from \(u\). For \(\epsilon>0\), a function \(\overline{D}[u,v]\) such that \(\forall t\in[0,T)\), \(D[u,v](t)\leq\overline{D}[u,v](t)\leq(1+\epsilon)\cdot D[u,v](t)\) is called a \((1+\epsilon)\)_upper-approximation_ for \(D[u,v]\). Our main goal is to obtain fundamentally different (but not necessarily disjoint) alternative-paths with optimal or near-optimal travel-times, from an origin-node \(o\) to a destination-node \(d\) in \(G\) and departure time \(t_{o}\) from \(o\). The aggregation of the computed alternative _od_-paths is materialized by the concept of the _Alternative Graph (AG)_, a notion first introduced in [7]. We shall now proceed with the adaptation of the AG concept to the time-dependent context. Formally, an alternative graph \(H=(V^{\prime},E^{\prime})\) is the induced subgraph by the arcs of several _od_-paths in \(G\). Let \(D_{G}[u,v](t)\equiv D[u,v](t)\) and \(D_{H}[u,v](t)\) denote the minimum travel-time functions, whereas \(Arr_{G}[u,v](t)\equiv Arr[u,v](t)\) and \(Arr_{H}[u,v](t)\) denote the earliest-arrival-time functions w.r.t. \(G\) and \(H\), respectively. Succinctly representing the produced alternative paths with AG is reasonable because the alternative paths may share common nodes (including \(o\) and \(d\)) and arcs. Furthermore, their subpaths may be combined to form even more alternative paths, possibly better than the ones that determined the AG. In general, there can be too many alternative \(od\)-paths, and the problem is to find a way to select only a meaningful subset of them. Hence, there is a need for filtering and ranking the alternative \(od\)-paths, based on certain quality-assessment criteria.