Capacitated Vehicle Routing Problem Using Algebraic Particle Swarm Optimization with Simulated Annealing Algorithm
Mohammad Sajid, Jagendra Singh, Ranjit Rajak
Abstract
The capacitated vehicle routing problem (CVRP) plays a significant role in the delivery networks, the slight improvement of which leads to substantial monetary savings and improved customer satisfaction. Various continuous-valued optimization algorithms such as particle swarm optimization (PSO), Harris-Hawks optimization, and Sine-Cosine algorithm have been employed to optimize the CVRP. However, the CVRP is an inherently discrete problem, and the application of continuous-valued optimization algorithms requires a conversion method to decode the continuous-valued solution in discrete form. Due to cardinality, an infinite number of continuous-valued solutions can be mapped to a single discrete solution, leading to wastage of computational efforts. This work proposes an algebraic PSO with simulated annealing (SA) (APS) algorithm to address the CVRP to make the total traveled distance minimum. APS algorithm consisting of an algebraic version of PSO and SA works on the permutations and employs an algebraic composition operator to realize the different operations of PSO. The well-known 27 CVRP benchmark instances have been used to evaluate the consistency and performance of the APS and random-key PSO (RK-PSO) algorithms. The simulation results show that the proposed APS algorithm is effective compared to the RK-PSO algorithm.