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

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

作　　者：周光辉 仲邵伟 李邓宇卉 张毅祥[3] Zhou Guanghui;Zhong Shaowei;Li Dengyuhui;Zhang Yixiang(School of Economics and Management,University of Chinese Academy of Sciences,Beijing 100190;Sino-Dainsh College,University of Chinese Academy of Sciences,Beijing 100190;School of Management and Economics,Beijing Institute of Technology,Beijing 100081)

机构地区：[1]中国科学院大学经济与管理学院,北京100190 [2]中国科学院大学中丹学院,北京100190 [3]北京理工大学管理与经济学院,北京100081

出　　处：《管理评论》2022年第8期299-312,共14页Management Review

基　　金：国家自然科学基金项目(72071195,71402176,91538113);国家重点研发计划战略高技术重点专项(H863-01-ZT-002-008-03);中国科学院青年创新促进会(2019171);中央高校基本科研业务费专项。

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] U492.22[自动化与计算机技术—控制科学与工程]