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

摘要： 针对时变路网下带混合时间窗的车辆路径问题，综合考虑多中心联合配送、混合时间窗、车辆行驶速度连续变化及车辆行驶速度、载重量对油耗的影响，以车辆派遣成本、油耗成本及时间窗惩罚成本之和最小为目标建立优化模型，并设计自适应遗传-大邻域搜索算法对其进行求解。该算法采用自适应交叉、变异以加快种群寻优速度，并引入时差插入法改进交叉算子和变异算子，嵌入移除算子和插入算子对可行解进行摧毁和重建以增加种群的多样性。通过多组算例验证算法的有效性，并分析了混合时间窗客户的比例变化及车辆行驶速度变化对车辆调度方案的影响，结果表明自适应遗传-大邻域搜索算法较基本算法有着更好的求解性能。该研究成果可丰富车辆路径问题的相关研究，为物流企业优化决策配送方案提供理论依据。

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