A Comparison of Metaheuristic Methods for the Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard combinatorial optimization problem with important applications in logistics and distribution systems. Although numerous advanced approaches have been proposed in recent years, systematic benchmarking of classical metaheuristic algorithms under a unified experimental framework remains limited. This study evaluates the performance and trade-offs of four well-known metaheuristics: Hill Climbing (HC), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Genetic Algorithms (GA). All methods are implemented within the same computational environment and assessed on benchmark CVRP instances, using the CPLEX exact solver as a reference for global optimality. The results indicate that ACO achieves the smallest optimality gaps and often approaches optimal solutions, at the cost of higher computational effort. PSO strikes a favorable balance between solution quality and runtime across the tested instances, whereas HC delivers very fast solutions but degrades as problem complexity increases. GA exhibits higher variability and less competitive performance under the selected parameter settings. Overall, this comparative analysis highlights the strengths and limitations of classical metaheuristics and establishes a reproducible baseline for future research, including hybrid and learning-assisted approaches for scalable vehicle routing optimization.