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.