The non-fixed destination multiple depot capacitated vehicle routing problem and genetic algorithms

摘要

Many organizations face the problem of delivering goods from a certain number of warehouses to a number of retail sites using a fleet of vehicles. The Multiple Depot Capacitated Vehicle Routing Problem is a mathematical model that closely approximates the problem faced by many of these organizations. With regard to the fact that the problem is NP-hard, requiring excessive time to be solved exactly, we develop heuristics based on a genetic algorithm that finds high quality solutions in a reasonable amount of computer time. Basic procedures adapted to a given problem are presented that enable the genetic algorithm to simultaneously route all vehicles. Also, six versions of crossover operators are compared. The test results reveal that the method is able to produce results of a kind not easily obtained before namely in terms of an amount of information about the solutions and the solution space.