# Time-Dependent Alternative Route Planning: Theory and Practice +
## 1 Introduction
### The Curse of Time-Dependence  
Most of the shortest-path algorithms traditionally consider static arc-costs. Nevertheless, a crucial aspect, at least when having to deal with real-world instances, is the temporality of the network characteristics, which is often depicted by some kind of predetermined dependence of the arc-cost metric on the actual time that each arc is used. E.g., the traversal-time of particular road segments in a city, the packet-loss rate of a connecting line in IT infrastructure, and the validity of particular relationships among pairs of individuals in a social network, depend on exactly when one considers the corresponding arc in the underlying graph model.  
Perhaps the most typical application scenario also motivating our work is that of route planning in road networks, where the time to traverse an arc \(a=uv\) (modeling a road segment) depends on the temporal traffic conditions while doing that and, thus, on the departure time from its tail \(u\). This gives rise to _time-varying_ network models and to computing time-varying solutions (i.e., collections of shortest paths) in such networks. Several variants of this model attempt to capture the time-variation of the underlying graph structure and/or the arc-cost metric, e.g., dynamic shortest paths, parametric shortest paths, stochastic shortest paths, and temporal networks; see [15] for a discussion on these variants and their comparison.  
In this work, we consider the case in which the traversal-time variation of each arc \(a\) is determined by a _function_\(D[a]\), which is considered to be a continuous, piecewise linear (pwl), and periodic function of the time at which the resource is actually being used [16; 17; 18; 19]. To see why this is more suitable, consider, for example, the live traffic services of major car navigator vendors (e.g., TomTom) that provide real-time estimations of average travel-time values, collected by periodically sampling the average speed of each road segment in a city, using the cars connected to the service as sampling devices. A customary, comprehensive, and computationally-lighter way to represent this historic traffic data is to consider the continuous pwl linear interpolants of the sample points as the _traversal-time functions_ for the arcs in the underlying graph.  
When providing route plans in these types of road networks, usually called _time-dependent_ road networks, the arc costs are determined by evaluating these _traversal-time_ functions for the arcs for certain departure time values, while the time-dependent shortest paths are construed as _minimum-travel-time_ paths.  
The goal is then to determine the cost (total _travel-time_) of an optimal path from an origin vertex \(o\) to a destination vertex \(d\) as a function of the _departure-time_\(t_{o}\) from \(o\). Due to the time-dependence of the arc-cost metric, the actual traversal-time of an arc \(a=uv\) is unknown until the exact time \(t_{u}\geq t_{o}\) at which \(uv\) starts being traversed from \(u\) towards \(v\).  
For the single-route case, there have been quite interesting and efficient oracles and speedup techniques to handle instances with time-dependent arc-costs. In particular, there exist approaches that compute either an optimal or an approximately optimal \(od\)-route, using heuristic methods (see e.g., [20]), or oracles (see e.g., [15; 21; 22]). The latter case, of an oracle, consists of a (subquadratic in size) carefully designed data structure, created during a preprocessing phase, along with a query algorithm that exploits this data structure in order to respond to arbitrary earliest-arrival-time queries in sublinear time, with a _provably small_ approximation guarantee for the quality of the solution.  
For the alternative-routes case, at least to our knowledge, the literature has been confined to instances with static arc-costs.