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

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

由于需求的多样性,以及不能混装等特点,一些货品通常需要采用多厢货车运输;对订单依据货品种类拆分,优先运送需求紧急度高的货品,可以提高物流服务效率。对于一些规则的箱体货物,采用合理的装箱方案可提高车厢的空间利用率。因此,本文针对需求不完全拆分的多厢车辆路径和三维装箱问题(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.