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.



Dario Bezzi, Alberto Ceselli, Giovanni Righini, A route-based algorithm for the electric vehicle routing problem with multiple technologies, Transportation Research Part C: Emerging Technologies, Volume 157, 2023, 104374, ISSN 0968-090X, https://doi.org/10.1016/j.trc.2023.104374.