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

Authors: Serap Ercan Comert; Harun Resit Yazgan; Sena Kır; Furkan Yener

Addresses: Engineering Faculty, Department of Industrial Engineering, Sakarya University, Sakarya, Turkey ' Engineering Faculty, Department of Industrial Engineering, Sakarya University, Sakarya, Turkey ' Engineering Faculty, Department of Industrial Engineering, Sakarya University, Sakarya, Turkey ' Engineering Faculty, Department of Industrial Engineering, Sakarya University, Sakarya, Turkey

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.

Keywords: capacitated vehicle routing problem; CVRP; k-means clustering algorithm; K-medoids clustering algorithm; random clustering algorithm; branch and bound algorithm.

DOI: 10.1504/IJPM.2018.092766

International Journal of Procurement Management, 2018 Vol.11 No.4, pp.399 - 419

Received: 06 Jan 2017
Accepted: 25 Mar 2017
Published online: 29 Jun 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article