The time‐dependent quickest path problem: Properties and bounds. Issue 2 (1st July 2015)

• Record Type: Journal Article
• Authors: Calogiuri, Tobia; Ghiani, Gianpaolo; Guerriero, Emanuela
• Is Part Of: Networks. Volume 66:Issue 2(2015:Sep.)
• Page Start: 112
• Page End: 117
• Publication Date: 2015-07-01
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21616
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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 <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2d2mk76w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:00283045:media:net21616:net21616-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>A</mml:mi><mml:mo>*</mml:mo></mml:msup></mml:mrow></mml:math></alternatives></inline-formula> 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. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 112–117 2015</p> </abstract>