Optimization of capacitated vehicle routing problem using Producer-Scrounger Method

Vehicle Routing Problem (VRP) has become an integral part in logistic operations which determines optimal routes for several vehicles to serve customers. The basic version of VRP is Capacitated VRP (CVRP) which considers equal capacities for all vehicles. The most popular way of solving CVRP is splitting the task into two different phases: firstly, assigning customers under different vehicles and secondly, finding optimal route of each vehicle. Sweep clustering algorithm is well studied for clustering customer nodes. On the other hand, route optimization is simply a traveling salesman problem (TSP) and a number of TSP optimization methods are investigated for this purpose. This study investigates a variant of Sweep algorithm for clustering nodes and Producer-Scrounger Method (PSM), the recent swarm intelligence method for TSP, for route generation to get optimal CVRP solution. In conventional Sweep algorithm, cluster formation starts from 00 and consequently advance toward 3600 to consider all the nodes. In variant Sweep, cluster formation starts from a user defined angle. We have compared the outcomes of the proposed method with other related methods including recent study on a suite of benchmark CVRPs. The experimental results revealed that proposed method outperformed other methods in solving benchmark CVRPs.