de Sousa, Andrea Vaz2024-07-132024-07-132023-11de Sousa, Andrea Vaz. (2023). The Development and Application of a Hybrid Metaheuristic Clustering Algorithm to the Capacitated Vehicle Routing Problem. [Master's dissertation, University of the Witwatersrand, Johannesburg]. WIReDSpace. https://hdl.handle.net/10539/38914https://hdl.handle.net/10539/38914A research report submitted to the Faculty of Engineering and the Built Environment, University of the Witwatersrand, Johannesburg, in partial fulfilment of the requirements for the degree of Master of Science in Engineering, in the School of Mechanical, Industrial and Aeronautical Engineering, in 2023.The Vehicle Routing Problem (VRP) is an important combinatorial optimization problem in the field of operations research that remains a significant challenge for distribution and logistics operations globally. This research is concerned with a relatively simple variation of the VRP referred to as the Capacitated Vehicle Routing Problem (CVRP), and it focuses on the integration of metaheuristics into its solution. A Genetic Algorithm (GA) was selected and integrated into several CVRP solutions with various configurations of the algorithm. Additionally, a hybrid implementation was proposed, which augments the GA by incorporating conventional heuristics to seed the initial population with “good” solutions. The proposed hybrid solution was the best performing solution evaluated and yielded results comparable to the best-known solution for the smaller datasets. However, the solution quality with respect to the best known solutions decreased with an increase in the size of the problem. This may be attributed to premature termination of the algorithm. Overall, the solutions evaluated were not able to match the best-known solution for each dataset, however successive improvements in the results suggest that GAs are effective at solving the CVRP. Moreover, combining metaheuristics with other methods is also an effective strategy for improving the efficiency of the solution space exploration.en©2023 University of the Witwatersrand, JohannesburgGenetic Algorithm (GA)Vehicle Routing Problem (VRP)MetaheuristicsCapacitated Vehicle Routing Problem (CVRP)Multi-Depot Vehicle Routing ProblemCTDUCTDDissertationUniversity of the Witwatersrand, Johannesburg