An evolutionary algorithm for a real vehicle routing problem

The NP-hard Vehicle Routing Problem (VRP) is central in the optimisation of distribution networks. Its main objective is to determine a set of vehicle trips of minimum total cost. The ideal schedule will efficiently exploit the company's recourses, service all customers and satisfy the given (mainly daily) constraints. There have been many attempts to solve this problem with conventional techniques but applied to small-scale simplified problems. This is due to the complexity of the problem and the large volume of data to be processed. Evolutionary Algorithms are search and optimization techniques that are capable of confronting that kind of problems and reach a good feasible solution in a reasonable period of time. In this paper we develop an Evolutionary Algorithm in order to solve the VRP of a specific transportation company in Volos, Greece with different vehicle capacities. The algorithm has been tested with different configurations and constraints, and proved to be effective in reaching a satisfying solution for the company's needs.