The shortest path problem is a fundamental problem with numerous applications. Here we study a variant of the problem, where the goal is to find a point-to-point shortest path distance in a directed graph. We have considered the road network of the Greater Vancouver area as our directed graph. In the courier dispatching and the patients' transfer problems in Greater Vancouver, we repeatedly require travel distance/time computations between the job locations. This is also true for the Limousine dispatching system, but for the city of Ottawa. Surely, one can store all the inter-point distances in the road network. However, this imposes a severe storage bottleneck on the prototype system being developed for the courier routing and the patient transfers problems. We have therefore decided to compute the distances on-the-fly. Thus we allow preprocessing, with only one restriction that the additional space used to store precomputed data is limited. Our goal is a fast algorithm for approximating point-to-point shortest path/travel times for any road network which does not require any city specific massaging of data.
A prototype has been built to compute distances for any city network. The approximate time needed to get the travel time between any two intersections in the network is found to be O(log n) (expected) for the greater Vancouver area. The relative error of the approximation, found experimentally, is 8 percent. The optimal Dijkstra's path can be approximated to within 1 percent of the optimal by using the upper bound extimates in A*-like search. The advantages of the designed algorithm are: