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.