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>

Collections

Endorsement

Review

Supplemented By

Referenced By