Local search for the vehicle routing problem

The aim of this thesis is to study the Vehicle Routing Problem (VRP), analyse the existing resolution methods in local search and extend a specific VRP module in the Open LS system, an open source local search system. The VRP is a well known optimisation problem. It consists in directing a fleet of vehicles to deliver goods to a series of clients situated at different places. The objective is to choose which route to assign to each vehicle in order to minimise the delivery costs. This thesis focuses on the local search approach to solve the VRP. The local search is a perturbative incomplete method which works by starting from a possible solution and applying local changes step by step in order to improve the current solution.