Computing City Distances

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 of interest. 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. Most of the reported research is on producing the optimal path for the point-to-point shortest path queries. An excellent review on this variant of the shortest path problem can be found in [39].

We have used the well-separated concept introduced by Callahan and Kosaraju [27]. Two subsets A and B of points in d-dimensional space are called well-separated if A and B can be contained in a ball of radius $r$ whose minimum distance is at least sr where s>0 is the degree of separation. Thus the approximated distance between any point in $A$ and any point in $B$ is bounded from below by sr and bounded from above by 4r+sr. The paper [27] develops a data structure, called the well-separated pair decomposition, that organizes the pairs of points into pairs of clusters, or well-separated pairs, in a way that preserves approximate distance. This leads to substantial improvements over algorithms that enumerate all distinct pairs of points. We have generalized the results in [27] to road networks. An efficient well-separated pair decomposition data structures have been designed and implemented. The statistics are as follows:

Size of the road network	60,000 intersections
Height of the split tree	33
Number of well separated components	331,916
Degree of separation	s=2.00
Query time	100,000 distance queries per second
Preprocessing time	10 minutes
Relative distance error	8.0 percent

We have further studied the shortest path algorithms and use $A^*$ search in combination with the bounding technique based on well separated sets. Our algorithms compute almost optimal shortest paths (with less than 1 percent error) and work on any road network. Our experimental results show that the algorithm explores significantly less number of nodes than what the algorithm of Goldberg [39] does while computing the shortest paths.

We are currently looking at ways of using our distance computing algorithm to facilitate solutions to so-called application area $\lq\lq$personalized" traffic alert. With street-level directions integrated with traffic incident information, the traffic alert would monitor all the routes registered by the customers simultaneously and warn them with alternate routes to avoid traffic problems along the way on a real time basis.