Using Grey Wolf Algorithm to Solve the Capacitated Vehicle Routing Problem

• Published in: IOP conference series. Materials Science and Engineering 2015-05, Vol.83 (1), p.12014
• Main Authors: Korayem, L, Khorsid, M, Kassem, S S
• Format: Article
• Language: English
• Subjects: Algorithms; Cluster analysis; Clustering; Clusters; Constraints; Customers; Optimization; Route planning; Route selection; Vector quantization; Vehicle routing; Vehicles
• ISSN: 1757-8981; 1757-899X
• DOI: 10.1088/1757-899X/83/1/012014

The capacitated vehicle routing problem (CVRP) is a class of the vehicle routing problems (VRPs). In CVRP a set of identical vehicles having fixed capacities are required to fulfill customers' demands for a single commodity. The main objective is to minimize the total cost or distance traveled by the vehicles while satisfying a number of constraints, such as: the capacity constraint of each vehicle, logical flow constraints, etc. One of the methods employed in solving the CVRP is the cluster-first route-second method. It is a technique based on grouping of customers into a number of clusters, where each cluster is served by one vehicle. Once clusters are formed, a route determining the best sequence to visit customers is established within each cluster. The recently bio-inspired grey wolf optimizer (GWO), introduced in 2014, has proven to be efficient in solving unconstrained, as well as, constrained optimization problems. In the current research, our main contributions are: combining GWO with the traditional K-means clustering algorithm to generate the 'K-GWO' algorithm, deriving a capacitated version of the K-GWO algorithm by incorporating a capacity constraint into the aforementioned algorithm, and finally, developing 2 new clustering heuristics. The resulting algorithm is used in the clustering phase of the cluster-first route-second method to solve the CVR problem. The algorithm is tested on a number of benchmark problems with encouraging results.