This dissertation is submitted in fulfillment of the requirements for the degree of Master of Science, University of the Witwatersrand, Johannesburg, August 2018 / Abstract. The vehicle routing problem is a common combinatorial optimization, which is modelled to determine the best set routes to deploy a fleet of vehicles to customers, in order to deliver or collect goods efficiently. The vehicle routing problem has rich applications in design and management of distribution systems. Many combinatorial optimization algorithms which have been developed, were inspired through the study of vehicle routing problems. Despite the literature on vehicle routing problems, the existing techniques fail to perform well when n (the number of variables defining the problem) is very large, i.e., when n > 50. In this dissertation, we survey exact and inexact methods to solve large problems. Our attention is on the capacitated vehicle routing problem. For exact methods, we investigate only the Cutting Planes method which has recently been used in conjunction with other combinatorial optimization problem algorithms (like the Branch and Bound method) to solve large problems. In this investigation, we study the polyhedral structure of the capacitated vehicle routing problem. We compare two metaheuristics, viz., the Genetic Algorithm and the Ant Colony Optimization. In the genetic algorithm, we study the effect of four different crossover operators. Numerical results are presented and conclusion are drawn, based on our findings. / XL2019
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/26894 |
| Date | January 2018 |
| Creators | Qhomane, Hlompo Napo |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | Online resource (vii, 91 leaves), application/pdf, application/pdf |
Page generated in 0.0019 seconds