工业工程 ›› 2024, Vol. 27 ›› Issue (2): 147-157.doi: 10.3969/j.issn.1007-7375.220254

• 系统建模与优化 • 上一篇    下一篇

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

吴廷映, 鲁佳琪, 夏洋   

  1. 上海大学 管理学院,上海 200444
  • 收稿日期:2022-12-19 发布日期:2024-04-29
  • 作者简介:吴廷映(1982-),男,苗族,贵州省人,讲师,博士,主要研究方向为运筹优化、鲁棒优化、智能优化算法

Vehicle Routing with Multiple Trips and Multiple Time Windows

WU Tingying, LU Jiaqi, XIA Yang   

  1. School of Management, Shanghai University, Shanghai 200444, China
  • Received:2022-12-19 Published:2024-04-29

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

关键词: 多车程, 多时间窗, 车辆路径问题, 自适应大邻域搜索

Abstract: 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.

Key words: multiple trips, multiple time windows, vehicle routing problem, adaptive large neighborhood search

中图分类号: