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

Edward Lam, Guy Desaulniers, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Article number105870
Number of pages16
JournalComputers and Operations Research
Volume145
DOIs
Publication statusPublished - Sep 2022

Keywords

  • Conflict-driven clause learning
  • Dantzig–Wolfe decomposition
  • Logic-based Benders decomposition
  • Scheduling
  • Synchronization
  • Vehicle routing problem

Cite this