Exploiting Road Network Properties in Efficient Shortest‐Path Computation

The essential elements of any navigation system are a shortest-path algorithm and a map dataset. When seen in the light of the basic requirement of such a system, to provide high quality navigation solutions fast, algorithms have to be efficient and road networks have to be up-to-date. The contribution of this work is two-fold. First, the HBA* algorithm, an efficient shortest-path algorithm, is presented that mimics human driving behavior by exploiting road network hierarchies. HBA* is a fast algorithm that produces high quality routes. Second, in a thorough performance study dynamic, travel times are introduced to replace the unreliable static speed types currently used in connection with road network datasets. Dynamic travel times are derived from large quantities of historic vehicle tracking data. The integrated result, fast algorithms using accurate data, is empirically evaluated using actual road network datasets and related dynamic travel time data. map dataset. When seen in the light of the basic requirement to such a system, to provide high quality navigation solutions fast, algorithms have to be efficient and road networks have to be up?to?date. The contribution of this work is two?fold. First, the HBA* algorithm, an efficient shortest?path algorithm, is presented that mimics human driving behavior by exploiting road network hierarchies. HBA* is a fast algorithm that produces high quality routes. Second, in a thorough performance study dynamic, travel times are introduced to replace the unreliable static speed types currently used in connection with road network datasets. Dynamic travel times are derived from large quantities of historic vehicle tracking data. The integrated result, fast algorithms using accurate data, is empirically evaluated using actual road network datasets and related dynamic travel time data.

ICSI Technical Report TR-09-007

Other