A Hybrid Metaheuristics Based on an Improved Set-Based Particle Swarm Optimization and a Self-Organizing Map for the Capacitated Vehicle Routing Problem

Abstract

The capacitated vehicle routing problem (CVRP) is a representative NP-hard combinatorial optimization problem with broad applications in logistics and transportation. This paper proposes a hybrid metaheuristic, termed SPSOM-CVRP, which integrates an improved set-based particle swarm optimization (SPSO) with a self-organizing map (SOM). In SPSOM-CVRP, the improved SPSO is responsible for constructing feasible CVRP solutions, whereas the SOM performs route-level refinement to improve solution quality. To strengthen exploration, when the personal best of a particle remains unchanged for a predefined number of generations, two new learning exemplars are randomly reassigned to the particle. To enhance exploitation while avoiding excessive computational cost, SOM-based route optimization is activated only when the global best solution stagnates and is applied to selected elite solutions. In this manner, particle-level and population-level stagnation information is jointly employed to coordinate exploration and exploitation. Experimental studies on three benchmark datasets demonstrate that SPSOM-CVRP achieves competitive solution quality with relatively low computational cost. In addition, the proposed method obtains several promising route configurations, including solutions with shorter travel distances than previously reported results under modified route numbers. It should be noted that the proposed algorithmic configuration is empirically motivated; its effectiveness is demonstrated on the selected CVRP benchmark suites and the specific route-number settings under test, rather than being claimed as a universally optimal solution for all possible CVRP instances or all combinatorial optimization problems.