Solving heterogeneous vehicle routing problems using decomposition and set covering

In practice, last-mile delivery carriers must efficiently transport goods to a large number of customers using a limited fleet of various vehicle types. Most academic research, however, focuses on developing solution algorithms for small- to mid-scale vehicle routing problems (VRPs), typically assuming a single vehicle type with unrestricted availability. This study introduces an iterative matheuristic framework that leverages decomposition and set covering methods to address large-scale VRPs with a heterogeneous fleet (HVRP). In every iteration, those instances are decomposed into smaller, homogeneous VRPs using customer- and routebased unsupervised machine learning. The resulting subproblems are solved by existing routing software, and the created routes are collected in a route pool. A solution to the original problem is found by solving the set covering problem. Computational experiments demonstrate the framework’s ability to produce highquality solutions across multiple HVRP variants within reasonable computing time, including several new best-known solutions for academic benchmark instances.