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

• Record Type: Journal Article
• Authors: Comert, Serap Ercan; Yazgan, Harun Resit; Kır, Sena; Yener, Furkan
• Is Part Of: International journal of procurement management. Volume 11:Number 4(2018)
• Page Start: 399
• Page End: 419
• Publication Date: 2018
• Subjects: capacitated vehicle routing problem -- CVRP -- k-means clustering algorithm -- K-medoids clustering algorithm -- random clustering algorithm -- branch and bound algorithm; Industrial procurement -- Management -- Periodicals; Industrial procurement -- Electronic information resources -- Periodicals; Business logistics -- Periodicals; 658.7205
• Languages: English
• ISSNs: 1753-8432

Abstract

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.