Qhomane, Hlompo Napo2019-05-142019-05-142018Qhomane, Hlompho Napo (2018) Comparison of techniques for solving vehicle routing problems, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/26894>https://hdl.handle.net/10539/26894This dissertation is submitted in fulfillment of the requirements for the degree of Master of Science, University of the Witwatersrand, Johannesburg, August 2018Abstract. 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.Online resource (vii, 91 leaves)enVehicle routing problemTransportation problems (Programming)Delivery of goods--Mathematical modelsThesis