A memetic algorithm for the Capacitated Vehicle Routing Problem with Time Windows

摘要

Vehicle Routing Problem (VRP) is a widely known NP-Hard combinatorial optimization problem. This paper presents a proposal of a memetic algorithm (MA) with simulated annealing (SA) as trajectory-based method for solving the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). A novel crossover operator, the Single Breaking-point Sequence Based Crossover (SBSBX), is introduced and compared with a widely used operator, the Sequence-based Crossover (SBX). One of the principles behind the design of SBSBX is to reduce the disruptive behavior of SBX, with the aim of providing additional intensification. Initial studies show that the different crossover operators heavily impact the preservation of diversity in the population. Thus, two different parent-selection operators that induce different selection pressure are applied: random selection and binary tournament. The proposal is validated using the well-known Solomon's benchmark. The experimental validation shows that in some of the tested methods premature convergence is an important issue, whereas in other cases convergence is not attained. Overall, the combination of SBSBX and random selection attains the most promising results. In fact, a new best-known solution could be generated for one commonly used instance.