The time-dependent quickest path problem: Properties and bounds

The fast computation of point-to-point quickest paths on very large time-dependent road networks will allow next-generation web-based travel information services to take into account both congestion patterns and real-time traffic informations. The contribution of this article is threefold. First, we prove that, under special conditions, the Time-Dependent-Quickest Path Problem (QPP) can be solved as a static QPP with suitable-defined (constant) travel times. Second, we show that, if these special conditions do not hold, the static quickest path provides a heuristic solution for the original time-dependent problem with a worst-case guarantee. Third, we develop a time-dependent lower bound on the time-to-target which is both accurate and fast to compute. We show the potential of this bound by embedding it into a unidirectional A* algorithm which is tested on large metropolitan graphs. Computational results show that the new lower bound allows to reduce the computing time by 27% on average.