Rich vehicle routing optimization based on variable neighborhood descent and differential evolution algorithm

In order to reflect the vehicle routing problem more realistically, meet the planning needs of different decision makers for vehicle routing, seek multiple equivalent optimal paths, and improve the diversity of the optimal solution set, we regard Rich Vehicle Routing Problem (RVRP, which also means vehicle routing problem with multi constraints) as a multi-modal multi-objective optimization problem. This paper considers the RVRP under four constraints, which are more practical, such as complex road network constraint, load constraints, time window constraint and demand splitting constraint. In addition, when solving this problem, We have designed a method that combines Differential Evolution (DE) algorithm with Variable Neighborhood Descent (VND) algorithm. Firstly, in order to expand the search range of the population, an Oppositional Learning (OL) mechanism is introduced in the basic DE to broaden the search range of solutions. Secondly, in response to the problem of premature convergence and falling into local optima in the basic differential evolution algorithm, a VND local search method is embedded to enhance the population search capability. By optimizing the mathematical model and improving the solving algorithm, the performance of the proposed method was evaluated on the standard benchmark instance of the problem. The experimental results showed that the constructed model and the improved solving algorithm can solve the problem of multiple equivalent optimal paths in logistics distribution. This method achieved the best comprehensive performance and was superior to the most advanced RVRP solving method. It has great potential in practical engineering.