基于贪心法以及遗传算法的工业装箱优化

陈意然，周正阳，吴思远，张烨钟

（绍兴文理学院，浙江 绍兴 312000）

1 研究背景

目前我国快递物流业已成为全球最大的快递市场。由于包裹的基数很大，所以适当节省包装材料就可以产生较大的经济效益。因此，我们需优化耗材方案，在装下包裹的同时节省材料与体积，并考虑货物与耗材之间的柔性问题，做出进一步优化。

2 问题重述

问题一：对订单数据给出包装方案。

问题二：优化每种耗材尺寸。

问题三：若考虑到耗材是柔性物体（长宽高的延伸比例不超过5%），重新探究问题一和问题二。

3 模型假设

1.所有需要装载的货物没有固定放置方向的要求。

2.待装物件都是由包装盒打包的规则长方体。

3.用袋子装物品时袋子的形状会因物件形状变化，在装如矩形物件后，袋子的边角处会存在一个不能放入任何物件的角，忽略此部分的体积。

4.不考虑货物与货物之间的挤压冗余，仅考虑耗材的形变。

4 模型的建立与求解

4.1 问题一：对订单数据给出包装方案

4.1.1 全部使用箱子作为耗材的方案

其中i=1，2，3，4，5。

订单总数为Dn，令num(d,i)为订单编号d 需要的i号箱的数量，目标函数可以表示为：

对于箱型选择和货物装载两个步骤，我们采用自适应随机算法，算法思想如下：

1.对任意订单d 输入，首先规定物件在耗材中的摆放规则，在包装箱的左后方为原点建立空间直角坐标系，优先填满X 轴[一维过程，记为step1]，在X 轴达到最优后由X 轴向Y 轴延伸[二维过程，记为step2]，最后由XOY 平面向Z 轴顶端延伸[三维过程，记为step3]）。

2.随机选择箱型i，记Boxi（Li，Wi，Hi）为i 号箱子的长宽高，goods(lj,wj,hj，d)为订单中第j 件货物的长宽高。在订单d 中随机选择首件货物，若能放下则更新箱内空间，以及装入后货物离坐标原点的最远距离点P（x,y,z），若不能则增大箱子型号，则结束，整体有约束：

3.计算剩余空间是否能减小箱子的尺寸型号，若能则减小，重新进行第二步；不能则继续第四步。

4.根据重力式空间搜索策略[1]算法的摆放优先级选择货物最优尺寸，即在一维过程中需要在订单d 中找到lj（wj 或hj），直至装载完成。

综上得到模型：

4.1.2 全部使用袋子作为耗材的方案

使用可变高度的袋子模型，配合贪心算法来解决问题[2]，首先用0-1 规划选择袋型：

对EXCEL 表格中的订单进行处理，把同一订单下的多种物品按照数量全部展开，akm表示第k 个订单的第m 个物品，akmXi表示将第k 个订单下的第m 个物品装入第Xi号码袋子，Vkm表示第k 个订单的第m 个物品的体积，显然有：Vkm=Ikm*Wkm*hkm。

Vi表示使用第i 个袋子的体积，显然有：Vi=Ii*Wi*hi。

根据题目中所给hi高度为1，进一步构造可变高度的袋子模型，袋子的高度hi等于第一个装入的物品高度且可实时更新，有：Vim=Ii*Wi*hkm。

用贪心法将所有订单物品按底面积从大到小排列，并分别算出四个袋子的底面积，排除无法装下的物品，在符合装袋要求的物品中，优先将最大的物品装入满足底面积要求且剩余底面积最小的袋子，更新袋子剩余体积：Vi'=Vim-Vkm。

选择满足装袋条件且次大的订单物品，继续进行装载，同时比较hkm与hk1m1，倘若hkm>hk1m1则不必更新袋子体积，否则再次更新袋子体积：Vim1=Ii*Wi*hk1m1。

重复上述装载操作，在整个装载过程中，需同时满足下列装载条件：

1.袋子约束：

袋子长+袋子高≥物品长+物品高；袋子宽+袋子高≥物品宽+物品高

对应写出数学约束：

其中hβikαβimα表示第β 次装载时向第i 个袋子中放入第α次订单物品后，更新的袋子高度。

2.方向约束。根据题意我们可以知道，袋子中的订单物品长宽高可以任意互换，因此我们建立方向约束：

bIkm，bWkm，bhkm为第k 个订单下的第m 个物品对应的边竖直放置作为高度，0 表示可以放，1 则表示不能放。

3.设置双目标函数。目标函数要满足耗材总体积越小越好的条件，耗材数量少的条件，我们可以写出：

4.1.3 箱子和袋子两种耗材同时使用的方案

由于袋子可塑性较强且比箱子更节省材料与空间，因此我们优先考虑使用袋子，当袋子装不下时，再考虑使用箱子[3]进行组装：

构造判断函数：

对于原来那些在上题情形超出1-4 号袋子底面积范围的袋子，或者物品本身尺寸并不满足袋子自身的约束条件，尝试使用箱子进行装载，比较物品体积与每个箱子的体积，用Vβω=Iβω*Wβω*hβω依次遍历五个箱子，比较Vβω与Vkm=Ikm*Wkm*hkm的大小关系，找到满足条件且体积最小的箱子，进行装载，并更新箱子的剩余体积：Vi''=Vβω-Vkm

再用Vi''遍历空箱子，若有多个订单物品的体积满足条件，则优先取体积最大的物品进行装箱。

目标函数需要综合考虑装袋与装箱部分：

在这一部分我们还要加上箱子体积约束：Vkm≤ aβVβω。

4.2 问题二：优化每种耗材尺寸

4.2.1 全部使用箱子时的耗材优化

采取遗传算法，新变量I'βω表示更改后的第i 种箱子的长度，W'βω表示更改后的第i 种箱子的宽度，h'βω表示更改后的第i 种箱子的高度：

同时我们需要保持耗材部分总体积最小化：

着重考虑约束条件：装箱方向保持约束条件不变。

使用遗传算法，根据每个箱子的既有尺寸在小范围内进行修改，利用遗传思路扩大尺寸变化范围，进一步寻找最优解。

4.2.2 全部使用袋子时的耗材优化

采取遗传算法[4]，更新后袋子依旧是可塑性的，高度为1，I'βi表示更改后的第i 种袋子的长度，W'βi表示更改后的第i 种袋子的宽度，目标是更新后的每个袋子的体积减去每个物品装袋后的剩余体积尽可能地小：

我们把假设的新袋装尺寸代入刚才的约束条件：

首先是袋子约束依然满足长宽条件：

其次是对于装袋条件，如果尺寸过大且超出装袋范围则无法装袋：I'βi ≤Ikm或者W'βi ≤Wkm，需在预处理时删除数据。

最后是保持上述装袋方向约束条件不变：

用遗传算法[5]将新尺寸的装载物品数量作为适应度函数的数值，同时减去箱子剩余空间的大小作为罚项。

同时使用箱子和袋子问题，基本思路同4.1.3，装满袋子后考虑箱子。

4.3 问题三：若考虑到耗材是柔性物体，重新探究问题一和问题二

全部使用箱子作为耗材时的方案。在装载完成后，耗材长度上会有原长宽高1.05 倍的空间约束条件：

在装载过程中，选取最佳货物时也要满足长度约束：

在新条件约束下，

求解目标函数：

利用遗传算法求解优化后的方案，设定目标函数：

同时需保持耗材部分总体积最小化：

装箱方向保持约束条件不变：

对于袋装和混装类型，只需要将参数做1.05 倍处理，其余做法与前例相同。

5 应用前景

通过优化装箱方案，可以减少运输中的空间浪费，缩减运输次数和运输成本，节约包装材料的使用量，提高经济效益。

在只用箱子包装的情况下，本文使用的自适应随机算法得到的方案准确度较高，但是收敛速度慢。在考虑只用袋装时使用的贪心算法忽略了物体的三维特征，但是贪心算法在解决三维尺寸可变装箱问题且待装物件较少的时候，也能给出较为准确的结果，贪心算法的优势在于运算时间短、效率高，但在运行时可能会陷入局部最优解，因而在某些情况下得到的解准确度较低。