APPLICATION OF GENETIC ALGORITHMS TO VEHICLE ROUTING PROBLEM

Denisa Mocková ； Alena Rybičková

《Neural Network World》 24卷1期 (2014/02) Pp. 57-78

https://doi.org/10.14311/NNW.2014.24.003

摘要

Distribution of the goods from a producer to a customer is one of the most important tasks of transportation. This paper focuses on the usage of genetic algorithms (GA) for optimizing problems in transportation, namely vehicle routing problem (VRP). VRP falls in the field of NP-hard problems, which cannot be solved in polynomial time. The problem was solved using genetic algorithm with two types of crossover, both including and leaving-out elitism, setting variable parameters of crossover and mutation probability, as well as prevention of creating invalid individuals. The algorithm was programmed in Matlab, tested on real world problem of spare parts distribution for garages, while the results were compared with another heuristic method (Clarke-Wright method). Genetic algorithm provided a better solution than the heuristic Clarke-Wright method.

關鍵字

VRP problem ； genetic algorithms ； Clarke-Wright algorithm ； metaheuristics