An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) is one of the commonly studied issues today. It belongs to the class of NP-hard problems and has a high time complexity. Therefore, the solution of the CVRP was focused in this study. An improved simulated annealing algorithm with crossover operator, called ISA-CO, was proposed. A population based simulated annealing algorithm was used in the proposed algorithm. The solutions in the popu-lation were developed through the local search operators, including swap, scramble, insertion, and reversion. The improved 2-opt algorithm was used to develop the routes making up the solution. The partially mapped crossover (PMX) and the order crossover (OX) operators were applied to the solutions in the population to accelerate the convergence. A mix selection method was used to ensure the balance between exploitation and exploration. The ISA-CO was tested on 91 well-known benchmark instances. The results indicated that the method has a better performance compared to other state-of-the-art methods on many instances.

Automated summary

The study proposed an improved simulated annealing algorithm ISA-CO for the CVRP, utilizing crossover and local search operators to enhance the solution. The method showed better performance compared to other state-of-the-art methods on various benchmark instances.