PARTICLE SWARM OPTIMIZATION TO IMPROVE A HYBRID HEURISTIC ALGORITHM FOR SOLVING CAPACITATED VEHICLE ROUTING PROBLEM

Document Type : Original Article

Authors

1 Information Systems Department, Faculty of Computers and Information Sciences, Mansoura University-Egypt

2 Computer Engineering and Systems Department, Faculty of Engineering , Mansoura University-Egypt

Abstract

Capacitated Vehicle Routing Problem is the most elementary version of the vehicle routing problem, where it represents a generalization of vehicle routing problems. It is an important problem in the fields of transportation, distribution and logistics which involves finding a set of routes, starting and ending at a depot, that together cover a set of customers. The proposed methodology in this research was based on Cluster-First Route-Second method. There are two proposed hybrid algorithms used to implement that methodology, the Sweep-Nearest Neighbour algorithm and the Sweep-Particle Swarm Optimization algorithm. The Particle Swarm Optimization algorithm was used instead of Nearest Neighbour algorithm to enhance the performance in finding the shortest routes. The two hybrid proposed algorithms were applied in a real case study and the results were compared. From the experimental results, it observed that particle swarm optimization was added more enhancement for finding the best route with the minimum travelling costs.