# Time-Dependent Alternative Route Planning: Theory and Practice +
## 3 The TDAG Algorithm
### Preprocessing Phase of Tdag  
Initially, TDAG selects a small subset \(L\subseteq V(G)\) of landmark-nodes. There are various methods for the selection of \(L\): either randomly, or according to some properties of the underlying graph, e.g., selection from boundary nodes of some balanced partition of the graph, or the selection of the most significant nodes in a node-ranking of the graph according to a centrality measure, such as betweenness-centrality [21].  
In this work, we adopt one of the most successful methods for landmark selection, called _Sparse-Random_ (SR), according to which, the landmarks are selected randomly and sequentially, so as to avoid having landmarks that are too close to each other. In particular, each new landmark \(\ell\) is chosen uniformly at random from the subset of currently eligible non-landmark nodes. Right after the selection of the new element \(\ell\in L\), a small neighborhood of non-landmark nodes around \(\ell\) is excluded from all the subsequent landmark selections.  
TDAG proceeds with the computation and succinct storage of timestamped shortest-path trees, from each landmark \(\ell\in L\) towards all reachable destinations \(v\in V\). The timestamp \(t\) of a given shortest-path tree \(SPT_{\ell}(t)\) emanating from \(\ell\in L\), denotes the assumed departure time from \(\ell\), for which \(SPT_{\ell}(t)\) is indeed a shortest-path tree. For each landmark \(\ell\in L\), the collection of SPTs  
\[SPT_{\ell}:=\left\{\,SPT_{\ell}(t)\mid t\in T_{\ell}:=\left\{\,t_{\ell}^{1},t _{\ell}^{2},\ldots,t_{\ell}^{\lambda_{\ell}}\,\right\}\,\right\},\]  
for carefully selected distinct (monotonically increasing) departure times, constitutes the travel-time summary stored for landmark \(\ell\) during the preprocessing phase. The computation of SPTs from each landmarks is exactly the one conducted during the preprocessing phase of CFLAT [21]. Therefore, the preprocessing-time requirements can be fine-tuned so that they are _subquadratic_ in the graph size. As for the required space (also _subquadratic_ in the graph size [21]), in order to be able to efficiently handle continental-size time-dependent instances, we had to significantly improve the succinct representation of CFLAT's travel-time summaries--in particular, how they are stored in the main memory.  
The main intervention of this work, w.r.t. the preprocessing space requirements of CFLAT, is a lossless sparse matrix compression methodology for the succinct and space-efficient representation of all the timestamped SPTs from the landmarks, avoiding a considerable increase in the access time of the preprocessed information. In particular, the preprocessed data structure still conceptually contains, for each \(\ell\in L\), the collection \(SPT_{\ell}\) of timestamped shortest-path trees rooted at \(\ell\), which are optimal for the set of distinct, carefully selected departure times from \(\ell\), \(T_{\ell}\subset[0,T)\). The selection of the set \(T_{\ell}\) of distinct departure times from \(\ell\) is such that, for all possible departure times \(t\in[0,T)\), the collection \(T_{\ell}\) contains at least one tree \(SPT_{\ell}(i)\) providing, in worst case, a \((1+\epsilon)\)-approximation for \(D_{G}[\ell,v](t)\):  
\[\forall v\in V,D_{SPT_{\ell}(i)}[\ell,v](t)\leq(1+\epsilon)\cdot D_{G}[\ell,v ](t)\]