Open AccessK-MEDOID PETAL-SHAPED CLUSTERING FOR THE CAPACITATED VEHICLE ROUTING PROBLEM
Author(s) -
Jacoba H. Bührmann,
Frances Bruwer
Publication year - 2021
Publication title -
south african journal of industrial engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.225
H-Index - 16
eISSN - 2224-7890
pISSN - 1012-277X
DOI - 10.7166/32-3-2610
Subject(s) - medoid , cluster analysis , vehicle routing problem , benchmark (surveying) , computer science , cluster (spacecraft) , data mining , k means clustering , mathematics , routing (electronic design automation) , artificial intelligence , geography , computer network , geodesy , programming language
In this research, k-medoid clustering is modelled and evaluated for the capacitated vehicle routing problem (CVRP). The k-medoid clustering method creates petal-shaped clusters, which could be an effective method to create routes in the CVRP. To determine routes from the clusters, an existing metaheuristic — the ruin and recreate (R&R) method — is applied to each generated cluster. The results are benchmarked to those of a well-known clustering method, k-means clustering. The performance of the methods is measured in terms of travel cost and distance travelled, which are well-known metrics for the CVRP. The results show that k-medoid clustering method outperforms the benchmark method for most instances of the test datasets, although the CVRP without any predefined clusters still provides solutions that are closer to optimal. Clustering remains a reliable distribution management tool and reduces the processing requirements of large-scale CVRPs.