@MASTERSTHESIS\{IMM2004-03183,
    author       = "Á. S. Bjarnad\'{o}ttir",
    title        = "Solving the Vehicle Routing Problem with Genetic Algorithms",
    year         = "2004",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Assoc. Prof.  Jesper Larsen and Assoc. Prof. Thomas Stidsen",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/3183-full.html",
    abstract     = "In this thesis, Genetic Algorithms are used to solve the Capacitated Vehicle Routing Problem. The problem involves optimising a fleet of vehicles that are to serve a number of customers from a central depot. Each vehicle has limited capacity and each customer has a certain demand. Genetic Algorithms maintain a population of solutions by means of a crossover and mutation operators.

A program is developed, based on a smaller program made by the author and a fellow student in the spring of 2003. Two operators are adopted from that program; Simple Random Crossover and Simple Random Mutation. Additionally, three new crossover operators are developed. They are named Biggest Overlap Crossover, Horizontal Line Crossover and Uniform Crossover. Three Local Search Algorithms are also designed; Simple Random Algorithm, Non Repeating Algorithm and Steepest Improvement Algorithm. Then two supporting operators Repairing Operator and Geographical Merge are made.

Steepest Improvement Algorithm is the most effective one of the Local Search Algorithms. The Simple Random Crossover with Steepest Improvement Algorithm performs best on small problems. The average difference from optimum or best known values is {4,}16  {1,}22 \%. The Uniform Crossover with Steepest Improvement Crossover provided the best results for large problems, where the average diÙerence was 11.20 {1,}79\%. The algorithms are called {SRC-GA} and {UC-GA}.

A comparison is made of {SRC-GA,} {UC-GA,} three Tabu Search heuristics and a new hybrid genetic algorithm, using a number of both small and large problems. {SRC-GA} and {UC-} {GA} are on average 10,52 {5,}48\% from optimum or best known values and all the other heuristics are within 1\%. Thus, the algorithms are not effective enough. However, they have some good qualities, such as speed and simplicity. With that taken into account, they could make a good contribution to further work in the field."
}