Özet:
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.
