多车程多时间窗车辆路径问题研究

Vehicle Routing with Multiple Trips and Multiple Time Windows

针对末端物流中配送车辆多趟次运输、客户对配送服务时间的多样化需求,研究多车程多时间窗车辆路径问题。构造该问题的最小化车辆数量和总运输成本的双目标混合整数规划模型,设计改进的自适应大邻域搜索算法对其求解;构建了基于路径、车程及客户点3个层级上的多种高效的破坏算子和修复算子来扩大解的搜索空间;使用自适应策略选择高效的搜索算子,以及引入模拟退火新解接受准则避免陷入局部最优解来提高搜索效率。通过多种规模算例实验结果分析,验证了改进的自适应大邻域搜索算法的优越性,并分析了考虑多车程的模型对总运输成本的影响。

Focusing on the multi-trip transportation of terminal logistics and the diverse demand of customers for service time,a vehicle routing problem with multiple trips and multiple time windows is studied.A bi-objective mixed integer programming model is established to minimize the number of vehicles and the total transportation cost,while an improved adaptive large neighborhood search algorithm is designed to solve the problem.In this algorithm,a variety of efficient destroy and repair operators based on three levels of routes,travel distances and customer points are constructed to expand the search space of solutions.An adaptive strategy is used to select efficient search operators and a simulated annealing rule is introduced to avoid the solution from falling into local optimum and improve the search efficiency.By analyzing the experimental results of instances with various scales,the advantages of the improved adaptive large neighborhood search algorithm are verified,and the positive impact of the model considering multiple trips on the total transportation cost is analyzed.