Specialeforsvar – Københavns Universitet


Solving VRP using Voronoi Diagrams and Adaptive Large Neighborhood Search 

v/Niels Peter Meyn Milthers



In this thesis I create an algorithm to solve the Vehicle Routing Problem with Time Windows. This algorithm uses the clustered structure of many real world datasets caused by large cities. This structure is used to divide the problem into subproblems which can be solved before they are combined and the solution is improved.

The main contribution of this thesis is the initial solution created to start the Adaptive Large Neighborhood Search, together with the use of regions in the ShawRemoval algorithm.

The algorithm is able to solve a well tested instance-set yielding results less than 9% from the optimal solutions using a maximum of 35 seconds pr instance

The algorithm proposed in this thesis shows promising results, but improvements are possible. Some improvements are discussed for later implementation.

Vejledere: David Pisinger & Bjørn Pedersen
Censor: Jesper Larsen, DTU