Optimizing Longer Routes for Electric Vehicles needing Charging Stations

Electric vehicles (EVs) have increased ten-fold over the last two years. And it is estimated that the market share of EVs will increase to more than 50 percent of the passenger car market in the US by 2030. But one of the big questions for buyers considering EVs is the accessibility and availability of recharging stations – particularly for trips requiring multiple charges due to limited battery capacity.

As of 2021 there are around 45,000 public outlets in the US. Pre-planning the most economical route can be a complicated algorithmic challenge, especially considering the various types of stations, availability and traffic conditions.

Kinetica’s graph route-solving capability can be used as the platform to calculate these optimal paths to minimize the total cumulative driving distance between the end points of a trip.

We needed a fast, practical and accurate graph-based optimization solver, with parameters specific to the optimal routing problem of an EV trip involving multiple charging stops so that different capacity limits and re-charging penalties can be rolled into the optimization algorithm

We surveyed various mapping and routing algorithms from Mapbox, Google, TomTom that are used by car manufacturers, such as BMW, Tesla, Hyundai, and Nissan. Many EV routing algorithms employ chronological shortest-path tree algorithms towards the same goal.

We devised a combinatorial optimization algorithm and a fixed storage graph topology construction for the graph road network of the continental USA. We re-purposed Kinetica’s existing Dijkstra solver to reduce the computational cost of many shortest path solves involved in the algorithm to meet SLA requirements. Our solution does not use bi-directional A-star Dijkstra between the prospective stations, and does not require finding a pivot location between charging locations.

An adaptive and light weight spatial search structure is also devised for finding a set of prospective stations at each charging location using uniform bins and double link associations. The entire algorithm is then implemented as yet another multi-threaded at-scale graph solver within the suite of Kinetica-Graph analytics, exposed as a restful API endpoint and operable within SQL.

This capability is demonstrated with example trips. See the results and get the details in the full paper: “Optimal routing algorithm for trips involving thousands of EV-charging stations using Kinetica-Graph” (PDF)