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

Serap Ercan Comert, Harun Resit Yazgan, Sena Kır and Furkan Yener

International Journal of Procurement Management, 2018, vol. 11, issue 4, 399-419

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. (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.inderscience.com/link.php?id=92766 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijpman:v:11:y:2018:i:4:p:399-419

Access Statistics for this article

More articles in International Journal of Procurement Management from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().