管理评论

管理评论 ›› 2022, Vol. 34 ›› Issue (8): 299-312.

• 物流与供应链管理 • 上一篇    下一篇

需求不完全拆分的多厢车辆路径和三维装箱模型与算法

周光辉1, 仲邵伟2, 李邓宇卉1, 张毅祥3   

  1. 1. 中国科学院大学经济与管理学院, 北京 100190;
    2. 中国科学院大学中丹学院, 北京 100190;
    3. 北京理工大学管理与经济学院, 北京 100081
  • 收稿日期:2020-04-20 出版日期:2022-08-28 发布日期:2022-09-21
  • 通讯作者: 周光辉(通讯作者),中国科学院大学经济与管理学院教授,博士
  • 作者简介:仲邵伟,中国科学院大学中丹学院硕士研究生;李邓宇卉,中国科学院大学经济与管理学院博士研究生;张毅祥,北京理工大学管理与经济学院副教授,博士。
  • 基金资助:
    国家自然科学基金项目(72071195;71402176;91538113);国家重点研发计划战略高技术重点专项(H863-01-ZT-002-008-03);中国科学院青年创新促进会(2019171);中央高校基本科研业务费专项。

Model and Algorithm for Three-dimensional Multi-compartment Vehicle Routing Problem with Discrete Split Deliveries

Zhou Guanghui1, Zhong Shaowei2, Li Dengyuhui1, Zhang Yixiang3   

  1. 1. School of Economics and Management, University of Chinese Academy of Sciences, Beijing 100190;
    2. Sino-Dainsh College, University of Chinese Academy of Sciences, Beijing 100190;
    3. School of Management and Economics, Beijing Institute of Technology, Beijing 100081
  • Received:2020-04-20 Online:2022-08-28 Published:2022-09-21

PDF (PC)

159

摘要： 由于需求的多样性,以及不能混装等特点,一些货品通常需要采用多厢货车运输;对订单依据货品种类拆分,优先运送需求紧急度高的货品,可以提高物流服务效率。对于一些规则的箱体货物,采用合理的装箱方案可提高车厢的空间利用率。因此,本文针对需求不完全拆分的多厢车辆路径和三维装箱问题(three-dimensional loading multi-compartment vehicle routing problemwith discrete split deliveries,3L-MCVRPDSD),建立混合整数线性规划模型。提出了一种文化基因算法(memetic algorithm,MA),算法设计了一种订单拆分与合并策略,来解决需求不完全拆分条件下的子订单-车辆分配问题,以及子订单排序与车辆路径之间的映射关系,并嵌套构造型启发式三维装箱策略,实现对模型的求解。与遗传算法(genetic algorithm,GA)、CPLEX的计算结果相比,该算法可以在合理的计算时间内求得满意的可行解。

关键词: 车辆路径, 三维装箱, 多厢, 需求不完全拆分, 文化基因算法

Abstract: Due to demand diversity, multi-compartment vehicles are often used to transport goods unfit for mixed loading. Splitting orders according to the type of goods and prioritizing the goods in urgent need can improve the efficiency of logistics service. For goods packed in boxes of regular shape, effective packing scheme can improve the space utilization ratio. Therefore, this paper studies the Threedimensional Loading Multi-compartment Vehicle Routing Problem with Discrete Split Deliveries (3L-MCVRPDSD) and formulates a mixed integer programming model. A Memetic Algorithm (MA) is proposed to solve the model, which designs an order splitting and assembling strategy to track the suborder-vehicle assignment considering discrete split deliveries, as well as the mapping relationship between suborder ordering and vehicle routing. A construction heuristic three-dimensional bin packing strategy is adopted to identify feasible three-dimensional packing schemes. Compared with the result of Genetic Algorithm (GA) and CPLEX, the proposed algorithm is proved to be able to get satisfactory feasible solution in a reasonable time.

Key words: vehicle routing, three-dimensional bin packing problem, multi-compartment, discrete split deliveries, memetic algorithm