The Development and Application of a Hybrid Metaheuristic Clustering Algorithm to the Capacitated Vehicle Routing Problem
Date
2023-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of the Witwatersrand, Johannesburg
Abstract
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.
Description
A 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.
Keywords
Genetic Algorithm (GA), Vehicle Routing Problem (VRP), Metaheuristics, Capacitated Vehicle Routing Problem (CVRP), Multi-Depot Vehicle Routing ProblemCTD, UCTD
Citation
de 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/38914