关键词: 多中心车辆路径问题, 时变路网, 混合时间窗, 自适应遗传-大邻域搜索算法

Abstract: Aiming at multi-depot vehicle routing problem with mixed time windows under time-dependent network, an optimization model is established to minimize the total cost, where the total cost includes the vehicle dispatch cost, the fuel consumption cost and the time windows penalty cost. The model comprehensively considers account factors such as multi-depot joint distribution, mixed time windows, the continuous change of vehicle speed and the effects of vehicle speed and load on fuel consumption. An adaptive genetic algorithm with large neighborhood search（AGA-LNS） is designed to solve the model. The adaptive crossover and mutation are adopted to speed up population optimization. The time difference insertion method is introduced to improve crossover operator and mutation operator, and removal operator and insertion operator are embedded to destroy and rebuild feasible solutions, which are all about improving population diversity. The effectiveness of the algorithm is verified by instance analysis, and the influence of the proportion of customers with mixed time windows and the influence of vehicle speed change on the vehicle scheduling scheme are analyzed, which show that the adaptive genetic large neighborhood search algorithm has better performance than the basic algorithm. The research results can enrich the related research of vehicle routing problems and provide the theoretical basis for logistics enterprises optimizing the decision of distribution schemes.

Key words: multi-depot vehicle routing problem, time-dependent network, mixed time windows, adaptive genetic algorithm with large neighborhood search