Comparison of Recombination Operators in Panmictic and Cellular GAs to Solve a Vehicle Routing Problem

摘要

The Vehicle Routing Problem (VRP) deals with the assignment of a set of transportation orders to a fleet of vehicles and the sequencing of stops for each vehicle to minimize transportation costs. This paper presents two different genetic algorithm models (panmitic and cellular models) for providing solutions for the Capacitated VRP (CVRP), which is mainly characterized by using vehicles of the same capacity. We propose a new problem dependent recombination operator, called Best Route Better Adjustment recombination (BRBAX), which incorporates problem specific knowledge such as information about the routes constitution. A comparison of its performance is carried out with respect to classical recombination operators for permutations. A complete study of the influence of the recombination operators on the genetic search is presented. The results show that the use of our specialized BRBAX operator outperforms the others more generic operators for all problem instances under all metrics. The deviation between our best solution and the best-known one is very low, under 0.91%.