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.

https://www.sciencedirect.com/science/article/pii/S0968090X23003649