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 patient transfer problems in Greater Vancouver, we repeatedly require travel distance/time computations between the job locations. This is also true for our Limousine dispatching system 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 transfer 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 [26].
We have used the well-separated concept introduced by Callahan and Kosaraju [15]. The paper [15] 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 [15] to road networks. Efficient well-separated pair decomposition data structures have been designed and implemented.
We have further studied the shortest path algorithms and used 
search in combination with the bounding
technique based on well-separted 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 the algorithm of Goldberg [26] does while
computing the shortest paths.
Our latest involvement with Mobile Knowledge is also very exciting. An essential part of finding the travel time between two points in a city is the underlying road network. The problem is that digital maps containing the information required to produce dependable travel time estimates can be very expensive for small to moderate-size companies. Nowadays, most companies involved in the transportation business add GPS chips to their vehicles. This means that every time a communication occurs with a driver, the current time and GPS position are included in the message. Even in a small-size company, if messages occur at frequent intervals the amount of GPS data is enourmous. The goal of our current project with Mobile Knowledge is to make use of this GPS data to re-create the underlying road network and to use this to produce accurate travel time estimates in a dynamic environment.
We define a track to be two consecutive GPS data points emitted by the
same vehicle. Thus our input is a set of tracks. However, the GPS data are
easily corruptible by the local environments and satellite alignments.
Using statistical analysis of the noisy data and tools from computational geometry,
we are able to
construct a good approximation of the road network in an unsupervised mode.
Once the road map is constructed using the GPS tracks, we apply linear programming-based techniques to estimate
an appropriate 
average' speed for every road segment. This is done using the available
GPS track data. In fact it
is possible to compute average speed for every road segment at
different times during the day. Given this information, we are able to
estimate the average travel time in the city network for any given weekday and time.