关键词: 多车场带时间窗车辆路径问题, 自适应大邻域搜索, 序列分割, 自适应权重, 模拟退火

Abstract: Aiming at the vehicle routing problem with time windows in multiple depots, an IALNS (Improved Adaptive Large-Scale) algorithm based on neighborhood search algorithm was proposed. Firstly, a path segmentation algorithm was improved in the stage of constructing the initial solution. Then, in the optimization stage, the designed removal and repair heuristic operators were used to compete with each other to select the optimal operator, a scoring mechanism was introduced for each operator, and the heuristic operator was selected by roulette. At the same time, the iteration cycle was segmented and dynamically adjusted the operator weight information in each cycle effectively prevents the algorithm from falling into local optimum. Finally, the simulated annealing mechanism was adopted as the acceptance criterion of the solution. The relevant parameters of the IALNS algorithm were determined by experiments on the Cordeau normative example, and the solution results of the proposed algorithm were compared with other representative research results in this field. The simulation experiments show that the solution error of the algorithm and the variable neighborhood search algorithm does not exceed 0.8 %, even better in some cases. Compared with the multi-phase improved Leapfrog algorithm, the average time-consuming of the algorithm is reduced by 12.8%. It is an effective algorithm for solving multi-depot vehicle routing problems with time windows.

Key words: multi-depot vehicle routing problem with time windows, adaptive large neighborhood search(ALNS), sequence segmentation, adaptive weight, simulated annealing