Electric vehicles are seen as a pragmatic way of reducing emissions. In freight transportation, they prove to be appealing also in terms of costs, if proper planning algorithms are designed. 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 of given demand. Vehicles have limited batteries and limited time: they need to stop en-route to recharge stations. Our variant has two distinguishing features: recharges can be partial and multiple recharge technologies are available at stations, providing energy at different costs and different recharge rates. We propose a novel exact algorithm. It relies on an extended formulation, having one variable for each possible depot-to-depot route of each vehicle, implicitly encoding also recharge plans. We optimize it by branch-and-price. We design ad-hoc pricing algorithms, which exploit a special 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.
Citation
Manuscript Draft Number TRC-22-00048. Submitted to Transportation Research Part C, January 7th 2022. Under review.
Article
View A Route-Based Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies