Improved discrete differential evolution algorithm for solving vehicle routing problem

Given that the vehicle routing problem with capacity constraints is easily influenced by uncertain factors such as customer location and demand, and leads to the infeasible or non-optimal solution, an improved discrete differential evolution algorithm was proposed. The greedy method was employed to construct the initial solution, thereby enhancing its quality of the initial solution. The mutation operator was redesigned according to the integer permutation characteristics, and the crossover operator was adapted for problem model, which improved the algorithm performance effectively. A local search strategy that incorporates local relocation, conditional exchange and a maximum contribution removal mechanism were designed, enhancing algorithm's exploration capabilities. Simulation experiments on the benchmark test set show that the improved algorithm can find the optimal value for 31 out of 33 test cases, indicating superior solution capabilities compared to other algorithms and effectively addressing the vehicle routing problem with capacity constraints.