考虑动态度和时间窗的两级车辆路径问题  

Two-echelon vehicle routing problem with time window considering dynamic degree

作　　者：林明锦 王建新 王超[3] LIM Ming Kim;WANG Jianxin;WANG Chao(College of Mechanical and Vehicle Engineering, Chongqing University, Chongqing 400044, China;College of Economics and Management, Taiyuan University of Technology, Taiyuan 030002, China;College of Economics and Management, Beijing University of Technology, Beijing 100124, China)

机构地区：[1]重庆大学机械与运载工程学院,重庆400044 [2]太原理工大学经济管理学院,山西太原030002 [3]北京工业大学经济与管理学院,北京100124

出　　处：《计算机集成制造系统》2022年第6期1870-1887,共18页Computer Integrated Manufacturing Systems

基　　金：重庆市科学技术局资助项目(cstc2019jscx-msxmX0189);国家自然科学基金资助项目(72071006,62073007)。

摘　　要：为应对由客户的动态需求、大型货车的限行政策及配送时间窗的限制给供应商制定科学配送计划带来的严峻挑战,设计考虑动态度和时间窗的两级车辆路径优化方法。该方法基于客户动态增量概率阈值及动态度构建响应增量需求的车辆路径更新策略;将连续两级车辆路径优化问题映射为由配送中心到中转站和由中转站到客户的两个子网络的带时间窗的车辆路径问题(VRPTW),并在并行模拟退火算法框架下融合Or-opt,2-opt,2-opt*,Swap/shift 4种邻域搜索策略求解VRPTW。用数据案例对模型及算法进行验证,表明所提策略及方法能较好地满足供应商对客户动态需求的响应,且具有良好的鲁棒性。Considering the dynamic characteristics of manufacturing unit needs,the line-limiting policy of large trucks and the exact constraint of delivery time,a two-echelon vehicle routing optimization method with time window considering dynamic degree was designed.Based on the customer dynamic incremental probability threshold and dynamic degree,an optimized routing update strategy in response to incremental demand was constructed.The continuous dual network optimization was innovatively mapped to the Vehicle Routing Problem with Time Windows(VRPTW)optimization of two sub-networks,including from the suburban delivery centre to the city delivery centre and from the city delivery centre to the customer.The four neighborhood search strategies of Or-opt,2-opt,2-opt*and Swap/shift were merged to improve the parallel simulated annealing algorithm.Company case was used to verify the model and method,and the results show that the proposed method could better meet the agility response of suppliers to the dynamic needs of customers,and had good robustness.

关 键 词：动态度 需求不确定 两级车辆路径 并行算法 模拟退火算法 

分 类 号：U116.2[交通运输工程]