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

Key words: dynamic degree, uncertain demand, two-echelon vehicle routing, parallel algorithm, simulated annealing algorithm

摘要： 为应对由客户的动态需求、大型货车的限行政策及配送时间窗的限制给供应商制定科学配送计划带来的严峻挑战,设计考虑动态度和时间窗的两级车辆路径优化方法。该方法基于客户动态增量概率阈值及动态度构建响应增量需求的车辆路径更新策略;将连续两级车辆路径优化问题映射为由配送中心到中转站和由中转站到客户的两个子网络的带时间窗的车辆路径问题(VRPTW),并在并行模拟退火算法框架下融合Or-opt,2-opt,2-opt*,Swap/shift 4种邻域搜索策略求解VRPTW。用数据案例对模型及算法进行验证,表明所提策略及方法能较好地满足供应商对客户动态需求的响应,且具有良好的鲁棒性。

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