A HYBRID CIAM-GA ALGORITHM BASED ON CLUSTER INITIALIZATION AND ADAPTIVE MEMETIC SEARCH FOR THE CAPACITATED VEHICLE ROUTING PROBLEM

Abstract

Abstract

The paper addresses the Capacitated Vehicle Routing Problem (CVRP). Using the giant-tour solution representation with greedy route decoding, threegenetic-algorithm (GA) enhancement mechanisms are implemented and systematically compared via ablation: k -means-based cluster-first populationinitialization, memetic refinement of elite solutions via 2-opt/Or-opt local search, and diversity-adaptive mutation controlled by the population fitnesscoefficient of variation. Local search is shown to be the dominant contributor (22 – 56 % versus a baseline GA), cluster initialization provides a notableindependent effect (19 – 46 %), while the original adaptive-mutation trigger yields no benefit because its activation condition is rarely met withouta mechanism that actively reduces population diversity. Based on this diagnosis, an alternative mutation-adaptation trigger is proposed, based on stagnation of the best-found solution rather than population diversity. Testing on 15 independent runs per problem size ( n  30 , 50 , 75 ) with a Wilcoxonsigned-rank test shows a statistically significant ( p  0.01 ) improvement of the redesigned trigger over local search without adaptation on 2 of3 problem sizes and over the original diversity trigger on 1 of 3 sizes; the remaining comparisons do not reach significance. Additional validation onthree standard Augerat Set A benchmarks with known optimal solutions ( A  n32  k5 , A  n60  k9 , A  n62  k8 ) confirms the qualitative patternfound on synthetic data: the gap to the best known solution for the full CIAM-GA with the stagnation trigger is 7.2 – 9.5 %, which is no worse thanthat of any other compared configuration and is better in some cases on all three benchmarks. The study demonstrates that component synergy claimedin parts of the VRP metaheuristic-hybridization literature requires verification through ablation and statistical testing across multiple independent datasources.