Fast point-to-point shortest path queries on dynamic road networks with interfal data.
Giacomo Nannicini, Philippe Jean Baptiste, Daniel Krob, Leo Liberti · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2007
We assume some lower and upper bounding functions l,u : A → R for c are known. In this paper, we propose a Polynomial-Time Approximation Scheme (PTAS) for the Point-to-Point Shortest Path Problem (PPSPP). The stringent time constraints do not make exact algorithms an acceptable choice, yet a guarantee on the solution quality is desired. Our algorithm is based on Dijkstra-type searches performed on clusters of nodes; such clusters are precomputed in such a way as to give a bound on the solution performance, whilst