Electric vehicle routing problem with machine learning for energy prediction

Routing electric commercial vehicles requires taking into account their limited driving range, which is affected by several uncertain factors such as traffic conditions.  presents the time-dependent Electric Vehicle Routing Problem with Chance-Constraints (EVRP-CC) and partial recharging.

Electric vehicles are currently seen as one of measures to reduce the negative impact of transport on the environment. But despite the latest technology developments, they are still limited by their battery capacities. Their batteries are heavy, big, and costly, which usually translates into a limited driving range. Furthermore, charging infrastructure is more scarcely available and it takes a longer time to charge the vehicles compared to re-fueling diesel. As a consequence, especially for commercial vehicles, more careful planning of the routes is needed. Accurate energy consumption prediction is required while routing in order to determine if charging stops are needed. 

Routing method

The routing method is divided into two stages, where the first finds the best paths and the second optimizes the routes. A probabilistic Bayesian machine learning approach is proposed for predicting the expected energy consumption and variance for the road links, paths, and routes. Hence it is possible to consider the uncertainty in energy demand by planning charging within a confidence interval.

Energy estimation

Predicting energy demand is a quite complex problem since it depends on many different parameters such as road topography, the total weight of the vehicle, and payload. It also depends on uncertain factors such as driving behavior and speed, which is affected by the traffic density during different times of the day. Therefore it is important to not only estimate the expected energy consumption but also its possible variation.

The energy estimation is validated with data from electric buses driving a public transport route in Gothenburg-Sweden as well as with realistic simulations for 24 hours traffic in the city of Luxembourg connected to a high-fidelity vehicle model. Routing solutions are compared with a deterministic formulation of the problem similar to the ones found in the literature. The results indicate high accuracy for the energy prediction as well as energy savings and more reliability for the routes.

The precision of energy consumption estimation resulted in a Mean Absolute Percentage Error of less than 6%, even with imprecise speed predictions. The prediction quickly gets improved after just a few routes being driven from the depot to the target customer area. The maximum error also gets significantly reduced. Even using uninformative priors the posterior tends to a good fit after learning. The variance predicted by the model tends to narrow down as it learns from more data, which indicates that it gets better precision over time. In the experiments, no actual consumption was outside the 95% confidence interval of the prediction. 

Source: Rafael Basso, Balázs Kulcsár, Ivan Sanchez-Diaz, Electric vehicle routing problem with machine learning for energy prediction, Transportation Research Part B: Methodological, Volume 145, 2021

Leave a Reply

Your email address will not be published. Required fields are marked *