• Using Age Layered Population Structure for the Multi-Depot Vehicle Routing Problem

      Opoku-Amankwaah, Audrey; Department of Computer Science
      This thesis studies the NP-hard multi-depot vehicle routing problem (MDVRP) which is an extension of the classical VRP with the exception that vehicles based at one of several depots should service every customer assigned to that depot. Finding the optimal solution to MDVRP is computationally intractable for practical sized problem sets, and various meta-heuristics including genetic algorithms have been proposed in the literature. In this work, an e fficient multi-population genetic algorithm based on age layered population structures for the MDVRP is proposed. Three inter-layer transfer strategies are proposed and multi-objective fi tness evaluation is compared with weighted sum approach. An empirical study comparing the proposed approach with existing genetic algorithms and other meta-heuristics is carried out using well known benchmark data. The performance found in terms of solution quality is very promising.