Abstract

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.

Autore Pugliese

• Ghiani Gianpaolo , Guerriero Emanuela

Tutti gli autori

• Calogiuri T. , Ghiani G. , Guerriero E.

Titolo volume/Rivista

NETWORKS

Anno di pubblicazione

2015

ISSN

0028-3045

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

1

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile