单一规格物体二维矩形条带装箱问题解法研究

胡锦超，贾春玉

(宁波工程学院 经济与管理学院,浙江 宁波 315211)

单一规格物体二维矩形条带装箱问题解法研究

胡锦超，贾春玉

(宁波工程学院 经济与管理学院,浙江 宁波 315211)

为了克服用启发式算法及智能搜索法解决单一规格物体二维矩形条带装箱问题耗时过长的缺陷，提出了新的解法和思路.用线性规划法分别在2个维度求最优解，以最好的方案作为近似最优解，可大幅度缩短求解时间,获得满意的近似最优解.

单一规格；装箱问题；启发式算法；线性规划解法；智能搜索法

三维n个不同规格矩形条带装箱问题是最为复杂NP难的矩形条带装箱问题,也是长宽高3个维度均需优化的装箱问题.只需考虑2个维度时，它同样也是NP难问题，只是复杂程度、计算工作量明显少于三维而已.当货箱某一维度是货物尺寸整数倍或摆放有特殊要求(如只能立着摆放)时，高度方向摆放货物的数量固定不变，三维装箱问题转化为二维装箱问题，可大幅度减少计算工作量，缩短优化时间.装箱问题的应用相当广泛,除直接运用于物流领域外,在新闻组版、布料切割、制造业的三维二维和一维下料等领域均可运用.

三维或二维n个不同规格矩形条带装箱问题的计算复杂度随着问题规模的增大呈指数增长.虽然国内外相关学者对这类问题做了大量的研究，但仍然需要提高解法的优化程度.国内外有关三维或二维装箱问题的研究广泛采用遗传算法[1]、模拟退火算法[2]等搜索算法与BL(bottom-left)、IBL(improved BL)、BLF(bottom-left-fill)等启发式布局算法相结合的方式.此外，还有块排列法[3]和分支定界方法等相关研究.这些研究关于多个不同货物装箱问题的成果较多，而关于单一货物装箱问题的成果却很少.

杨德荣在2006 年提出了一套完善的同规格物体优化装箱算法[4].该算法首先沿3 个坐标方向计算最优高度, 得出层的分布, 将问题转化为平面布局;再通过优化计算和镜像复制, 得到完整的平面优化结果;然后比较三维空间3个坐标方向的优化趋势, 选择可能装入物体最多的方向中最好的一个平面优化布局结果, 并依次装入集装箱.尽管已有一些线性规划方法用于优化装箱问题，但仍有很大的改进空间，急需对这一问题进行深入研究，丰富完善和简化优化方法，提高优化程度.为此，在文献[5]的基础上,本研究提出了一种更为简单的数学模型和计算方法，将沿3 个坐标方向取优简化为仅沿高度方向取优, 计算量为该文献算法的1/3，而计算相同算例得到的集装箱容积利用率相同.新的算法在平面优化中,采用牛玉玲等在文献[6]中提出的优化模型, 并对其进行了改进.

1 问题描述

设有n个相同货物需要装箱，货物三维尺寸分别为长LH、宽WH、高HH，货箱三维尺寸分别为长Lj、宽Wj、高Hj,货物摆放要求为只能立着摆放.问题是如何摆放才能使得货物所需装箱最少或占用空间最小.

2 理论探讨

2.1 三维变二维

由于货物摆放有要求，只能立着摆放，因此高度不需要优化.

设摆放个数为：

NKh=[Wj/HH]

(1)

其中，符号“[]”为向下取整.这样，三维装箱问题就可简化为二维装箱问题，即如何在一个长为Lj、宽为Wj的平面内摆放长为LH、宽为WH的货物，达到优化摆放目标(如一个货箱内所装货物最多的目标).一个货箱内所装货物最多意味着剩余不能利用的空间(这里是面积)最小.假设货箱和货物长度分别大于等于货箱和货物的宽度，按长度优化组合摆放货物后，货箱的剩余长度为△Lj，则货箱的剩余面积为：

SL=△Lj×Wj

(2)

按宽度优化组合摆放货物后，货箱的剩余宽度为△Wj，则货箱的剩余面积为：

SW=△Wj×Lj

(3)

2.2 优先维度优化组合的条件

由式(2)和式(3)可知，货箱剩余不能利用的面积等于单位长度或宽度乘以不能利用的尺寸，受2个因素影响.按哪个维度优化组合剩余面积小，就优先按哪个维度优化组合.

优先按长度优化组合的条件是：

(4)

若式(4)不成立，就优先按宽度优化组合.

因为Lj≥Wj，所以，设优化组合后货箱的可利用长度增加△YLj，可利用宽度增加△YWj，则按长度优化组合后增加的货箱可利用面积为：

YSL=△YLj×Wj

(5)

按宽度优化组合后增加的货箱可利用面积为：

YSW=△YWj×Lj

(6)

当△YLj=△YWj，或接近时，通常优先优化组合宽度，以提高优化程度.但严格条件还是式(4).为了简化，可分别按长度和宽度进行优化组合，两者比较后哪个优化程度高，哪个方案就是最优解.

2.3 数学模型

如果按货箱长度Lj优化组合可摆放X11个长度为LH的货物(第一个下标为货物维度代号，1代表长度，2代表宽度；第二个下标为货箱维度代号，1代表长度，2代表宽度)，可摆放X21个宽度为WH的货物；如果按货箱宽度Wj优化组合可摆放X12个长度为LH的货物，可摆放X22个宽度为WH的货物.

在这种情况下，在货箱宽度方向可摆放宽度为WH的货物kX22个.其计算式为：

kX22=[Wj/WH]

(7)

在货箱宽度方向可摆放长度为LH的货物kX12个.其计算式为：

kX12=[Wj/LH]

(8)

设目标函数是每个货箱所装货物数量最多(maxZL)，则按货箱长度优化组合的数学模型为：

maxZL=X11×kX22+X21×kX12

其约束条件为：

X11+X21≤Lj

1.1一般资料2012年1月至2014年10月对我院的1800份细菌样本进行了分析,有350份血液样本,占总数的19.44%,有312份尿液样本,占总数的17.33%,有268份痰液样本,占总数的14.89%;有287份粪便样本占总数的15.94%;有348份创伤组织样本,占总数的19.33%;有235份生殖道分泌物样本,占总数的13.06%。

Lj-(X11+X21)≤min(WL，WH)

Xi j≥0，且为整数(i=1,2,…；j=1,2,…).

同理，按货箱宽度优化组合时，每个货箱所装货物数量最多(maxZW)的数学模型为：

maxZW=X12×kX21+X22×kX11

其约束条件为：

X12+X22≤Wj

Wj-(X12+X22)≤min(WL，WH)

Xi j≥0，且为整数(i=1,2,…；j=1,2,…).

3 解法实例

3.1 实例1

这里参考文献[5]中例题讨论线性规划法在装箱问题中的运用.货箱长度为5 000cm，宽度为3 000cm，货物长度为400cm，宽度为235cm.

首先计算kX22、kX12、kX21和kX11.

因为kX22=[3 000/235]=12,kX12=[3 000/400]=7,kX21=[5 000/235]=21,kX11=[5 000/400]=12

所以按货箱长度优化组合的单层数学模型为：

maxZL=X11×12+X21×7

其约束条件为：

X11+X21≤5 000

5 000-(X11+X21)≤min(WL，WH)=235

Xi j≥0，且为整数(i=1,2,…；j=1,2,…)

用Excel软件解得：X11=6，X21=11，maxZL=6×12+11×7=149.

按货箱宽度优化组合的单层数学模型为：

maxZW=X12×21+X22×12

其约束条件为：

X12+X22≤3 000

3 000-(X12+X22)≤min(WL，WH)=235

Xi j≥0，且为整数(i=1,2,…；j=1,2,…).

用Excel软件解得：X12=1，X22=11，maxZW=1×21+11×12=153

可见，该方法更为简单，省去了计算各种组合的工作量,只要改变货箱和货物长与宽4个变量，用Excel软件即可自动完成优化计算.实例1按货箱宽度优化组合，单层最多可装货物153个，而按货箱长度优化组合时单层最多可装货物149个.

3.2 实例2

把实例1中货物的长、宽尺寸分别改为430cm和230cm，货箱尺寸不变，即货箱长度为5 000cm，宽度为3 000cm.

建立与实例1类似的数学模型，只需改变货物的长、宽尺寸，变量清除后直接求解即可.求解的结果为：kX22=[3 000/230]=13,kX12=[3 000/430]=6,kX21=[5 000/230]=21,kX11=[5 000/430]=11.

按货箱长度优化组合的最优解为：X11=11，X21=1，maxZL=149；按货箱宽度优化组合的最优解为：X21=0，X22=13，maxZW=143.显然，按货箱长度优化组合的优化程度高，单层最多可装149个货物，而按货箱宽度优化组合的最优解是单层最多只能装143个货物.可见，不一定维度尺寸小的方向优化组合效果就好.

4 结束语

传统上优化组合时优先考虑维度尺寸短的然后考虑尺寸长的，是一种比较好的启发式算法，但不能保证最优解.优化程度改善量受2个因素影响(以二维为例受2个因素影响，三维时受3个因素影响)：一个是货箱一维度优化后可增加的长度；另一个是货箱另一维度的长度.这二者的乘积决定了优化程度的改善量.虽然维度尺寸短的对应的另一维度尺寸长，但不能保证二者乘积一定大.因此，应按二维列出线性规划模型，求出最佳组合.哪个维度的最佳组合更好，哪个就是最优解.这是一种非常有效的单一规格物体装箱问题求解方法.

[1] 李大可，杨花娥.利用遗传算法求解装箱问题[J].延安大学学报，2005，24(4)：32-34.

[2] 张德富，彭 煜，朱文兴，等.求解三维装箱问题的混合模拟退火算法[J].计算机学报，2009，32(11)：2147-2156.

[3]EleyM.Solvingcontainerloadingproblemsbyblockarrangement[J].EuropeanJournalofOperationalResearch, 2002,141(2):393-409.

[4] 杨德荣.一类集装箱布局问题的优化计算[J].物流科技,2006,29(8):43-45.

[5] 杨德荣.集装箱单一规格物体装箱的优化算法[J].交通运输工程与信息学报,2007,5(2):17-23.

[6] 牛玉玲, 范玉妹, 徐 尔.条式配装集装箱的方法初探[J].物流技术,2004(5)：47-49.

Research on the Solution of Two-dimensional Rectangular Strip Packing Problem in Single Specification Goods

HU Jin-chao,JIA Chun-yu

(School of Economics & Management, Ningbo University of Technology, Ningbo 315211,China)

The packing problem of two-dimensional rectangular strip is a big problem of NP. Although the two-dimensional bin packing can adopt the heuristic algorithm and intelligent search method, the time it takes usually very long. There have been some research results, but it still needs improvement. To solve these problems, new solutions are put forward. The linear programming method is used to find the best solution among two dimensions and to use the best solution as the approximate optimal solution. In this way, the resolving time can be greatly reduced and the satisfied approximate optimal solution can be obtained. This method is relatively simple with high efficiency.

single specification goods; packing problem; heuristic algorithm; linear programming solution; intelligent search method

2016-11-14

宁波市自然科学基金资助项目(2015A610174)

胡锦超(1995-)，男，浙江金华人，本科生，研究方向为物流管理.

1006-3269(2017)02-0006-03

TP391

A

10.3969/j.issn.1006-3269.2017.02.002