Vehicle Routing Problem: A Performance Comparison of Hybrid Evolutionary Algorithm with Local Search Strategies

Abstrak

The Vehicle Routing Problem (VRP), one of the most challenging problems in logistics and transport, has been an area of optimization solutions to minimize costs and optimize the operational process. This study examines a hybrid of metaheuristic algorithms that are combinations of the Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA), and Local Search (LS) to tackle various complexities of VRP. The hybrid approach offered better exploration and exploitation by integrating global explorations with GA and PSO and local refinement with SA and LS. The performance was performed using real datasets and generated randomly with problem sizes ranging from 9 to 100 customers. PSO-LS and GA-LS are LS-based hybrids that produce lower standard deviations, showing a stable and consistent result for small to medium problems. For example, PSO-LS computed 3.31 for 9 customers and 5.76 for 50 customers. However, SA-based hybrids, such as PSO-SA and GA-SA, presented more variability, with SA-GA reaching 100 customers as much as 7.83. These findings highlight key trade-offs while optimizing VRP between stability, efficiency, and problem scale.