Operations Research 2025
Abstract Submission

250. Branch-and-Cut POPMUSIC for the Electric Vehicle Routing Problem with Time Windows

Invited abstract in session TA-11: Vehicle Routing, stream Heuristics, Metaheuristics and Matheuristics.

Thursday, 8:45-10:15
Room: U2-200

Authors (first author is the speaker)

1. Lelisa Bijiga
Institute of Operations Research (IOR), Karlsruhe Institute of Technology (KIT)
2. John Warwicker
Karlsruhe Institute of Technology
3. Steffen Rebennack
Institute of Operations Research (IOR), Karlsruhe Institute of Technology (KIT)

Abstract

Advancements in computer hardware and commercial software have enabled the use of branch-and-cut (BC) methodologies to address medium-scale vehicle routing problems (VRPs). Despite the introduction of efficient heuristics in the literature, tailoring these approaches to suit various VRP variants, such as the Electric Vehicle Routing Problem with Time Windows (EVRPTW), remains a difficult task. EVRPTW is an extension of the classic VRP with Time Windows, in which internal combustion engine vehicles are replaced by electric vehicles. In this study, we explore the potential of combining BC techniques with decomposition strategies through constrained k-means clustering. We develop a POPMUSIC matheuristic that only relies on BC, which can be implemented using commercial optimisation software like Gurobi. Our methodology begins by decomposing the customers into geographical-based clusters, thereby imposing a manageable size for the subproblems and facilitating the efficient application of BC. These subproblems are solved iteratively to derive a comprehensive solution. We adapt new battery infeasibility inequalities and incorporate them into Gurobi, along with capacity cuts and default cuts, to tighten the linear programming relaxation of the MILP model and show that it can improve the solution quality through extensive computational experiments. We demonstrate the effectiveness of our approach on known benchmark instances of EVRPTWs and compare it with state-of-the-art exact solutions. Our result shows that the approach achieves comparable or better performance, especially on larger problems.

Keywords

Status: accepted

Back to the list of papers