A lower bound for the quickest path problem

The point-to-point quickest path problem is a classical network optimization problem with numerous applications, including that of computing driving directions. In this paper, we define a 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 an A* algorithm. Computational results on three large European metropolitan road networks, taken from the OpenStreetMap database, show that the new lower bound allows us to achieve an average reduction of 14.36%. This speed-up is valuable for a typical web application setting, where a server needs to answer a multitude of quickest path queries at the same time. Even greater computing time reductions (up to 28.06%) are obtained when computing paths in areas with moderate speeds, e.g. historical city centers. © 2014 Elsevier Ltd.

https://doi.org/10.1016/j.cor.2014.04.015

Cite as:

@article{Ghiani_2014,
	doi = {10.1016/j.cor.2014.04.015},
	url = {https://doi.org/10.1016%2Fj.cor.2014.04.015},
	year = 2014,
	month = {oct},
	publisher = {Elsevier {BV}},
	volume = {50},
	pages = {154--160},
	author = {Gianpaolo Ghiani and Emanuela Guerriero},
	title = {A lower bound for the quickest path problem},
	journal = {Computers {&}amp$mathsemicolon$ Operations Research}
}