Self-Competition Particle Swarm Optimization Algorithm for the Vehicle Routing Problem With Time Window

Abstract

The vehicle routing problem with time windows (VRPTW) is a well-known NP-Hard combinatorial optimization problem, which is frequently encountered in transportation and logistics scenarios. When traditional algorithms solve this problem, there are some problems, such as slow convergence speed. In this paper, a Self-competitive Particle Swarm Optimization (ScPSO) algorithm is proposed, which regulates the learning direction of the next generation of particles based on their degree of self-competition. When the particle’s self-competition degree is low, it is compelled to learn from the individual optimal solution using the self-competition selection probability, thereby achieving rapid convergence. ScPSO uses the nonlinear inertia weight adaptive strategy to adjust the search preference in the search process, and it can balance the relationship between exploration and exploitation. Meanwhile, Random greedy heuristic selection and variable neighborhood search strategies are used in initial solution construction and constraint restriction. Finally, ScPSO is tested on 56 Solomon 100-customers benchmark problems and compared with four state-of-the-art VRPTW algorithms and best-known solutions reported on Solomon’s webpage.The running results of the ScPSO algorithm are better than four state-of-the-art VRPTW algorithms and best-known solutions reported on Solomon’s webpage. The experimental results show that ScPSO can solve VRPTW problems efficiently.

Keywords

• Particle swarm optimization
• self-competitive learning strategy
• random greedy heuristic selection strategy
• variable neighborhood search strategy