A Hybrid Effective Genetic Algorithm for Solving the Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is one of the most important combinational optimization problems that has nowadays received much attention of researchers and scientists. In this problem, the objective is to minimize the cost traveled by several vehicles that start to move simultaneously from depot and come back to depot after visiting customers if at first each node is visited only once by one of the vehicles and at second each vehicle does not load more than its capacity during the route. This paper presents a hybrids meta-heuristic algorithm for solving the classical vehicle routing problem. At the first stage, a modified genetic algorithm for finding a suboptimal solution is applied in which a new crossover method for combination chromosomes is proposed. Then at the second stage, the 3-opt algorithm is used for finding better solutions. Extensive computational tests on standard instances from the literature confirm the effectiveness of the presented approach.