Speeding Up Stochastic Routing Of Vehicles Using Tiering Of Shortcut Edges In Contraction Hierarchies

Patent Status

Patent Pending

Full Description

Background

Stochastic route planning is a type of navigation that takes into account uncertainties during travel. For electric vehicles (EVs), both travel time and energy consumption are variable (stochastic). Stochastic routing can offer significant benefits such as arrival at a destination on time while ensuring that the driver does not get stranded due to a lack of battery charge. With stochastic route planning, identifying the appropriate route is computational intensive and can take time of the order of seconds. Prior approaches have had limited success and have stymied the real world adoption of real-time stochastic routing.

Technology

Professor Ravishankar and his team at UCR have previously developed an algorithm for stochastic routing of electric vehicles. In this new invention, they have developed a novel and elegant method for speeding up the computations in identifying an optimal path for an EV on a large road network. The navigation method is augmented with appropriate techniques which adds relevant and realistic shortcuts in the algorithm.

An illustration of the tiering strategy. Uncertainties (or variables) during the travel are represented as either histograms or as continuous distributions. Based on the approximation, as an example, histograms are represented in tier H while continuous distributions are represented in tier G.

Sample results of the computational times on a sample road network in Los Angeles, California.

Advantages

• Effective computational speed up strategy for real time navigation of EVs.
• Demonstrated in real-world traffic conditions with significant improvements to computation time.
• Practical and useful - providing good speed up without sacrificing accuracy.
  

Suggested uses

• Delivery and fleet vehicles
• Public transportation and personal EVs
• Traffic simulation and route planning
  

State Of Development

The team has developed a lab level prototype and evaluated it on real-world traffic data for a section of Los Angeles area - between Long Beach and Oxnard demonstrating competitive computational times.

Related Materials

• Tiering in contraction and edge heirarchies for stochastic route planning