An Improved Particle Swarm Optimization for a Class of Capacitated Vehicle Routing Problems

Abstract

Vehicle Routing Problem (VRP) is addressed to a class of problems for determining a set of vehicle routes, in which each vehicle departs from a given depot, serves a given set of customers, and returns back to the same depot. On the other hand, simultaneous delivery and pickup problems have drawn much attention in the past few years due to its high usage in real world cases. This study, therefore, considered a Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pickup (VRPTWSDP) and formulated it into a mixed binary integer programming. Due to the NP-hard nature of this problem, we proposed a variant of Particle Swarm Optimization (PSO) to solve VRPTWSDP. Moreover, in this paper we improve the basic PSO approach to solve the several variants of VRP including Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pickup (VRPTWSDP), Vehicle Routing Problem with Time Windows (VRPTW), Capacitated Vehicle Routing Problem (CVRP) as well as Open Vehicle Routing Problem (OVRP). In proposed algorithm, called Improved Particle Swarm Optimization (IPSO), we use some removal and insertion techniques and also combine PSO with Simulated Annealing (SA) to improve the searching ability of PSO and maintain the diversity of solutions. It is worth mentioning that these algorithms help to achieve a trade-off between exploration and exploitation abilities and converge to the global solution. Finally, for evaluating and analyzing the proposed solution algorithm, extensive computational tests on a class of popular benchmark instances, clearly show the high effectiveness of the proposed solution algorithm.