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

摘要

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