An Evolutionary Multiobjective Route Grouping-Based Heuristic Algorithm for Large-Scale Capacitated Vehicle Routing...

The capacitated vehicle routing problem (CVRP) has been extensively investigated in the past years due to their applications in a variety of real-world scenarios. However, it is still very challenging for most existing algorithms to tackle large-scale CVRPs (LSCVRPs), namely, CVRPs with hundreds or thousands of customers. In this article, we propose a heuristic algorithm, called EMRG-HA, to address LSCVRPs based on the framework of divide and conquer, where an evolutionary multiobjective route grouping (EMRG) method is suggested to decompose an LSCVRP into small subcomponents. The suggested EMRG adopts a multiobjective evolutionary algorithm for route grouping by simultaneously optimizing three well-defined objectives, intragroup distance, intergroup distance, and intergroup balance in size, which can obtain a set of promising decompositions of LSCVRPs. Based on the EMRG, a local search method is suggested to improve the quality of routes in groups, where only routes in one group instead of in all groups are improved which is determined according to the average serving cost of routes in each group. The performance of the proposed EMRG-HA is verified on 42 test instances from three popular benchmark suites. The experimental results show that the EMRG-HA is superior over eight existing algorithms on most test instances of LSCVRPs, in terms of both computational efficiency and solution quality.