Petal-shaped clustering for the capacitated vehicle routing problem
No Thumbnail Available
Date
2018
Authors
Bruwer, Frances
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this research report, k-medoid (petal-shaped) clustering is modelled and evaluated for the Capacitated Vehicle Routing Problem (CVRP). To determine routes, an existing metaheuristic, termed the Ruin and Recreate method, is applied to each generated cluster. Results are benchmarked to that 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 Vehicle Routing Problems (VRPs). The results show that k-medoid outperforms the benchmark method for most instances of the test datasets, although the CVRP without any predefined clusters still provide solutions that are closer to optimal. Clustering remains a reliable distribution management tool and reduces processing requirements of large scale CVRPs.
Description
A research report submitted to the Faculty of Engineering and the Built
Environment, University of the Witwatersrand, in partial fulfillment of the
requirements for the degree of Master of Science in Engineering.
Johannesburg, February 2018
Keywords
Citation
Bruwer, Frances (2018) Petal-shaped clustering for the capacitated vehicle routing problem, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/25890>