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

作者简介:

通讯作者:

基金项目:

国家自然科学基金青年科学基金项目(No.71902054);国家社会科学基金一般项目(No.23BGL047);河南省高校科技创新人才项目(No.23HASTIT025);河南省哲学社会科学规划项目(No.2022CJJ134);河南省高等学校重点科研项目(No.22A630010);河南科技智库调研课题(No.HNKJZK-2024-36B)


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

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

    Abstract:

    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. Based on the operational characteristics of trunk and branch logistics, the two-echelon vehicle routing problem involving soft time windows, multiple depots, multiple commodities and split delivery is extracted, 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. The experimental results show that: 1) The proposed model can solve instances involving 5 distribution centers, 20 satellites, and 4 commodities within 2 hours by using optimization software. 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. 2) 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 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 maximum 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. 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.

    参考文献
    相似文献
    引证文献
引用本文

徐东洋,吕闯,王利娟.带软时间窗的多商品需求可拆分两阶段车辆路径问题研究[J].重庆师范大学学报自然科学版,2024,41(2):75-87

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2024-06-12