© 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} }