# Time-Dependent Alternative Route Planning: Theory and Practice +
## 1 Introduction
### The Curse of Alternatives  
Single-route responses to route-planning queries may not always be desirable or satisfactory. There is quite often a need for providing, not just the optimal route, but rather a handful of _meaningful_ (by ambiguous and different aspects or features) alternative routes, e.g., for having some plan-B mobility scenarios in case of unforeseen incidents (against the scenario of having just a single computed route, which may become obsolete) or simply because the commuter is uncertain about their actual secondary preferences (e.g., quietness, view, or safety) among \"sufficiently good\" routes. In particular, the commuters typically:  
1. prefer to have choices;
2. have some secondary optimization criteria, based on their own personal preferences, that vary and depend on specialized knowledge or constraints (e.g., like/dislike certain parts of a route), which are usually difficult to quantify, and certainly unknown to the route planner;
3. occasionally prefer to follow a route different from the optimal one, according to their primary optimization criterion, due to some unforeseen or emergent traffic condition (accident, road works, etc.). Consequently, a route planning service offering a _set_ of _meaningful_ alternative routes of _good quality_, is more likely to satisfy the commuters' needs; and vice versa, the commuters can use alternative routes as back-up choices in case of emergent traffic conditions or other unforeseen incidents. Since, most of the time, the commuters' secondary optimization criteria are unknown to the route planner, modern route planning systems, like Google maps, typically recommend, apart from the optimal route, also a handful of alternative routes for each route-planning query, hoping that at least one of them might positively surprise the commuter. The present work focuses exactly on this aspect, the _efficient_ computation of a small set of meaningful alternatives to the optimal _od_-route. In other words, the goal is the selection of a few, hopefully meaningful but also divergent, alternative routes of good quality. When thinking about the computation of alternative routes, a first line of attack that comes to mind is to consider several criteria. In that case, one might be tempted to try to compute the set of all pareto-optimal solutions. Yet, as stated in [2], for a network of 18 Mio nodes \"it turns out this input is too big for finding all Pareto routes\". Hence they had to restrict their experimentation to a graph with 77K nodes and two metrics only, reporting running times around 200 ms; as stated in the paper explicitly, more than two metrics may only be considered for very strongly correlated travel time metrics. Other approaches were based on responding to the so-called skyline-queries in the multicriteria setting; however, they also turned out to be feasible only for small graph sizes, e.g., in [3] a query time of 40 s on a graph with only 6K nodes and three metrics was reported. Apart from the obvious tractability issues, another challenge is that, as previously mentioned, the route planning service may not be aware of the commuters' secondary criteria of optimization, either because they do not want to reveal them, or because they cannot even quantify them. Another approach that would come to mind, is the computation of the \(k\)-shortest paths from \(o\) to \(d\). Unfortunately, this problem is also quite complex and computationally demanding [4], especially for large-scale real-world instances. Moreover, the resulting routes are typically almost identical to the optimal route, differing only in a few arcs, which constitute small \"detours\", rendering them rather uninteresting alternatives to the optimal route. The works [5; 6] study the efficient computation of \(k\)-loopless-shortest paths, in order to both speed-up the computation and provide more meaningful alternative routes. Still, each newly constructed route is only meant to avoid the creation of cycles with the previously selected routes but otherwise can be quite similar to them.