Metaheuristic algorithm design and application for open vehicle routing problem

In this study, the Open Vehicle Routing Problem, which is widely employed by the companies in practice with the use of third party logistics services, is discussed. This problem is in the class of high-dimensional and complex optimization problems. First of all, a decision support system based on a mathematical models and a population based meta-heuristic algorithm was developed for a real-life problem with a heterogeneous vehicle fleet. Then, a three-phase Variable Neighborhood Search Algorithm was proposed in order to solve large-scale problems efficiently. In this proposed method, eight different neighborhoods and shaking strategies was used. The performance of the method was tested on literature test problems and its success was reported comparatively. In addition, different strategies were designed and implemented for the parallelization of parts of the proposed variable neighborhood search algorithm that are suitable for simultaneous calculation on the graphics processing units. A significant speed up was observed in the parallel method obtained by the implementation of these strategies compared to the serial version.