A circle search algorithm based on dual population co-evolution for vehicle routing problems with capacity constraints

In this paper, a circle search algorithm based on dual population co-evolution (CSA-DPCE) is proposed for solving the capacitated vehicle routing problem (CVRP). The algorithm divides the population into two parts with different evolutionary strategies for the main and auxiliary populations, respectively. The main population adopts a multiscale control factor strategy, which utilizes different control factors to balance the global and local search throughout the evolutionary process. Elite individuals in the main population are used to guide the evolutionary direction of the auxiliary population, which introduces an adaptive learning step, accelerates the convergence in the early stage, stabilizes the convergence in the late stage while approaching the optimal solution, and migrates the new optimal solution generated by the auxiliary population during the evolutionary process to the main population. In order to further ensure the feasibility of the solution and improve its quality, removal and insertion operators were developed using a large-scale neighborhood local search framework. The experimental results show that the CSA-DPCE algorithm converges faster and more accurately, making it an effective algorithm for solving CVRP.