VEHICLE ROUTING PROBLEM SECTORIZATION USING HYBRID METHODS

Abstract

VRP (Vehicle Routing Problem) is a problem that was first introduced in the late 1950s and has been since studied thoroughly. However there are no algorithms that have the ability to conclude an optimum solution for the problem yet. In this paper a brief introduction is given to familiarize the reader with the prob lem. Afterwards scope of the study along with its limitations, and assumptions are expressed briefly. Motivations are explained as well to indicate the importance of the problem and its effects in our everyday lives. A summary of previously done researches along with their types of solutions are studied throughout this paper. Then a new algorithm that uses a combination of exact methods and metaheur istics to find the solution closest to the optimum one is introduced. The algorithm in question uses metaheuristics to divide the clients population into smaller pop ulations called sections where each section represents a group of clients that will be served by one of the available vehicles. The algorithm then finds the best route within each of the sections using exact methods which have the advantage of guaranteeing best solutions for small numbers of clients within acceptable time windows. The algorithm then compares newly found solutions with previous ones and decides accordingly whether it must (1) continue in the same path, (2) change it, or (3) stop processing and outputs the best solution that has been found until this moment as the best solution possible. Afterwards, the algorithm is tested using two different sets of configurations to find the best way to visit all 80 cities in the Republic of Turkey with 8 vehicles starting and ending at Ankara with the lowest possible cost. The algorithm is then benchmarked against a tool that has been developed by Dr. Erdo˘gan Gune¸s ¨ and makes use of Microsoft Excel to find the optimal solution for the same prob lem with the exact same configurations and circumstances and then both tools are compared to one another stating advantages of each of them. The comparison shows Dr. Gune¸s’s excel tool was more successful in finding the better solution ¨ within the same time window allowed for processing the given data. At the end of the paper, applications of the algorithm, along with suggestions for further improvements are suggested.