多种货物三维装箱问题研究
2021-03-03丁纺侯兆烽赵凯芳
丁纺，侯兆烽，赵凯芳
（天津大学仁爱学院，天津 301636）
集装箱装载一直被应用于智能物流运输、加工调度、复杂系统等领域，同时，也是NP-hard问题，随着全球经济迅猛发展，在现实生活中，自然灾害带给我们的问题也不容小觑。问题背景源于2019年美国数学建模竞赛B题“无人机发送：开发空中救灾响应系统”。Grorge和Robinson首次提出了“层”的概念，再确定货物装载的优先级得到较为突出的启发式算法；Bischoff和Ratcliff提出了一种以计算加载范围由下而上分层建立为主要特征的启发式方法来解决装载不相同物品的问题，这种方式产生的布局结构更加稳定，将运输平稳性与包装效率有效结合起来。后来，Taylor等人将混合整数规划公式与动态规划启发式算法相结合得到可行解。
不过，与之前研究的有所不同，在救灾响应系统中，不仅仅要在满足集装箱承重约束、尺寸约束时使集装箱的体积利用率最大，而且还要满足装载货物数量比例的要求，保证让灾区人民迅速得到救治，快速了解现场环境，对合理安排战略性部署具有很强的现实意义。
1 三维装箱建模
1.1 问题描述
三维装箱问题定义为：已知有i个长宽高分别为Li、Wi、Hi的集装箱和j种长宽高分别为li、wj、hj的货物，经一系列约束后使得集装箱的利用率最大。
1.2 模型假设
（1）集装箱形状为长方体；
（2）所有货物同样均为长方体且质量分布均匀；
（3）所有货物均有外壳不会由于堆积而变形。
1.3 数学模型建立
式中，Z表示集装箱装载货物的体积利用率；V表示集装箱的体积；vi表示第i件货物的体积。
货物集装三维尺寸长宽高约束：
2 基于启发式三空间分割算法的模型求解
2.1 对启发式三空间分割算法做几点说明
（1）定序规则。在实际应用中，不仅需要让集装箱的体积利用率最大，而且要在保证体积利用率最优的情况下，让货物的数量符合一定要求保证装载质量。
（2）空间分割规则。空间分割是指在集装箱装入货物后对剩余空间的有效划分，避免因为不同划分方式对剩余空间的利用率造成负面影响，而且随着货物装载不断进行，集装箱内部装载情况复杂严峻。这采用了三空间分割规则对集装箱进行空间划分，即每当有一个货物装入集装箱时，在该货物的前、右、上三个空间进行分割，不断生成一系列子空间，直至剩余空间不能满足装载条件。
（3）空间合并规则。启发式算法中的空间分割只是让集装箱的货物布局更加明朗，实际操作中，肯定会存在一些零散剩余子空间，所以，一定要对这些可以利用的剩余子空间进行有效整合。这样一来，就会有更大的剩余空间装载货物，提高集装箱的体积利用率。
2.2 启发式三空间分割算法分为以下步骤
Step1：导入集装箱和货物的尺寸信息，确定待装货物的种类、需求量以及不同货物被允许的摆放方向。初始化待装空间，表示为readyspace=（i,0,0,0,L,W,H），其中i表示为货物的种类；O=(0,0,0)表示初始空间坐标；Q=(L,W,H)表示可装剩余空间坐标。
Step2：根据空间大小和货物需求量筛选货物，确定准备装入集装箱的货物种类和方向组合，根据约定好的货物装载优先级Si对待装货物进行排序，生成W种装载组合，其中W依赖于选择的货物种类d和货物的方向组合p。
Step3：选择第Wj（j=1）种装载组合，对待装入集装箱的货物进行三维尺寸约束和体积约束条件进行判断，满足货物的长宽高和体积小于集装箱的长宽高和体积。
Step4：判断第Wj（j=1）种装载组合是否满足货物装载优先级S，记录产生的货物种类di和货物的方向组合pi。
Step5：当满足以上条件时，即有效装箱后在剩余空间中划分前、右、上三个空间的子空间，并且根据空间合并规则对剩余空间进行整合，等待后续装箱。
Step6：跳转Step3，令j=j+1，选取新的装载组合，对约束条件进行判断，重复迭代此循环直至j=W，结束循环。记录其中产生的最优解：包括货物装载的种类、数量和摆放方向。
Step7：结束装箱，计算体积利用率，导出关于解的信息。
3 实验与结果
3.1 集装箱和装载货物的尺寸信息
集装箱采用国际标准ISO集装箱，尺寸为231×92×94（单位：英尺）。货物基本信息如表1所示。
表1 货物的尺寸数据信息
3.2 实验结果与分析
通过计算得到，各种情况下装载结果，如表2所示。
表2 计算结果
四种情况下的装载效果图如图1～4所示。
图1 情况1装载示意图
图2 情况2装载示意图
图3 情况3装载示意图
图4 情况四装载示意图
3.3 模型优化及推广
通过生成标准ISO集装箱装载模型用户界面，在输入框内输入四种货物的长宽高尺寸信息，经过模型求解，便会在输出框内产生相对应货物的数量以及装载货物所用的体积利用率。图5为输入不同于上述四种货物长宽高尺寸信息所产生的装载模型界面。
图5 标准ISO集装箱装载模型效果图
