Comparison of techniques for solving vehicle routing problems
Qhomane, Hlompo Napo
Abstract. The vehicle routing problem is a common combinatorial optimization, which is modelled to determine the best set routes to deploy a ﬂeet of vehicles to customers, in order to deliver or collect goods eﬃciently. 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 deﬁning 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 eﬀect of four diﬀerent crossover operators. Numerical results are presented and conclusion are drawn, based on our ﬁndings.
This dissertation is submitted in fulﬁllment of the requirements for the degree of Master of Science, University of the Witwatersrand, Johannesburg, August 2018
Qhomane, Hlompho Napo (2018) Comparison of techniques for solving vehicle routing problems, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/26894>