A route-based algorithm for the electric vehicle routing problem with multiple technologies

We consider a variant of the electric vehicle routing problem: a fleet of identical vehicles of limited capacity needs to visit a set of customers with given demands. An upper limit is imposed on the duration of the routes. Vehicles have limited autonomy: they may need to stop en-route at recharge stations. Recharges can be partial and multiple recharge technologies are available at stations, providing energy at different costs and different recharge rates.We present a new a branch-and-price algorithm, that relies on an extended formulation having one variable for each possible depot-to-depot route of each vehicle, implicitly encoding also recharge plans. We design ad-hoc pricing algorithms, which exploit a novel encoding of recharge plans, allowing for efficient bi-directional dynamic programming techniques.Extensive computational results show our approach to clearly outperform previous ones from the literature, being able to solve instances with up to 30 customers, 5 stations, 7 vehicles and 3 technologies to proven optimality within some minutes on a standard PC.

Automated summary

This article presents a variant of the electric vehicle routing problem, where a fleet of identical vehicles with limited capacity needs to visit customers with given demands. The vehicles have limited autonomy and may need to recharge en-route at stations offering different recharge technologies. The article introduces a new branch-and-price algorithm that outperforms previous methods from the literature and is capable of solving instances with up to 30 customers, 5 stations, 7 vehicles, and 3 technologies within a few minutes on a standard PC.