A cluster first-route second approach for a capacitated vehicle routing problem: a case study

In this study, a capacitated vehicle routing problem (CVRP) which dealt with minimum distance routes for vehicles that serve customers having specific demands from a common warehouse under a capacity constraint. This problem is NP hard. We solved the problem in a hierarchical way (i.e., cluster-first route-second method). Firstly, customers were clustered using three different clustering algorithms; K-means, K-medoids and random clustering with considering a vehicle capacity. Secondly, routing problems for each cluster were solved using a branch and bound algorithm. The proposed solution strategy was employed on a case study in a supermarket chain. Results of numerical investigation were presented to illustrate the effectiveness of the algorithms using paired sample t tests. The results illustrated that the K-medoids algorithm provided better solution than the others.