徐跃明 方锦明 刘哲贤 郑 重 陶海旭

1红云红河烟草（集团）有限责任公司 昆明 650202 2昆船智能技术股份有限公司 昆明 650236 3清华大学精密仪器系 北京 100084

0 引言

随着物流自动化的发展，智能立体仓储和自动化分拣设备得到了广泛应用，但货车运输前的装车过程却仍然高度依赖人工，国内目前暂无成熟的自动装车系统。装货车依赖人工的主要缺点有：自动化、信息化程度低；成本高，管理难度大；效率低，很难长期保持高效率作业；缺少产品数据有效追溯；招工困难，愿意从事搬运行业的年轻人越来越少。除烟箱物流外，疫情之下的冷链物流行业对自动装车系统也有同样迫切的需求。

理论研究中把这类问题称为集装箱装载问题（CLP）。集装箱装载问题是一个经典的组合优化问题：给定一些不同规格的三维箱子，将箱子的1个子集装载进集装箱，使得集装箱的空间使用率最大。集装箱装载问题是一个NP -难的问题[1]：它是背包问题(Knapsack Problem)在三维空间上的扩展。由于背包问题本身是NP完全问题，故集装箱装载问题也不存在有多项式时间复杂度的算法。出于问题本身搜索空间的庞大，求解精确解的集装箱装载算法通常只能求解小规模的问题[2]。

Junqueira L等[3]在2012年使用混合整数线性规划模型来求解集装箱装载矩形箱的最优解，并考虑了货物稳定性和负载的约束。其使用优化软件对100多个随机生成的实例进行了全面的性能分析[4]。计算结果验证了这些模型，并表明它们只能够处理中等规模的问题。……