Developing a solution method to capacity constrained vehicle routing problem for the environments with obstacles using metaheuristic algorithms

In capacitated vehicle routing problem, it is targeted to find the optimum set of routes for a fleet of vehicles in which each one is identical with a certain capacity. These vehicles start at a central depot, serve a set of customers and return back to this depot. It is aimed to realize this operation with the minimum number of vehicles and the minimum cost. There are recent studies intended for different path planning problems for the environments in which obstacles exist in literature. In this thesis, on the other hand, capacity constrained vehicle routing problem for the environments with obstacles is addressed for the first time. After the problem was defined and a model was created, a hybrid meta-heuristic method that consists of genetic algorithms and local search strategies was developed for the solution. A visual simulation tool was implemented in which two different types of obstacles as circles and convex polygons may be added in addition to depot-customer locations. The algorithm developed was tested for various scenarios designed. Comprehensive performance tests were conducted for different numbers of customers and obstacles, and obstacle sizes for the first time in literature, and the results obtained were presented. Additionally, potential application areas of this particular form of the problem were discussed.