Route splitting and adaptive mutation in genetic algorithms for the capacitated vehicle routing problem

Abstract

The capacitated vehicle routing problem (CVRP), where vehicle capacity constraints limit the load carried per route for multiple vehicles, is addressed using an optimized genetic algorithm (GA) framework. This work focuses on finding the best configuration of GA by systematically evaluating 12 distinct GA variants, differing in adaptive mutation rates and route-splitting strategies. The framework integrates adaptive mutation rates and novel route-splitting approaches—greedy, dynamic programming (DP), and heuristic—to enhance computational efficiency and solution quality. Experiments on six CVRP instances of varying complexity, encompassing differences in problem size, vehicle capacity, and geographical distribution, demonstrate the heuristic approach’s effectiveness. It achieves solutions within 2%–5% of the optimal cost of DP while being 3–4 times faster. Adaptive techniques reduce costs by up to 20% compared to standard GAs and heuristics. The framework’s scalability is evident in large-scale instances such as the 200-customer case, where the heuristic method balances cost (414.17) and computation time (0.003 seconds). The developed software is openly available at GitHub, providing a robust tool for addressing practical logistics challenges.