# Time-Dependent Alternative Route Planning: Theory and Practice +
## 3 The TDAG Algorithm
### Query Algorithm of Tdag
**: For further reducing the number of the candidate \(od\)-paths, we initially use the Plateau method [11; 13] within \(H\), by having previously run TDD from \((o,t_{o})\) and RTDD from \((d,t_{o}+D_{H}[o,d](t_{o}))\). Any arc not belonging to the resulting Plateau candidate \(od\)-paths is removed from \(H\). The Penalty pruning method [11; 14] is then applied to the resulting subgraph, in order to prune it even further. At each Penalty iteration, TDD runs on \(H\), computing a new time-dependent shortest path \(\pi_{o,d}\), whose constituent arcs are marked and are then appended to the solution set \(E_{s}\). Additionally, all the arcs in \(E_{s}\), and the all the arcs incident to nodes of \(\pi_{o,d}\), are penalized with increasing the penalty factors \(p(e)\) and \(r(e)\), respectively, both initially set to \(0\). In particular, for each arc \(e=uv\in E_{s}\), its travel-time is increased to \(D[e](t)^{(penalized)}=(p(e)^{(current)}+1)D[e](t)^{(original)}\); otherwise, if \(u\) or \(v\) are nodes in \(\pi_{o,d}\) and \(e\) is not an arc of \(\pi_{o,d}\cup E_{s}\), its travel-time is increased to \(D[e](t)^{(penalized)}=(r(e)^{(current)}+1)D[e](t)^{(original)}\). The penalty factors of the affected arcs are increased at the end of each step to \(p(e)^{(new)}=p(e)^{(old)}+p_{c}\) and \(r(e)^{(new)}=r(e)^{(old)}+r_{c}\), where \(p_{c}>0\) and \(r_{c}>0\) are constants. The process is repeated until a sufficient number of alternative paths are found or the travel time adjustments of \(\pi_{o,d}\) paths bring no better results. Eventually, all the unmarked arcs are removed from \(H\). In order to speedup the Penalty method at path computation, the time-dependent variant of \(A^{*}\)[28; 29] can be used in place of TDD. For each node of \(H\), its remaining distance towards \(d\), which was already computed from RTDD during the Plateau substep, can be used as a lower bound for the time-dependent \(A^{*}\) heuristic. **Step 3.3: Reduction in complexity of the alternative graph. **: The final pruning of \(H\) is performed via a ranking procedure. Initially, if a path \(\pi_{x,y}\) in \(H\) has \(outdeg(x)\geq 2\) and \(indeg(y)\geq 2\), and \(\forall v\in\pi_{x,y}-\{x,y\}\)\(outdeg(v)=indeg(v)=1\) (i.e., it increases by one the _decisionEdges_), then it is considered as a _decision-path_ and it is ranked by the function \(rank(\pi_{x,y},t)=\sum_{e\in\pi_{x,y}}\)\((share[e](t)-stretch[e](t))\) that represents the contribution of \(\pi_{x,y}\) in terms of \(averageDistance\) and \(totalDistance\) in \(H\). The ranked decision paths are then sorted by increasing ranking order in a priority queue \(Q\). Consequently, an iterative procedure starts where, in each iteration, a path \(\pi_{x,y}\) is dequeued from \(Q\). If the condition \(outdeg(x)\geq 2\) and \(indeg(y)\geq 2\) remains in effect, then \(\pi_{x,y}\) is removed from \(H\), leading to a decrease by one of the parameter \(decisionEdges\). After the removal of \(\pi_{x,y}\), if, for \(v\in\{x,y\}\), it holds that \(outdeg(v)=indeg(v)=1\), then a new decision path \(\pi\) is revealed that has \(v\) as an internal node. \(\pi\) is ranked and inserted in \(Q\), in order to be considered along with the rest of decision paths. The iterative procedure stops when \(decisionEdges\leq maxDecisionEdges\).