Dynamic Routing

The intent of this research is to find a way of applying a version of a shortest path algorithm such as Dijkstra’s, or the more general A*, to a graph with parameterized edge weights that are subject to possibly many updates, and apply this to a dynamic travel routing environment. Let a directed graph G = {V, E, w} be given with vertex set V = {1, 2, . . . , n}, edge set E, and a parameterized weight function w : E × T → R+. In our application G corresponds to a road map with edges corresponding to road segments, vertices corresponding to intersections, and w(e,t) denoting the travel time weight on edge e at entrance time t. We assume that T is a suitable representation for different times on different days, months, years, etc. The travel time w(e,t) on an edge e = (u, v) at time t is the time it takes a vehicle to travel from u to v when entering u at time t. The dynamic routing task is to find the shortest path (i.e., the path with the lowest sum of travel time weights) from a start vertex s to a target vertex t. In addition, we plan to find a scheme that works best in a system where the edge weights are frequently updated. Hence, the dynamic routing task is dynamic in two ways: (1) The edge weights are parameterized (as opposed to one constant weight per edge), and (2) the weight function w may be subject to updates.

Dynamic routing has a direct application in route planning for automobile travelers. Current in-car navigation systems generally compute shortest paths without taking the current traffic situation into account. Assuming the existence of a system which provides current and frequent updates of travel time weights, a dynamic routing algorithm will have to cope with non-constant edge weights as well as with travel time updates. Also note that real-world limitations such as bandwidth and data transfer rates affect the implementation. This paper presents algorithms for two real-world architectures for the system that would handle this task.