Bruwer, Frances2018-10-232018-10-232018Bruwer, Frances (2018) Petal-shaped clustering for the capacitated vehicle routing problem, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/25890>https://hdl.handle.net/10539/25890A 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 2018In 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.Online resource (52 leaves)enVehicle routing problemTransportation problemsThesis