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.

Autore Pugliese

• Ghiani Gianpaolo , Guerriero Emanuela

Tutti gli autori

• G. Ghiani , E. Guerriero

Titolo volume/Rivista

COMPUTERS & OPERATIONS RESEARCH

Anno di pubblicazione

2014

ISSN

0305-0548

ISBN

Non Disponibile

Numero di citazioni Wos

4

Ultimo Aggiornamento Citazioni

28/04/2018

Numero di citazioni Scopus

4

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile