带软时间窗的多商品需求可拆分两阶段车辆路径问题研究

【目的】干线、支线作为电商企业物流配送的关键环节，其协同优化对降本增效意义重大。【方法】基于干线、支线实际运营特征，提炼出软时间窗、多车场、多商品、需求可拆分两阶段车辆路径问题，建立以车辆路径成本、固定派车成本和惩罚成本（违反配送时间要求）为优化目标的混合整数规划模型，基于派车次数和运输距离节约的贪婪思想，设计高效启发式求解算法，并借助27个小规模算例和8个较大规模算例对模型和算法的求解效果进行验证。【结果】实验结果表明：1）借助优化软件，模型在2个小时内能够求解5个区域中心仓库、20个中转仓库、4种商品的算例；2）所设计的启发式算法能够在较短时间内对现实中的较大规模问题求出可行解，求解能力和求解效率远优于优化软件CPLEX；3）问题复杂度随着问题规模（区域中心仓库数量、中转仓库数量、商品种类数量）增加急剧增加，中转仓库数量对问题复杂度的影响最大，区域中心仓库数量的影响次之，商品种类数的影响最小。4）针对较小规模算例，干线配送成本占比较大，随着算例规模增加，支线环节派车数量增幅较大，进而导致支线配送成本明显增加；5）增加车辆工作时长后，干线环节派车数量减幅较大，总配送成本显著降低。放宽第二阶段车容量限制，第二配送阶段的用车数量大幅度降低；【结论】研究成果不仅可拓展两阶段车辆路径问题现有理论，而且有助于电商企业实现多级配送网络高效协同运作；此外，通过优化配送方案，减少派车次数，有助于缓解城市交通压力，改善城市交通环境。

Multi-Commodity Two-Echelon Vehicle Routing Problem with Split Delivery and Soft Time Windows

Purposes] As crucial components of logistics and distribution in e-commerce enterprises, the coordination and optimization of trunk and branch routes have significant importance in cost reduction and efficiency improvement. Methods] Based on the operational characteristics of trunk and branch logistics, this study extracts the two-echelon vehicle routing problems involving soft time windows, multiple depots, multiple commodities, and split delivery, and a mixed integer programming model is established with the objective of minimizing vehicle routing cost, fixed cost and penalty cost (violation of delivery time requirements). Employing a greedy idea focusing on dispatch frequency and transportation distance savings, an efficient heuristic algorithm is designed and validated through experiments involving 27 small-scale instances and 8 larger-scale instances. Findings] 1) The experimental results show that: Our proposed model can solve instances involving 5 distribution centers, 20 satellites, and 4 commodities within 2 hours by using optimization software; 2) the proposed heuristic algorithm efficiently produces feasible solutions for large-scale problems in a short time, demonstrating superior solving capability and efficiency compared to CPLEX; 3) The complexity of the problem increases sharply with the increase of the scale of the instance, and the number of satellites has the greatest impact on the complexity of the problem, followed by the number of city distribution centers, and the impact of the number of commodity types is the smallest. 3) For small-scale instances, linehaul distribution costs account for a relatively large proportion. With the increase of the scale of the instance (the number of city distribution centers, satellites and commodities), the number of vehicles in the delivery level increased significantly, which leads to a significant increase in the distribution cost of the delivery level. 4) After increasing the working hours of vehicles, the number of vehicles in the linehaul level decreases significantly, and the total cost is significantly reduced. With the relaxation of the capacity limit in the delivery level, the number of vehicles used in the delivery level was significantly reduced. Conclusions] The research results can not only expand the existing theory of two-echelon vehicle routing problem, but also help e-commerce enterprises to achieve efficient and collaborative operation of multi-level distribution networks. In addition, by optimizing the distribution schedule and reducing the number of dispatches, it will help alleviate the pressure on urban traffic and improve the urban traffic environment.