An application of a two-level genetic search for the soft-clustered vehicle routing problem

We propose a two-level Hybrid Genetic Search (HGS) for the Soft-Clustered Vehicle Routing Problem (SoftCluVRP), an extension of the Capacitated VRP where customers are grouped into clusters that vehicles can enter and exit multiple times to reduce costs. The method decomposes the problem into cluster-level and node-level subproblems, each optimized via tailored local searches. Node-level routes are refined by solving a traveling salesman problem for each route, enhanced by seven well-known neighborhoods. Cluster-level optimization represents clusters as sequences of consecutive visits to their nodes, modeled with a newly introduced sequence chromosome and optimized through a sequence-based best-insertion strategy. A polar sector-based inter-route swap further boosts efficiency. Tested on benchmark instances, the algorithm achieves competitive results, setting 191 new upper bounds across 232 cases and demonstrating strong convergence behavior and scalability. Code available at: https://github.com/vlatorre847/HGS-SoftCluVRP.