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.

A lower bound for the quickest path problem

GHIANI, GIANPAOLO;GUERRIERO, Emanuela
2014-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/389768
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact