# Time-Dependent Alternative Route Planning: Theory and Practice +
## 1 Introduction
### The Curse of Alternatives
Moreover, these algorithms work efficiently only for small-to-moderate network instances. To tackle the issue of extensive overlapping in the proposed alternative routes, some more successful, mostly heuristic attempts have been considered. Some of them were based on the _penalty approach_, where one starts with the optimal route but then penalizes its arcs before recomputing the next route in the network with the penalized arc costs [7]. This approach suffers from the need of careful tuning of the penalization parameters to obtain meaningful results. Another approach is based on the so-called _via nodes_. This idea, initiated in [8] and further extended in [9; 10], is based on the computation of a set of routes that are concatenations of shortest paths from the origin \(o\) to some intermediate node \(v\) and then to the destination \(d\). The careful selection of intermediate nodes, called _via-nodes_, may assure meaningful alternatives of acceptable quality. Criteria to measure the quality of a set of alternative routes were proposed in [8], with some improvements in [9; 10]. The query-response is described as this set of alternative routes. An interesting idea for representing a set of alternative routes via the induced subgraph from the involved arcs, which is called the _alternative graph_ (AG), was proposed in [7]. The same work also proposed some quality measures for assessing alternative graphs. Two quite interesting aspects of the notion of an alternative graph, compared to the selection of a set of alternative routes, are the following:  
1. The AG may also contain some additional routes, apart from the chosen ones, by combining parts of the chosen routes in arbitrary ways, and these could also be very good candidates. 2. The small size of the AG allows for a more thorough (but possibly more computationally demanding) search for the best possible set of alternative routes, whose quality and meaningfulness is already guaranteed by the selection of the alternative graph itself. Consequently, [11], which was also based on the penalty method and the alternative graph, improved on the work of [7]. The Alternative Graph (AG) turned out to be more suitable than the Via-Nodes (VN) for high-demanding navigation systems [12]. This is because the VN approach is restricted on fixed optimization criteria and may create (higher than required) overlapping among the alternative routes. The VN approach may not even be successful in finding a sufficient number of alternatives, for certain scenarios. The present work adopts the rationale of an alternative graph, along with the generic quality characteristics that were proposed in [7], quantified by the following _quality-assessment_ criteria:  
* the _totalDistance_ criterion, measures the _total-overlappingness_ of the best subset of routes within AG;
* the _averageDistance_ criterion, measures the _stretch_ of these routes; and
* the number of _decision edges_, i.e., the sum of alternatives per intermediate node visited other than the outgoing arc belonging to the optimal remaining path towards the destination, which measures the complexity of the entire AG subgraph. As it is shown in [7], each of these quality-assessment criteria is important on its own, in order to produce a high-quality AG containing meaningful alternative routes. However, optimizing a single objective function for choosing the AG that combines just any two of them, is an NP-hard problem [7]. Hence, one has to concentrate on heuristics. Four heuristic approaches were investigated in [7], based on the Plateau [13] and Penalty [14] methods. Experimental evaluations in [7; 13] demonstrated that a combination of these two heuristics appeared to be the best choice. A new set of heuristics, including improved extensions of both the Plateau and Penalty methods, was proposed in [11]. As a result, computing an AG subgraph of much better quality than the ones in [7] became possible, and this was verified on several static (i.e., time-independent) road networks of Western Europe.