# Time-Dependent Alternative Route Planning: Theory and Practice +
## 3 The TDAG Algorithm
### Query Algorithm of Tdag  
The TDAG query algorithm executes three sequential phases for serving a query \((o,d,t_{o})\in V\times V\times[0,T)\). PHASE 1: Landmark Settlement  
A forward TDD tree \(SPT_{o}(t_{o})\) is grown from \((o,t_{o})\) until either the destination-node \(d\) is settled or a set \(F=SPT_{o}(t_{o})\cap L\) of the \(|F|=N\) closest landmarks are settled (whichever comes first). Subsequently, a reverse BFS tree \(RBFS_{d}\) from \(d\) is constructed that ignores, totally, the traversal-times of the arcs and exploring the neighborhood around \(d\) in a backward fashion. The growth of \(RBFS_{d}\) is interrupted when its size becomes equal to \(|RBFS_{d}|=c\cdot|SPT_{o}(t_{o})|\), for some constant \(c\geq 1\). Our experimental analysis showed that \(c=1.2\) is an appropriate choice. We experimented also with growing a reverse TDD tree towards \(d\); however, this approach was more time-consuming, and the resulting alternative graph, to be constructed in the next phases, was eventually similar to the one constructed using the reverse BFS tree from \(d\). PHASE 2: Path Collection  
Using the preprocessed data, our next task was to construct a subgraph of the approximate shortest paths from the \(N\) landmarks \(\ell\in F\), with their own departure times \(t_{\ell}\), which were already computed in PHASE 1, towards each leaf node of \(RBFS_{d}\). This was done as follows: For each leaf-node \(v\) of \(RBFS_{d}\) and landmark \(\ell\in F\) with departure time \(t_{\ell}\), we recursively move backwards from \(v\) towards \(\ell\) by recursively looking-up predecessors in the timestamped shortest-path trees \(SPT_{\ell}(i)\) and \(SPT_{\ell}(i+1)\) for which it holds that \(t_{\ell}^{i}\leq t_{\ell}<t_{\ell}^{i+1}\). All the arcs that participate in these \((\ell,v)\)-paths, for all landmarks \(\ell\in F\) and all leaves \(v\) of \(RBFS_{d}\), become marked. The initial alternative graph \(H\) consists, then, of the union of the two trees \(SPT_{o}(t_{o})\) and \(RBFS_{d}\) of PHASE 1, with the set of all the marked arcs during PHASE 2. We continue by expanding the forward TDD tree \(SPT_{o}(t_{o})\) of PHASE 1 towards \(d\), by working only in the subgraph \(H\), until all the nodes in \(H\) are settled. This allows us to obtain a tentative arrival time \(\tilde{t}_{d}\) at \(d\):  
\[\tilde{t}_{d}=t_{o}+D_{H}[o,d](t_{o})\leq t_{o}+\min_{\ell\in F}\{D_{G}[o,\ell ](t_{o})+\overline{D}[\ell,d](t_{o}+D_{G}[o,\ell](t_{o}))\}\]  
where \(\overline{D}[\ell,d](t)\) is the upper-bounding \((1+\epsilon)\)-approximate travel-time function from \(\ell\) to \(v\), stored in the preprocessed data of TDAG. As was proved in [21], \(\tilde{t}_{d}\) is a constant upper-bound of the earliest-arrival-time \(t_{d}=t_{o}+D_{G}[o,d](t_{o})\). The quality of this upper bound depends on the choice of the precision \(\epsilon\) of the preprocessed information, the number \(N\) of settled landmarks within \(SPT_{o}(t_{o})\), and the size of the reverse BFS tree \(RBFS_{d}\). PHASE 3: Pruning of the Alternative Graph  
The graph \(H\) produced by PHASE 2 is already smaller than \(G\). Nevertheless, it is further pruned so as to meet the three quality criteria for an alternative graph: small path overlapping, small stretch, and small size. This is done in three steps. **Step 3.1: Enforcement of the small stretch. **: We first aim at a loose pruning over \(H\), in order to obtain a subgraph containing candidate \(od\)-paths with reasonable travel-times. Towards this direction, we consider the rationale of the via-node shortest \(od\)-routes. In particular, any node \(v\) in \(H\) whose shortest travel-time from \(o\) to \(d\) via \(v\) is greater than the targeted upper-bound, i.e., \(D_{H}[o,v](t_{o})+D_{H}[v,d](t_{o}+D_{H}[o,v](t_{o}))>maxStretch\cdot D_{H}[o,d] (t_{o})\), is removed. **Step 3.2: Decrease in the number of candidate \(od\)-routes.