© 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 112-117 2015 © 2015 Wiley Periodicals, Inc.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.
https://doi.org/10.1002/net.21616Cite as:
@article{Calogiuri_2015,
doi = {10.1002/net.21616},
url = {https://doi.org/10.1002%2Fnet.21616},
year = 2015,
month = {jul},
publisher = {Wiley},
volume = {66},
number = {2},
pages = {112--117},
author = {Tobia Calogiuri and Gianpaolo Ghiani and Emanuela Guerriero},
title = {The time-dependent quickest path problem: Properties and bounds},
journal = {Networks}
}