Available information determines the best routing algorithm
The state of the art in vehicle routing, whether human controlled or autonomous, relies on solving network graphs representing interconnected streets and highways. The network graph consists of nodes representing intersections and edges representing roadways. Edges are given weights which depend on, e.g., edge distance or travel time. Each vehicle using the network has an origin and destination node. A route connects the origin and destination node, optimizing the sum of edge weights, for example, minimizing the total travel time. Here I discuss four routing schemes which comprise different degrees of complexity and overall optimization. The difference between the schemes is based on the availability and use of of real-time and historical traffic data.
Static Routing
Static routing is based on algorithms for optimizing network graph paths to produce, e.g., shortest distance or fastest travel time. Most modern smart phones and vehicle navigation systems are capable of performing static routing. However, static routing does not account for current road conditions, construction, accidents or traffic congestion. Static routing is based on relatively unchanging road and infrastructure data but is not aware of real-time roadway conditions.
Reactive Routing
Reactive routing algorithms account for real-time traffic congestion by increasing one or more edge weights to represent slower average vehicle speed on those edges. In such cases, the routing algorithm may select a route that avoids the congested roads. Reactive Algorithms react to existing congestion and may reduce congestion intensity, but they do not prevent congestion.
Predictive Routing
Predictive routing uses both real-time and historical data to predict potential congestion a few hours in advance. Vehicle routes can be selected which avoid these potential congested areas. It is interesting to note that widespread adoption of predictive routing algorithms may simply relocate congestion along inferior secondary routes, resulting in a net negative benefit. The algorithms may also be subject to cyclic feedback behavior as historical data is altered by the algorithms themsleves. A worst case scenario would have the congestion following the congestion-avoidance routing, like a dog chasing its own tail.
Preemptive Routing
Connected autonomous vehicle (CAV) technology allows for the implementation of new routing algorithms based on preemptive strategies which avoid the formation of traffic congestion before it happens. For example, given a real-time set of vehicle origins and destinations, predictive routing algorithms can predict which roads and intersections may operate above their carrying capacities. A sufficient number of vehicles are then routed on alternative roads to prevent congestion which would occur using current reactive routing algorithms.
What strategies qualify as preemptive?
Traffic flow problems typically assume a continuous ‘fluid flow’ model. Recent developments in CAV technology allow a ‘digitized’ or ‘packet’ model. Similar to the difference between analog and digital data transmission.