Article ID: | iaor20101538 |
Volume: | 45 |
Issue: | 1 |
Start Page Number: | 143 |
End Page Number: | 158 |
Publication Date: | Jan 2010 |
Journal: | Computational Optimization and Applications |
Authors: | Baptiste Philippe, Liberti Leo, Nannicini Giacomo, Barbier Gilles, Krob Daniel |
Keywords: | networks: flow |
Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.