Electronic Theses and Dissertations (Masters)

Permanent URI for this collection

https://hdl.handle.net/10539/37972

Browse

Browsing Electronic Theses and Dissertations (Masters) by Keyword "Metaheuristics"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    The Development and Application of a Hybrid Metaheuristic Clustering Algorithm to the Capacitated Vehicle Routing Problem
    (University of the Witwatersrand, Johannesburg, 2023-11) de Sousa, Andrea Vaz; Bührmann, Joke
    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.