Heuristik til løsning af vehicle routing problems

Kenneth Knudsen & Mamona Tahir

Student thesis: Master thesis

Abstract

The Vehicle Routing Problem (VRP) is one of the most important and challenging problems in the field of Operations Research. It was first presented by Dantzig and Ramser in 1959, as a problem of designing a least-cost set of routes for vehicles in such a way, that all customers are visited once, and vehicle capacities are adhered to. The importance of VRP is due to the fact that it yields significant economic benefits, which is why researchers have given more and more attention to the various extensions of the VRP that arise from real life applications. Typically such extensions consider additional and more complicated constraints, such as time windows. In this thesis, we have chosen to focus on approximate solution techniques, which not only provide high quality solutions, but within an acceptable computational time. Such methods are especially necessary in large VRP instances with hundreds or even thousands of both customers and constraints. Classical heuristics is a category, consisting of methods, which relatively quickly converges to a solution. It suffers, however, from the fact that the search often results in local minima, which is why the field of metaheuristics currently dominates the heuristics arena, since it considers inferior solutions as access points to more promising regions of the solution space. At the time of this writing, the proposed metaheuristics for most of the VRP extensions is rather limited in the literature. However, we have nevertheless presented some of the currently best metaheuristics for several of such extensions. At the end of this paper, we have applied metaheuristics for an atypical real life instance of vehicle routing, which is based on the district heating network in Copenhagen. A solution is presented, and even though several of the special characteristics of the problem have been simplified and reduced, there is a large similarity between this solution and the existing network.

EducationsMSc in Mathematics , (Graduate Programme) Final Thesis
LanguageDanish
Publication date2011
Number of pages132