# Time-Dependent Alternative Route Planning: Theory and Practice +
## 3 The TDAG Algorithm
### Analysis of TDAG's Preprocessing Phase and Query Algorithm
We explain the main steps of this query algorithm for alternative routes in Figure 3.  
In order to proceed with the analysis of TDAGsimple, we first recall a theorem that concerns the analysis of the FCA\({}^{+}\) query algorithm for computing an (approximation of an) earliest-arrival-time route in sparse, time-dependent networks:  
**Theorem 1** ([15]). : _If a TD-instance, with \(m\in\mathcal{O}(n)\) and compliant with Assumptions 1, 2 and 3 is preprocessed using \(\mathtt{BIS}^{+}\) for constructing travel-time summaries from \(\rho\) i.u.a.r chosen landmarks, then the expected preprocessing space \(S_{\mathtt{BIS}^{+}}\) and time \(P_{\mathtt{BIS}^{+}}\) are_  
\[ \begin{array}{rl}\mathbb{E}\{S_{\mathtt{BIS}^{+}}\}&\in\mathcal{O}\big{(} \rho n^{2}(K^{*}+1)\big{)}\\ \mathbb{E}\{P_{\mathtt{BIS}^{+}}\}&\in\mathcal{O}\big{(}\rho n^{2}(K^{*}+1) \big{|}\log(n)+\log\log(K_{\max})\big{|}\big{)}=\mathcal{O}\big{(}\rho n^{2}(K ^{*}+1)\log(n)\big{)}\\ \mathbb{E}\{Q_{\mathtt{FCA}^{+}}\}&\in\mathcal{O}(1/\rho)[\log(1/\rho)+\log\log (K_{\max})])=\mathcal{O}(1/\rho)\log(1/\rho))\end{array} \]  
_For the approximation guarantee, \(\mathtt{FCA}^{+}\) returns either an exact od-path or approximate od-path via the nearest landmark \(\ell\) s.t. \(D[o,d](t_{o})\leq R_{o}+\overline{D}[\ell_{o},d](t_{o}+R_{o})\leq(1+\epsilon) \cdot D[o,d](t_{o})+\log(K_{\max})\)._  
Proof. : We first recall that \(D[o,d](t_{o})\leq R_{o}+\overline{D}[\ell_{o},d](t_{o})\leq(1+\epsilon)\cdot D [o,d](t_{o})+\log(K_{\max})\). We claim that \(D[o,d](t_{o})\leq R_{o}+\overline{D}[\ell_{o},d](t_{o})\). We claim that \  
\(\psi\cdot R_{o}\leq(1+\varepsilon+\psi)\cdot D[o,d](t_{o})\), where \(R_{o}=D[o,\ell](t_{o})\) is the minimum-travel-time to \(\ell\), and \(\psi=1+\Lambda_{\max}(1+\varepsilon)(1+2\zeta+\Lambda_{\max}\zeta)+(1+ \varepsilon)\zeta\) is a constant that only depends on the parameters of the travel-times metric but is independent of the network size._  
The following theorem provides a similar analysis for the query time and the approximation guarantee of TDAGSimple (the preprocessing requirements remain the same). Theorem 4.2: _TDAGSimple has the expected time-complexity \(\mathcal{O}(n^{1+\gamma})\), and also returns an alternative graph \(H\) in which the minimum-travel-time for \((o,d,t_{o})\) is, at most, a constant approximation of the minimum-travel-time for \((o,d,t_{o})\) within \(G\): \(D_{H}[o,d](t_{o})\leq\alpha\cdot D_{\mathcal{G}}[o,d](t_{o})\), for some constant \(\alpha=1+\varepsilon+\psi\in\mathcal{O}(1)\)._  
Proof (sketch). : The expected size of the landmark set is \(\mathbb{E}\{|L|\}\in\mathcal{O}(pn)=\mathcal{O}(n^{1-\delta})\). Moreover, by a simple application of Chernoff Bounds, we know that \(|L|\in(1\pm\alpha(1))\cdot n^{1-\delta}\), with high probability. The expected size of the forward TDD-ball grown, cf. step 1, is \(\mathbb{E}\{|SPT(o,t)|\}\in\mathcal{O}\Big{(}\frac{1}{\rho}\Big{)}=\mathcal{O} \Big{(}n^{\delta}\Big{)}\). Again, by a simple application of Chernoff Bounds, it can be shown that \(|SPT(o,t)|\in(1\pm\alpha(1))\cdot n^{\delta}\), with high probability. The expected time-complexity to construct this ball is \(\mathcal{O}(n^{\delta})\). The size of the reverse BFS ball grown in step 4 is chosen as \(|RBFS_{d}|\in n^{\gamma}\). In the original version of the TDAG algorithm (which we implemented in this work), we considered the case where \(|RBFS_{d}|\in\mathcal{O}[|SPT(o,t)|)\), i.e., \(\gamma=\delta\). For our analysis here, we consider the more general case where the BFS ball is chosen independently of the forward TDD ball (e.g., we could select \(\gamma=\frac{\delta}{3}\), in order to reduce the number of paths to reconstruct in step 7). The time-complexity for step 4 is linear in the size of the BFS ball, i.e., \(\mathcal{O}(n^{\gamma})\). Figure 3: The pseudocode for TDAGSimple. The expected size of the reverse TDD ball, cf. step 6, is \(\mathbb{E}\{|TDD_{r}|\}\in\tilde{\mathcal{O}}(n^{\gamma})\).