A genetic based approach to the vehicle routing problem

In its basic form the vehicle routing problem (VRP) consists of serving a set of clients with known locations and demands by a fixed fleet of vehicles of limited capacity, minimizing the total route length. All vehicles are located at a common depot with known location. This is an NP-hard problem. The few methods developed to solve the problem exactly are very time consuming and they are only feasible for small dimension problems. So, the most efficient approaches are based on heuristic algorithms. More recently some meta-heuristics, mainly based on Tabu search, have been developed to the VRP. In this work we present a genetic algorithm to the basic version of the VRP. We describe the way we have adjusted the genetic operators to the problem. We report and analyse the results of a computational study with a set of known test problems.