Improved approximation for time-dependent shortest paths
We study the approximation of minimum travel time paths in time dependent networks. The travel time on each link of the network is a piecewise linear function of the departure time from the start node of the link. The objective is to find the minimum travel time to a destination node d, for all possible departure times at source node s. Dehne et al. proposed an exact output-sensitive algorithm for this problem [6, 7] that improves, in most cases, upon the existing algorithms. They also provide an approximation algorithm. In [10, 11], Foschini et al. show that this problem has super-polynomial complexity and present an ε-approximation algorithm that runs(equation presented) shortest path computations, where λ is the total number of linear pieces in travel time functions on links, L is the horizontal span of the travel time function and Tmin and Tmax are the minimum and maximum travel time values, respectively. In this paper, we present two ε-approximation algorithms that improve upon Foschini et al.'s result. Our first algorithm runs (equation presented) shortest path computations at fixed departure times. In our second algorithm, we reduce the dependency on L, by using only (equation presented)total shortest path computations.
Omran, M. (Masoud), & Sack, J.-R. (2014). Improved approximation for time-dependent shortest paths. doi:10.1007/978-3-319-08783-2_39