The Routing Algorithm

 

The generative component of the Adaptive Route Advisor is a routing algorithm that plans a path through a digital map from a starting point to a destination. The planner represents the digital map as a graph, where the nodes are intersections and the edges are parts of roads between intersections. Our digital maps provide four attributes for each edge: length, estimated driving time, turn angle to connected edges, and road class (e.g., highway, freeway, arterial road, local road). The planner refers to these digital maps to minimize the weighted sum of the driving time, distance, number of turns, number of intersections, and distance on each road class.

  

Figure 2: The route request window for the Adaptive Route Advisor.

The routing algorithm finds a path from a designated source node, usually the current position, to a designated destination. The cost of an edge is computed as a weighted sum of its attributes,

$$c = \sum_i{(w_i \cdot a_i)} .$$

The weight vector plays the role of a user preference model that defines the relative importance of the attributes. The system uses an optimized version of Dijkstra's shortest path algorithm [2] to find the path with the minimal sum of the costs for the edges in the path.