Development of some local search methods for solving the vehicle routing problem

Abstract

In this thesis, two heuristic methods, the assignment-based local search (ABLS) and the generalized crossing (GC) methods, are proposed for solving the capacitated vehicle routing problems (CVRP) and some of its variants. The ABLS method is a multi-route improvement method in which the nodes are inserted into routes based on the solution of assignment problem. The GC method is an extension of the normal string crossing method, in which the new routes are constructed by combining the strings in their original and opposite directions. Computational experiments on several literature benchmark problems are carried out and the results show that the two proposed methods are effective in solving the CVRPs. An application of the two proposed methods to a real-world soft drink distribution problem is also carried out. The computational results show that the proposed methods are able to generate better solutions than the existing approaches.