Branch-and-cut-and-price for the Electric Vehicle Routing Problem with Time Windows, Piecewise-Linear Recharging and Capacitated Recharging Stations. (September 2022)

• Record Type: Journal Article
• Authors: Lam, Edward; Desaulniers, Guy; Stuckey, Peter J.
• Is Part Of: Computers & operations research. Volume 145(2022)
• Publication Date: 2022-09
• Subjects: Vehicle routing problem -- Synchronization -- Scheduling -- Dantzig–Wolfe decomposition -- Logic-based Benders decomposition -- Conflict-driven clause learning; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105870
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The Electric Vehicle Routing Problem with Time Windows, Piecewise-Linear Recharging and Capacitated Recharging Stations aims to design minimum-cost routes for a fleet of electric vehicles subject to intra-route and inter-route constraints. Every vehicle is equipped with a rechargeable battery that depletes while it transports goods along its route. A vehicle must detour to a recharging station to recharge before draining its battery. To approximate a real recharging process, the amount of energy restored is modeled as a piecewise-linear function of the time spent recharging. Furthermore, each station has a small number of chargers, and hence, when and where a vehicle can recharge must be scheduled around the availability of a charger. This interaction between vehicles does not appear in classical vehicle routing problems and motivates the development of new methods that can exploit the joint routing and scheduling structure. This paper proposes a branch-and-cut-and-price algorithm that designates the routing to integer programming using Dantzig–Wolfe decomposition and the scheduling to constraint programming using logic-based Benders decomposition. Experimental results indicate that this hybrid method solves 34% of the instances with 100 customers. Highlights: This paper considers the routing of electric vehicles and their recharging en route. Recharging the batteries of the vehicles is governed by a piecewise-linear function. Vehicles must recharge at stations with a limited number of chargers. Hence, the vehicles must be scheduled around the availability of a charger. The problem is tackled using a branch-and-cut-and-price algorithm. The algorithm decomposes the routing to integer programming and the scheduling to constraint programming. Results show that this hybrid algorithm solves instances with up to 100 customers.