# Time-Dependent Alternative Route Planning: Theory and Practice +
## 2 Preliminaries
The main idea of the AG approach is to rank candidate subgraphs w.r.t. their quality scores and discard the ones that have poor scores. We adapt the quality-assessment indicators proposed in [7] for static instances to the time-dependent case. These indicators are defined on the single-arc level and then they are extended to the arc-set level. We provide, at this point, the definition of these quality-assessment criteria, adapted to time-dependent networks. Let \(H=(V^{\prime},E^{\prime})\) be any subgraph of \(G\), in which we are interested for route plans for the query \((o,d,t_{o})\in V\times V\times[0,T)\). * Arc _ae_: \(W[ae](2)=D[ae](Arr_{H}[o,a](2))=D[ae](4)=4\) \(Arr_{H}[o,e](2)=Arr_{H}[o,a](2)+D[ae](Arr_{H}[o,a](2))=4+4=8\) \(share[ae](2)=\frac{W[ae](2)}{D_{H}[o,a](2)+W[ae](2)+D_{H}[e](Arr_{H}[o,a](2))}= \frac{(4)}{(2)+(4)+(5+2)}=0.31\)
* Arc _cc_: \(W[ec](2)=D[ec](Arr_{H}[o,e](2))=D[ec](8)=5\) \(Arr_{H}[o,c](2)=2+min\{D_{H}[(oa,ae,ec)](2),D_{H}[(oa,ab,bc)](2)\}=2+min\{11,10\}=12\) \(share[ec](2)=\frac{W[ec](2)}{D_{H}[o,a](2)+W[ec](2)+D_{H}[c](Arr_{H}[o,c](2))}= \frac{(5)}{(2+4)+(5)+(2)}=0.38\)
* Arc _cd_: \(W[cd](2)=D[cd](Arr_{H}[o,c](2))=D[cd](12)=5\) \(Arr_{H}[o,d](2)=Arr_{H}[o,c](2)+D[cd](Arr_{H}[o,c](2))=12+2=14\) \(share[cd](2)=\frac{W[cd](2)}{D_{H}[o,c](2)+W[e](2)+D_{H}[e](Arr_{H}[o,d](2))}= \frac{(2)}{(2+3+5)+(2)+(0)}=0.17\)  
The overall quality of \(H\) in terms of the path non-overlappingness, stretch, and size-complexity are computed as follows:  
\[ \begin{split} totalDistance(2)&=(share[o](2)+share[ ab](2)+share[bc](2)+share[cd](2))\\ &+(share[af](2)+share[fh](2)+share[hg](2)+share[gd](2))\\ &+(share[ae](2)+share[c](2))+(share[gf](2))\\ &=\frac{(2)}{(2)+3+5+2}+\frac{(3)}{2+(3)+5+2}+\frac{(5)}{2+3+(5)+ 2}+\frac{(2)}{2+3+5+(2)}\\ &+\frac{(2)}{2+(2)+2+4+3}+\frac{(2)}{2+2+(2)+4+3}+\frac{(4)}{2+2 +2+(4)+3}+\frac{(3)}{2+2+2+4+(3)}\\ &+\frac{(4)}{2+(4)+5+2}+\frac{(5)}{2+4+(5)+2}+\frac{(7)}{2+2+(7) +3}\\ &=\frac{(2+3+5+2)}{(2+3+5+2)}+\frac{(2+2+4+3)}{2+(2+2+4+3)}+\frac {(4+5)}{2+(4+5)+2}+\frac{(7)}{4+(7)+3}\\ &=1+0.85+0.69+0.5=3.04\end{split} \]  
\[ \begin{split} averageDistance(2)&=\sum_{c\in\mathcal{ E}}\frac{W[e](2)}{D_{C}[o,d](2):totalDistance(t_{o})}=\sum_{c\in\mathcal{E}}\frac{W[e](2)}{12 \cdot 3.04}\\ &=\frac{2+2+2+2+3+3+4+4+5+5+7}{12\cdot 3.04}=1.07\end{split} \]  
\[ \begin{split} decisionEdges&=|E|^{\prime}|-(|V^{\prime}|- 1)=11-8=3\end{split} \]  
In order to assess the quality of an alternative graph, one should attempt to maximize the value of some target function, which is increasing in the \(totalDistance\) and decreasing in  
Figure 1: Evaluation of the quality-assessment criteria for a given alternative graph. For each node \(x\), \(t_{x}=Arr[o,x](2)\) is the earliest arrival time at \(x\), for departure time \(t_{o}=2\). We assume that \(D_{H}[o,d](2)=D_{G}[o,d](2)\). The minimum travel time is \(D_{H}[o,d](2)=12\) via \(\langle oa,ab,bc,cd\rangle\). the _averageDistance_, under the constraint that the _decisionEdges_ variable remains bounded. Unfortunately, achieving a lower value for _averageDistance_ may take away the ability of collecting high-degree disjoint (non-overlapping) paths, which would lead to a high value for _totalDistance_, since these criteria can be contradicting with each other. In this work, we choose to maximize a target function--the linear combination of the _totalDistance_ and _averageDistance_ variables. In particular, following [7; 11], we aimed to maximize the value of the function  
\[targetFunction(H,o,d,t_{o})=totalDistance+1-averageDistance \tag{1}\]  
under the constraint that the _DecisionEdges_ parameter is, at most, 10.