# Time-Dependent Alternative Route Planning: Theory and Practice +
## 3 The TDAG Algorithm
### Analysis of TDAG's Preprocessing Phase and Query Algorithm  
In this section, we provide a theoretical analysis for the quality of the alternative graph produced by TDAG, by means of the stretch of the optimal \(od\)-path in the alternative graph \(H\), compared to the one in the original graph \(G\). Since TDAG employs a series of heuristic improvements, which make it difficult to provide a theoretical analysis, we focus here on a simplified variant of TDAG without any heuristic improvements, which we shall explain in detail later on. Before that, we start with our working assumptions on the input instance. We consider a directed graph \(G=(V,E)\) with \(n=|V|\) vertices and \(m=|E|\) arcs, which is sparse: \(m\in\mathcal{O}(n)\). \(G\) is accompanied with a time-dependent cost metric, succinctly represented by periodic, continuous, pwl arc-traversal-time functions \(D[uv]:[0,T)\mapsto\mathbb{R}_{\diamond}\). All time-dependent distances in this metric are indeed the minimum-travel-times \(D[o,d](t_{o})\), for each pair of vertices \((o,d)\in V\times V\) and departure time \(t_{o}\in[0,T)\) from the origin \(o\). Apart from the travel-times metric, we also consider the _Dijkstra-Ranks_ metric for vertex-pairs: For any pair \((o,d)\in V\times V\) and departure time \(t_{o}\in[0,T)\), the (also time-dependent) Dijkstra-Rank value, \(DR[o,d](t_{o})\) is the cardinal number of \(d\) (i.e., its position in the settling order) when growing a forward TDD ball from \((o,t_{o})\). For theses two metrics that we consider, we make the following assumptions that have also been considered in previous works concerning time-dependent oracles, e.g., in [22]. **Assumption 1** (Bounded Travel-Time Slopes). : _All the minimum-travel-time slopes are bounded in a given interval \([-\Lambda_{\min},\Lambda_{\max}]\), for the given constants \(\Lambda_{\min}\in[0,1)\) (\(\Lambda_{\min}<1\) due to the FIFO property) and \(\Lambda_{\max}\geq 0\)._  
**Assumption 2** (Bounded Opposite Trips). : _The ratio of minimum-travel-times in opposite directions between two vertices for any specific departure time, but not necessarily via the same path, is upper bounded by a given constant \(\zeta\geq 1\)._  
**Assumption 3** (Min-Travel-Times vs. Dijkstra-Ranks). : _There exist constants \(\lambda,c_{1},c_{2}\in\mathcal{O}(1)\) and functions \(f(n)\leq\log^{c_{1}}(n)\), \(g(n)\leq c_{2}\log(n)\), s.t. the following hold:_  
1. \(DR[o,d](t_{o})\leq f(n)\cdot(D[o,d](t_{o}))^{\lambda}\)_, and_
2. \(D[o,d](t_{o})\leq g(n)\cdot(DR[o,d](t_{o}))^{1/\lambda}\)_._  
_Analogous inequalities hold for the static free-flow and the full-congestion metrics, \(D^{(f)}\) and \(D^{(c)}\)._  
Our next consideration is the preprocessed data-structure that is created by a time-dependent oracle (e.g., the CFLAT oracle in [22]). We start with an i.u.a.r. (i.e., independent and uniformly at random, without repetitions) selection of a small subset \(L\subset V\) of landmark-vertices: each vertex \(v\in V\) is chosen to be included in \(L\) with probability \(\rho\in(0,1)\), independently of the other vertices. The preprocessed data structure succinctly represents the upper-bounding functions \(\overline{D}[\ell,v]:[0,T)\mapsto\mathbb{R}_{\diamond}\) of the (unknown) minimum-travel-time functions \(D_{\mathbb{G}}[\ell,v]:[0,T)\mapsto\mathbb{R}_{\diamond}\), for all landmark-to-vertex pairs \((\ell,v)\in L\times V\). Our precondition is that these upper-bounding functions are also periodic, continuous, pwl, and constitute \((1+\epsilon)\)-approximations of the optimal travel-time functions. The variant of the TDAG query algorithm that we consider, called TDAGsimple, considers that \(N=1\), i.e., it attempts to exploit only the closest landmark from the origin of the route.