# Time-Dependent Alternative Route Planning: Theory and Practice +
## 2 Preliminaries
### Computing Alternative Graphs in Static Road Networks
#### 2.2.1 Computing Alternative Routes within the Pareto Set  
The Pareto algorithm [24; 25; 2] computes an alternative graph \(H\) by iteratively finding _Pareto-optimal_ paths on a suitably defined objective cost vector. The idea is to use, as the first edge-cost vector, one of the single-criterion problems, while the second edge-cost is defined as follows: Initially, \(H\) only contains the shortest \(od\)-path. Then, all edges already belonging to \(H\) set their second cost function to their initial edge cost. All edges not belonging to \(H\) set their second cost function to zero.  
A similar line of attack, for finding alternative routes via the multicriteria setting, is related to the so-called _skyline-queries_[3]. This approach was found to be feasible only for small graphs with a few thousands of nodes and three metrics for the arc costs, in which several-seconds query-response time is typically required.  
The only multicriteria-based approach for alternative-routes, at least that we are aware of, that manages to efficiently compute alternative routes in million-node instances, is [26]. Based on the idea of personalized route planning, the paper discovers extreme solutions from the convex-pareto solution set that are sufficiently dissimilar with each other. In this direction, the idea is to use different weight vectors for the arc-cost metrics that provide significantly distinguishable routes for the commuter.  
The deficit of this approach, nevertheless, is that it assumes that the route planner is aware of each commuter's personalized secondary optimization criteria (which would render some of the alternative routes more attractive than others). Of course, this is not a typical situation, mostly because it is hard for a commuter to quantify secondary criteria, such as the scenic-ness or quietness of the routes. Moreover, this approach definitely excludes dominated paths (exactly due to their domination by some other path), even if it is not much worse than other paths but is also significantly distinct from other alternative routes. It also excludes pareto-optimal solutions that do not belong to the convex-pareto solution subset, irrespectively of their significance as alternative routes.  
To recap, all these multicriteria-optimization based approaches for discovering alternative routes suffer from at least one of the following severe deficiencies:  
1. They produce too many alternatives, causing severe computability issues even for moderate-size instances. Moreover, the produced solutions have only small deviations with each other, rendering them rather uninteresting, unless one really looks among them for actually distinguishable alternatives.
2. Relaxing the domination criteria and fine-tuning the bounds to speed-up the computational requirements is non-trivial and time consuming.
3. The secondary optimization criteria, which are rather personalized, are private information of the commuter, typically invisible to the route planner, and they are often difficult to quantify as concrete cost metrics, even for the commuters themselves.