Solving Capacitated Vehicle Routing Problem Using Variant Sweep and Swarm Intelligence

10.6180/jase.2017.20.4.13

M. A. H. Akhand；Zahrul Jannat Peya；Tanzima Sultana；M. M. Hafizur Rahman

Capacitated Vehicle Routing Problem ； Sweep Clustering ； Genetic Algorithm ； Ant Colony Optimization ； Producer-scrounger Method ； Velocity Tentative Particle Swarm Optimization

淡江理工學刊

20卷4期（2017 / 12 / 01）

511 - 524

英文

Capacitated vehicle routing problem (CVRP) is a real life constraint satisfaction problem in which customers are optimally assigned to individual vehicles (considering their capacity) to keep total travel distance of the vehicles as minimum as possible while serving customers. Various methods are used to solve CVRPin last few decades, among them the most popular way is splitting the task into two different phases: assigning customers under different vehicles and then finding optimal route of each vehicle. Sweep clustering algorithm is well studied for clustering nodes. On the other hand, route optimization is simply a traveling salesman problem (TSP) and a number of TSP optimization methods are applied for this purpose. This study investigates a variant of Sweep algorithm for clustering nodes and different Swarm Intelligence (SI) based methods for route generation to get optimal CVRP solution. In conventional Sweep algorithm, cluster formation starts from smallest angle and consequently advances to consider all the nodes. In variant Sweep of this study, cluster formation are considered from different starting angles. On the other hand, four TSP optimization methods including recent ones are considered for route optimization. The experimental results on a large number of benchmark CVRPs revealed that clustering with proposed variant Sweep and route optimization with Velocity Tentative Particle Swarm Optimization is able to produce better solution. Finally, the proposed mythology is found to achieve better solutions for several CVRPs when compared with prominent existing methods.