## 3 Traffic Multi-Maps Generation Based on Disjoint Path Flows
### Semi-Disjoint K-Shortest Paths  
When considering all the possible paths available for a commodity, it is necessary to analyze the disjoint level between them. If the first \(K\) shortest paths are selected, only one or two links may vary between them. It will cause congestion on some shared links when alternative routes are distributed to the flow. When designing traffic balancing, generating the best route alternatives and route variety is necessary. \[DjC_{n}=1-Sim_{n} \tag{10}\]  
Disjoint level criteria \(DjC_{n}\) between two routes \(\mathrm{r_{a}}\) and \(\mathrm{r_{b}}\) is the inverse of their similarity \(Sim_{n}\) (10). Complete disjointed paths a very restrictive constraint, so they is usually considered a partial path disjoint level, assuming a minimum disjoint level threshold \(\phi\). For instance, when a threshold \(\phi=0.6\) is used, any found paths must have at least a 60% difference, considering the similarity criteria selected. Different similarity criteria can be used:  
* Edge-cost similarity (11) is the most used term (often simplified as \"similarity\") and is measured as the ratio of accumulated cost from edges in common between \(\mathrm{r_{a}}\) and \(\mathrm{r_{b}}\) versus the minimum cost of the whole routes \(\mathrm{r_{a}}\) or \(\mathrm{r_{b}}\)[16]: \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{6}{c}{**Commodities**} \\ \hline  & & d\({}_{1}\) & d\({}_{2}\) & d\({}_{3}\) & d\({}_{4}\) & d\({}_{5}\) \\ \cline{2-7}  & q\({}_{1}\) & \(x^{1,1}\) & \(x^{1,2}\) & \(x^{1,3}\) & \(x^{1,4}\) & \(x^{1,5}\) \\ \cline{2-7}  & q\({}_{2}\) & \(x^{2,1}\) & \(x^{2,2}\) & \(x^{2,3}\) & \(x^{2,4}\) & \(x^{2,5}\) \\ \cline{2-7}  & q\({}_{3}\) & \(x^{3,1}\) & \(x^{3,2}\) & \(x^{3,3}\) & \(x^{3,4}\) & \(x^{3,5}\) \\ \cline{2-7}  & q\({}_{4}\) & \(x^{4,1}\) & \(x^{4,2}\) & \(x^{4,3}\) & \(x^{4,4}\) & \(x^{4,5}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Traffic flow decomposition for five commodities and three fleets. \[Sim_{EC}(\tau_{a},\tau_{b})=\frac{\sum c_{e}^{FF}}{\min\{\mathrm{ffc}_{a}^{d}, \mathrm{ffc}_{b}^{d}\}},\forall e_{e}\in r_{a}\cap r_{b} \tag{11}\]
* In Common-Edges similarity (12), ratio of the number of edges in common between both routes \(\tau_{a}\) or \(\tau_{b}\) versus the minimum number of links in both routes: \[Sim_{EiC}(\tau_{a},\tau_{b})=\frac{\mathrm{count}(\mathrm{ffl}_{e})}{\min\{ \mathrm{E}_{a},\mathrm{E}_{b}\}},\forall e_{e}\in r_{a}\cap r_{b}\] (12)
* Route-length similarity (13), differential route length ratio between the two routes \(\tau_{a}\) and \(\tau_{b}\) considering the minimum length of both routes, as it is considered in CSO [35]: \[Sim_{RL}(\tau_{a},\tau_{b})=\frac{\mathrm{abs}(\mathrm{L}_{a}-\mathrm{L}_{b})}{ \min\{\mathrm{L}_{a},\mathrm{L}_{b}\}}\] (13)
* Route-cost similarity (14), differential route cost ratio between the two routes \(\tau_{a}\) and \(\tau_{b}\) considering the minimum cost of both routes: \[Sim_{RC}(\tau_{a},\tau_{b})=\frac{\mathrm{abs}(\mathrm{ffc}_{a}^{d}-\mathrm{ ffc}_{b}^{d})}{\min\{\mathrm{ffc}_{a}^{d},\mathrm{ffc}_{b}^{d}\}}\] (14)
* Route-links number similarity (15), differential number of links ratio between the two routes \(\tau_{a}\) and \(\tau_{b}\) considering the minimum number of links in both routes: \[Sim_{RN}(\tau_{a},\tau_{b})=\frac{\mathrm{abs}(\mathrm{E}_{a}-\mathrm{E}_{b})}{ \min\{\mathrm{E}_{a},\mathrm{E}_{b}\}}\] (15)  
The k-Shortest Paths with Limited Overlap (kSPwLO) problem for a given commodity \(d\) is a weak NP-hard task that cannot be afforded by extensive searching over all the paths \(\{p_{i}^{d}\}\in P^{d}\), as it grows exponentially [55]. There are exact algorithms to solve _kSPwLO_, but they require intense individual shortest-path processing (using Dijkstra or similar algorithms).