（计算机软件与理论专业论文）装箱问题的算法研究——同一物体的装箱算法.pdf

装箱问题的算法研究 一同一物体的装箱算法 专业：计算机软件与理论 硕士生：梁锋 指导老师：郭嵩山 摘要 装箱问题( c o n t a i n e r l o a d i n g p r o b l e m ) 研究的是如何把一些立方体形状的盒 子放到同样立方体形状的箱子内。该问题有重要的工业使用价值和经济价值。但 是装箱问题是属于n p 难问题的，因此在理论上很难寻找一种求解最优解的普遍 方法。 论文首先回顾了装箱问题的研究背景以及从前人研究中得到的某些启发策 略。然后给出了一个同一物体装箱的启发策略，通过该策略去生成装箱的解。在 此基础上使用树搜索算法加以改进。搜索算法提供了回溯的可能，这样在一定程 度上提高了解的质量。通过对算法的分析，并进行大量的试验，采用通用的测试 数据以及部分随机数据对该算法进行测试，结果显示算法能在一个合理时间内得 到较好的次优解。这样的结果很好地满足工业应用的需要。最后论文总结指出了 进一步研究的方向。 关键字：装箱问题，区块结构，组合优化 a s t u d yo f a l g o r i t h mf o rc o n t a i n e rl o a d i n g p r o b l e m a a l g o r i t h mf o ri d e n t i c a lc a r g o s m a j o r ：c o m p u t e rs o t i w a r ea n dt h e o r y n a m e ：l i a n gf e n g s u p e r v i s o r g u os o n g s h a n a b s t r a c t t h ec o n t a i n e rl o a d i n gp r o b l e m ( c l v ) i st h ep r o b l e mo fl o a d i n gas e to f r e c t a n g u l a rb o x e si n t oar e c t a n g u l a rc o n t a i n e rw i t h o u to v e r l a p t h i sp r o b l e mh a s i m p o r t a n ti n d u s t r i a la n dc o m m e r c i a la p p l i c a t i o n , e s p e c i a l l yi nc u t t i n ga n dp a c k i n g i n d u s t r y c l pb e l o n g st ot h ec l a s so fn p - h a r dp r o b l e m s s oo p t i m a ls o l u t i o n sa d i 伍c u l tt of i n d t h et h e s i sf i r s t l yr e v i e w st h eh i s t o r i c a lb a c k g r o u n da n ds o m eh e u r i s t i c sg i v e nb y p a s tr e s e a r c h e s t h e nah e u r i s t i co fi d e n t i c a lc d l r g o si sp r e s e n t e dt h a tg e n e r a t e s e f f i c i e n tl o a d i n ga r r a n g e m e n t s a d d i t i o n a l l y , t r e e - s o a r e ha l g o r i t h mi su s e dt oh a v ea p o s s i b i l i t yo fh a c k t r a e k i n g , s ot h a tt h e s o l u t i o n sp r o v i d e db yt h eb e u r i s t i ea 托 i m p r o v e d a n a l y s i si sp r e s e n t e da n dp e r f o r m a n c et e s ti sd o n eb y1 l s i n gb o t hp u b l i s h e d a n dr a n d o m l yg e n e r a t e dd a t a t h e s ee n m p u t a t i o n a lr e s u l t ss h o wt h a tn e a r - o p t i m a l s o l u t i o nc a l lb ep r o c e d u r ei nr e a s o n a b l et i m e , a n di tn l d st h ei n d u s t r i a lr e q u i r e m e n t f i n a l l y , t h et h e s i sc o n c l u d e s 、斩血s u g g e s t i o n sf o rf n r t h e rw o r ki nt h i sa r l 琵 k e yw o r d s ：c o n t a i n e rl o a d i n gp r o b l e m , k - b l o c ks t r u c t u r e , e n m b i n a t o r i a l o p t i m i z a t i o n 第1 章概述 集装箱是重要的现代化运输工具，在某些发达国家，这样一种标准化的运输 方式已经占到物流运输量很高的比例；而在我国，尤其在沿海地区，也越来越普 及。提高集装箱的箱容利用率可以为企业节约了运输成本，大大加强了其竞争能 力也节约社会资源。但目前为止，国内大部分企业在这方面还是处于人手操作 阶段，依靠工作人员的经验来编排计划，往往耗费很多时间且效果也不理想。装 箱问题( c o n t a i n e rl o a d i n gp r o b l e m ) 的研究可以充分利用计算机的运算能力，代替 人手，快速实现商质量的装箱计划，从而提高工作效率。 抽象来说，装箱问题研究的是如何把一些立方体形状的盒子放到同样立方体 形状的箱子内。该问题源于g i l m o r e 和g o m o r y 把切割下料问题( c u v a n gs t o c k p r o b l e m ) 高维推广【1 】。目前的研究集中在如何在单个集装箱内装尽可能多的箱 子。由于装箱问题在理论上属于n p 难问题，因此快速寻找一个比较好的解是最 具实用性的研究。 本文余下章节在结构上分为四部分。第二章是问题的描述，为装箱问题定义 一个数学模型，并且对已有的研究做一个回顾总结。第三章是作者把问题集中在 研究单个物体的装箱问题，详细讨论了如何利用降维的思想，在解决二维装箱问 题的基础上，得到三维装箱问题的一个较好结果。带回溯的启发式算法是该方法 的核心。第四章则通过实验的方式，利用数据对算法的结果做一个分析，现实算 法在实践上具有可行性。最后第五章总结，指出了进一步研究的方向是实用。 第2 章问题描述 3 1 一般装箱问题的数学模型 简单来说，装箱问题就是如何把一些小的立方体形状的盒子( b o x ) 放入一个大 的立方体箱子( c o n t a i n e r ) 里面。c h e n 等人【2 】试图给装箱问题定义一个用数学方 程描述的模型。它的基本思想是使用坐标指定盒子的摆放位置，以及用0 - i 变量 去指定盒子的摆放方向，从而可以确定地给出盒子与箱子之间的关系。在此基础 上用方程表达各种限制条件以及目标函数，例如盒子的摆放是如何不允许重叠 的。事实上c h v n 等人给出的模型是一个可求解的线性规划( l i n e a r p r o g r a m m i n g ) 模型。 描述一般的三维装箱问题，首先要确定盒子与箱子的个数以及大小，这些参 数都是已知的： 需要放入箱子的盒子个数； 肘 总共有的箱子个数； ( 融靠r j ) 每个盒子的长、宽、高； ( 匕既h i ) 每个箱子的长、宽、高。 此外，为了表示它们之间的位置关系，需要定义一个三维直角坐标系，然后 把所有箱子都放入到坐标系的第一挂限，它们的三条边分别平行于坐标系的三个 轴，并且其中一个顶点位于坐标原点初。同时定义下面一些变量表示盒子的位置： ( 轧y t , 动 u 墙l 舜l 南 ( i 矗嵋啦w a ) 坐标变量，表示第f 个盒子摆放的位置。它记录的是该盒 子前面的左下角坐标，也就是盒子八个角中最靠近原点的 坐标值。 一个二进制向量。三个分量分别表示表示盒子i 的长边胁 是否平行于工轴、y 轴和z 轴。例如，如果长边平行于j 轴，那么t ：l ，否则k = o 。 一个二进制向量。三个分量分别表示表示盒子i 的宽边m 2 ( 蚴 4 b 咖c 蜘d te ，南 是否平行于x 轴、y 轴和：轴。例如，如果长边平行于并 轴，那么w 。- - - - i ，否则w 矗- - o 。 一个二迸制向量。三个分量分别表示表示盒子i 的长边r i 是否平行于j 轴、y 轴和z 轴。例如，如果长边平行于x 轴，那么 产l ，否则j l d = o 这六个变量表示盒子i 与盒子k 之间的位置关系。如果盒 子f 位于盒子k 的左边，那么4 i 尸l ，否则a o - - o 。类似地。 其余五个分别表示位于盒子k 的右方、后方、前方、下方 和上方。这里可以规定i k 的情况可以据 此推断出来。 最后为了表示盒子与箱子之间的关系，还需要定义另外两个二进制变量： 唧如果第i 个盒子放入到第，个箱子中，那么s o = l ；否则5 圹- - o n j如果第- ，个箱子中放入了某些盒子，那么n t l ，表示该箱 子已经使用了；否则雄，：o ，表示没有使用该箱子。 各变量的含义如图2 1 所示。 y 1 ：兰竺轴 竺! = = ! - ； h 一轴_ - 图2 - 1 装箱的表示：盒子i 和k 放在箱子，中【2 】 一个符合要求的装箱方案，必须满足： $ i l + 萱珏+ + 以f i f s l( 2 - 1 ) s l j + s 2 j + + 帅2inf+吩(2-2) x l + p i z 畦+ q l 毒w d + r i 试s x k + ( 1 - a m * i n f o 移 q 溉+ 肌+ 瓠搴k + n 嘞吐- x i + ( 1 - b i t ) * l n f 一 砂( 2 - 4 ) 期+ p + 承+ n i h + o - c 征) * n f 一 矽( 2 5 ) 腓+ 肌+ 瓠+ “- y i + ( 1 - d & * i n f 一( 材( 2 - 6 ) z t + p f 专b + q t 、协+ r t * h as z t + n - 列叫t v f一 移( 2 - 7 ) z k + p l 矗+ q k 矗+ r h 噍s z i + 0 - 列* t w ( t i 磅 而+ p j + q i + n s 与+ ( 1 - s 矿* i n f ( 2 - 9 ) y l + p i + 缈帆+ r t 乃+ ( 1 - s t p * l n f( 2 - l o ) 句+ p l 锄+ q i * w h + r i * h a j 巧+ ( 1 - s ) * n f ( 2 1 1 ) 这里n f 是一个足够大的整数。任何满足上述公式的解都给出一个装箱的可 行方案公式( 2 - 1 ) 表示任何一个盒子最多只能放入一个箱子里，也可能被忽略而 不放入任何箱子。任何箱子如果装有至少一个盒子，那么这个箱子被认为是已经 被使用过，公式( 2 2 ) 就是表示这样的关系。公式( 2 3 ) 一( 2 8 ) 保证了盒子的摆放位 置不重叠，这里的重叠只是考虑位于相同箱子的情况，对不同箱子里面的盒子之 间不必考虑位置关系。一旦盒子i 被放入箱子k 里面，那么盒子一定不能超出箱 子的大小限制，要满足这个条件则必须符合公式( 2 9 ) - - ( 2 一1 1 ) 另外，表示盒子摆放方向的向量( k 钿乙) 、m w y i , 劲和( 矗 归蚴并不是 相互独立的，它们必须满足下面的关系： b + “+ t a = l k + w x l + = l ， k + b + h a = l k + w k + k = i 如+ 瓠+ b ；l l 矗+ w d + h z i = 1 满足所有这些方程的解称为一个可行解，它对应一种装箱的方案。特殊情况 下，如果任何一个盒子都不放入箱子中，也是可行的。为了得到需要的装箱方案， 需要设计一个目标函数。不同的目标函数就得到各种特定的装箱问题。常见的装 4 箱问题的类型有： 带状充填( s t r i pp a c k i n g ) ：一个箱子有确定的高度和宽度，但长度无限大 目标是把所有盒子装迸箱子后的长度尽可能小。令m = i ，公式( 2 1 ) 改为 毋j + 即+ + $ m = l 且令t 为变量，则目标函数为 m i n l t 背包装载( k n a p s a c kl o a d i n g ) 这种情况下假定每个盒子都有一个价值竹， 如何把部分的盒子装入一个箱子中，使得到的价值总和最大。令m = i ， 目标函数为 m a x v 1 目 如果盒子的价值定义为它的体积，那么目标就变成使箱子空间浪费最低， 即容积利用率最高此时目标函数可以写成 m 缸厶彤h t 一( a 吼) i = 1 货柜装载( b i n - p a c k i n g ) ：如何用尽可能少的一种规格箱子去装载所有的 盒子。即有厶= 厶，坼= w j , 蜀= 碍( i j ) ，公式( 2 - 1 ) 改为 s h + s 口+ + s 湖4 目标函数为： r a i n m 多箱装载( m u l t i - c o n t a i n e r p a c k i n g ) ：和货柜装载类似，但是箱子大小不一 定相同，并且每使用一种箱子都有一定的花费，目标就为如何使装载完 左右的盒子后总的花费最小。为每种规则的箱子准备足够多个，令国表 示箱子_ ，的花费，公式( 2 1 ) 改为 研，+ 跑+ + $ m = l 那么目标函数为 村 m a x 岛”， j z l 装箱问题有时候也按盒子种类进行分类。如果所有的盒子都是同一的长宽 5 高，那么就成为同形装箱( h o m o g e n e o u s ) ，而有很多种不同规格的盒子就成为强 异形装箱( s t r o n g l yh e t e r o g e n e o u s ) 。更多时候出现的情形是，只有少数几种规格， 每种规格各有很多个盒子，通常把这样的问题成为弱异形装箱( w e a k l y h e t e r o g e n e o u s ) 3 2 问题描述 上面这么多种目标函数，每一个都是很难寻找最优解的，因此本文把注意力 集中到一个特殊的闯题上来。设想箭牌公司生产的绿箭口香糖需要包装好运送到 各个经销商处，他们首先把每五条口香糖包成一小包，然后把一打这样的小包装 到一个盒子里面，再一盒一盒地装入纸箱去运送。每一个步骤需要装载的东西都 是规格一致的。似乎箭牌公司的产品销路一直不错，他们暂时不需要考虑在放口 香糖的箱子里加其它的产品。但是他们会去考虑如何充分利用纸箱空间，这样工 人搬运就更加方便，提高运输效率会给公司带来极大的利益。 这个问题也是一个装箱问题，纸箱和包装盒都可以抽象成为立方体。更准确 来说，这个一个背包问题。有无穷多盒子虽然不适合上面给出的模型，但其实一 个箱子能容纳的盒子是有限的，那么令n 足够大就可以了。把这些盒子都装入 到一个箱子里面，使得箱子的容积率最大。 为了简化问题，有必要把上面模型的无关变量去除，因为某些变量并不是至 关重要的，例如，表示盒子的摆放位置和方向等变量仅仅只是最后结果的一种表 示方式。 事实上，单一物体的装箱问题只需要知道该盒子和箱子的尺寸就可以了。令 工、形和h 分别表示箱子的长、宽和高，而，、w 和 分别表示盒子的长、宽和 高。问题是最多能在箱子放多少个盒子，或者如何尽可能多地放下盒子使得箱子 的剩余空间最小。 3 3 启发式方法的回顾 在2 1 节给出的模型是一个混合模型，它不是纯粹的线性规划模型，也不是 6 纯粹的整数规划或者0 - 1 规划模型，因为它里面包含有二进制变量，这些变量只 能取值0 或者1 ，而坐标则可以取实数值。c h e r t 尝试使用上面的模型去解决提 高空间利用率的背包问题【2 】。经过化简，模型总共有3 n 个连续变量以及 ( 3 + j j l 升1 肌肘个二进制变量。c h e r t 用l i n g o 软件包计算了包含1 9 8 个约束条 件和1 5 3 个变量的问题，发现随着盒子的增加，约束条件会急剧增加，造成计算 上的困难，即使使用速度快的计算机，也需要十分漫长的时间。作为一个有应用 价值的问题，花费大量时问去寻找一个最优解并不是一个经济的选择，提高利用 率所能得到的远远小于为此付出的花销。因此，在可接受时间内寻找一个满意的 方案会是好的选择。在理论上，即使是一维的背包问题是属于n p 难问题，目前 还没有找到在多项式时间的算法可以有效解决它。在这个思想指导下，各种根据 经验建立起来的启发式方法被不断发现 众多文献上有装箱问题有归类和总结，例如参考文献 3 - 8 】。常用的启发式方 法有四种：筑墙方法( w a l l - b u i l d i n g ) ，堆叠方法( s t a c k b u i l d i n g ) ，剪裁方法( g u i l l o t i n e c u t t i n g ) ，立体排列方法( c u b o i d sm - r a n g e m e n t ) 。 图2 - 2 筑墙方法 g e o r g e 和r o b i n s o n 9 第一个尝试给出三维装箱问题的启发式方法，使用的 就是筑墙方法。沿着前后方向垂直把箱子切开来，每一块成为一个“层”( l a y s ) ， 然后在每个层中分别考虑如何装入盒子，这样每一个盒子只能被放入某一个层 中，而不允许同时占据多个层的位置。如此可以减少装箱的复杂程度，只要层划 分得足够好，在每层里面都尽可能多放入的盒子，那么总体上也就可以达到一个 比较好的效果。g e o r g e 和r o b i n s o n 从前往后逐一切分层，每次决定一个层的长 度，然后再往该层放入其它盒子，直到不能放入盒子就构建下一个新的层( 如图 2 2 ) 。为了决定层的长度，他们把盒子分成两类：一类是在之前的层里面已经使 7 用过的盒子，而另一类则是仍未使用过的。切分一个层的时候优先考虑还没有使 用过的盒子。第一个放入这个新层的盒子，它的长度也就决定了层的长度，也就 是说这个新的层长度要刚刚好能够容纳这个盒子。在选取盒子的时候，如果没有 未使用过的盒子，那么就通过一系列原则来选取，例如：选择最小边长尽可能大 的盒子；具有最大边长的盒子；已经使用得最多的盒子等等。同样如果有多个未 使用过的盒子，也要尽量选择一个“好的”盒子，例如：相同类型最多的盒子， 或者是类似于上面的一些原则。放入了第一个盒子之后，再从剩下的盒子里面选 择长度相同，或者接近的盒子，再放入该层中。更小的盒子应该越后面才考虑， 因为小盒子摆放比较灵活，它们一般只是用来填充空白位置为了改进解的结果 g e o r g e 和r o b i n s o n 给层的长度引入一个上界，在这个上界限制下尝试不同的层 构造方式，从中选择最好的结果。 b i s c h o f f 和d o w s l a n d i o 也给出一个用筑墙方法构造的启发式方法。其方法 的特点是每一个层只能用同一种盒子来填充。不再考虑放入别的类型盒子，从而 简化装箱的情况。为了一步提高装箱效果，放在同一个层里面的盒子都统一方向， 把问题简化为二维的情形，以此降低复杂性。层的长度选择与g e o r g e 和r o b i n s o n 的方法同样都是通过不断选择来达到一个好的结果。 同样是为了把问题转换成了二维情形。g i l m o 和g o m o r y i 选用了堆叠方法 来装箱。他们先把盒子分成组，摆放不超过箱子高度的一堆一堆，最下面的盒子 在低面上一定是最大的。这样所有堆的最低下盒子只要能放入箱子中，那么整个 堆的盒子也一同被放进去。剩下的工作就是要尽可能多地把堆都放进去。但是如 何构造堆将会影响到最后的结果。 图2 - 3l 形填充 h a n s e n 1 1 等人提出了一个混合动态规划和筑墙方法的启发式方法。他们通 过另外一种途径来缩小箱子，以减少规模。不考虑盒子的方向限制，它们首先沿 着箱子的地步以及其中一个面摆放箱子( 如图2 3 ) 。当填充完这个l 形空间后， 8 一个新的更小立方体空间出现了，同样的方法应用在这个空间上面，知道所有的 空间都填充完。h a n s c n 的方法取决于填充l 形的效果。 x u c 和l a i 1 2 n 1 提出一个综合的启发式方法来解决问题。他们同时使用三种 启发式方法，首先是按照盒子的个数、形状等信息赋予盒子不同的优先级，然后 利用第二种启发式方法选取盒子的摆放位置来构造新的层，最后用另外一种启发 式方法去填充一个层结果显示他们的方法可以较单一的方法提高3 到1 0 剪裁方法是另一个解决装箱问题的途径。n g o i z 3 等人设计了一个启发式方 法解决单箱子装箱问题，他们要求盒子在垂直方向上是固定的，但水平方向上可 以旋转。n g o i 等人的方法使用了空间表示的技术来描述装箱的过程。他们把箱 子表示成一个一个小箱子在各个方向上组合的结果，然后用矩阵描述某一高度范 围内的各个小箱子的情况，例如，如果小箱子里面装了某个盒子，那么就记下它 的编号；否则置为零，表示空箱子。一连串的矩阵一起就可以表示整个箱子的装 载情况，这样的矩阵成为空间矩阵( s p a 触m a t r i x ) 当要往箱子里面放入一个盒 子的时候，就按照一定准则去寻找一个有足够大小的小箱子这个小箱子剩余的 空间随后会沿水平或者垂直方向被分割开，形成若干更小的箱子。这样的方法一 直进行下去，最后箱子越分越小，直到不能再放入更多的盒子。事实上没有一个 很好的办法去指导如何选择和切分小箱子，到最后往往会产生出大量的小箱子。 n g o i 等人的结果表明这种方法的结果只能维持在8 0 左右的容积利用率。但如 果有些小箱子如果是相邻的，那么就可以把它们合并起来，形成更大的空间以容 纳其它的盒子。通过空问矩阵就可以有效地完成合并，l i r a 1 4 1 等人的结果证明 这样的改进方法是有效的。 c h u a 1 5 等人在n g o i 等人的基础上把算法推向实际应用。因为用空间表示法 可以很清晰地表达出各个盒子办法的位置，所以c h u a 等人允许在装箱之前确定 好某些盒子必须放在特定的位置。 l a i 1 6 等人则把装箱问题应用到多客户投递问题中去。假设快递公司接到很 多客户的业务单，把他们的货物放入运输车，然后再投递到不同地方。物体装入 和取出的顺序刚好相反，车子每到一个地方就把部分货物卸载下来。同一客户的 东西都将被放到一起。问题就是如何尽可能多地摆放这些物体，以及选择行走路 线。如果单纯考虑装箱，那么一个简单的方法就是把车厢按照长度分割成几个部 9 分，分别放入不同物体，再次基础上考虑行走路线也只是最后再调整摆放顺序。 l 面等人通过建立一个图的模型来解决这个问题。每一个可行的位置被表示成图 的一个点，两个点之间连一条边当且仅当在这两个位置摆放不同物品后不会重 叠。最终问题被归结为求图的最大团( c l i q u e ) 。这种方法的缺点是图的规模会变 得很大，l a i 等人发现即使只有1 0 个一模一样的盒子，图的顶点数也达到1 0 0 0 左右。而且求解图的最大团也还没有一个有效的算法 1 0 第3 章同一物体装箱问题 同一物体装箱问题可以被描述为：现在有一个l xw x h 的箱子，以及无穷 多个l x w x h 的盒子，如何在箱子中放入尽可能多的盒子? 下面介绍作者在该研究中采用的方法。 3 1 启发式方法 本论文的启发式算法也是建立在筑墙方法基础上。箱子从下到上被划分为多 个层，每当一个层被划分出来之后就往该层中填充盒子( 如图3 1 ) 图3 - 1 从一f 往上逐一填充每层的启发式方法 显然，每层的高度一定与盒子的边长有关，即层高d = a l * b w * c h “b , c 是整数) 。 因为如果不是，则超出来的部分一定是多余的空问，它们不能被填充。从另一个 角度考虑，如果d 取值过大，划分出来的空间也会很大，下一步还是需要继续 划分，这样对问题的解决没有很大的帮助。因此，选择d 应该等于盒子的某条 边长。 层被划分后就要往里面填充盒子。没有方向限制的盒子有六种摆放方法，其 中最多有三种不同的高度，显然，高度超过d 的不能放入该层。假设l w h 并 取d = h ，如果把盒子平放( 如图3 - 2 ) 。又假设此时取w 为高度，那么此时的占 据层的面积为h * l ，要大于原来的w 吖。而且上面会出现一个h * l * ( h - w ) 的空间。 一般情况下，盒子的边长差异不会超过2 倍，也就是说上不产生出来的空间将得 不到有效利用。因此，把高度小于d 的盒子放入该层也不是一个很好的选择。 如果放入这个层的盒子高度等于d ，此时盒子的底面只有一种规格。问题将被简 化为如果用小的矩形填充一个较大的矩形，是装箱问题的二维情形。 ( a )( ” 图3 - 2 盒子的填充方式( a ) d 瑚平放，高度为w 当高度已经确定的时候，填充每一层需要考虑的参数进一步减少，从箱子的 上面往下看，其实就是如何把一个x x y 的矩形放入w x l 的大矩形之中，这里 伍y ) = m 鬼，) 。这次选取的策略是把x x y 的小矩形放入大矩形a e g i 的一个角 a b c d ( 如图3 3 ) ，沿b c 和d f 会有两条分割线把大矩形a e g i 划分开四个不 同区域，其中左下方区域已经被完全占据。直接往另外三个区域分别填充是一个 简单方法，但是太零碎的空间会降低填充的效果，因此可以考虑把空白区域合并 有两种合并方法：b e g h 与d c h l ，或者b e f c 与d c h i 。这两种填充方法一定 不会比上面的效果差，但是没有一个好的准则去判断这两种方法哪一种更好，它 们的结果在不同情况下可能相差很远。因此，最好就是两种方式都尝试一遍，然 后从中选择最好的一个。 1 2 图3 - 3 二维装箱( 层的俯视图) 启发式算法的基本过程如下； 输入：箱子的尺寸工、肌z ，箱子的尺寸，、w ， 输出：所放入的箱子个数 算法：p a = k m g p r o c d l 扯_ p a c k i n g l ，w ，h ； 初始化已装入的箱子数s = 0 ； 1 ，h ) f o zdi nt 1 ，w ，h 且d st h 令s = s l ，并记下当前的d 为db e s t ； n d i f e 耐- f o e i ts 不等于0t h 札 调用p a c k i n g ( l - db e s t ，w ，h ；1 ，w ，h ) 得到一个解s 2 ； 令s = s + s 2 ； e m d - l f n t n z n 三维装箱的结果s ； 子程序：p a c k i n g2 d p r o c d 哪p a c k i n g _ 2 d ( l ，w ； 1 ，w ) i fl 皇la n dw - - - wt h 雠 调用p a c k i n g d ( l ，w w ；lr w ) 和p a c k i n g 2 d ( l 一1 ，w ；1 ，w ) 连同已放下的一个矩形得到一个解，记为s l ； 调用p a c k i n g _ 2 d ( 1 ，w w ；l ，w ) 和p a c k i n g2 d ( l 一1 ，w 7 1 ，w ) 连同已放下的一个矩形得到一个解，记为s 2 ， e n d - i f i fl w , y l + y 3 x 3 ，x l x 2 ，x i x 4 = l - y i 即令区块l 是所有四个区块里面最大的一个。 所有这些条件加起来，就可以有效枚举出所有可能的4 区块结构了 由此可以得到改进后的过程p a c k i n g _ 2 d _ i m p o r v e ，取代3 1 节里面的予过程 p a c k i n g。_2d 子程序：p a c k i n g _ 2 d _ i m p r o v e p z o c _ k h , r ep a c k i n g _ 2 d _ i m p r o v e ( i - ，w ，l ，w ) 初始当前最优解s ；0 ， i fl * w 能容纳l * wt h e m 令s = l ，柚d i f f o za l lx l 2d o 调用p a c k i n g _ 2 d _ i m p r o v e x ，w ，1 ，w ) 和 p a c k i n g2 d _ i m p r o v e ( l - x ，w ；l ，w ) 得到一个结果s l ； 保留展优解：s - - m a x s ，s l ， 砌- e o e f o za l ly gw ) w ) 3 则空余面积s 可以通过下面的方法计算： m i l ls s t s 2 m a x 丸b ) s i a ( m o d j ) s i b ( r o o d 讷 4 最后得到上界： = 悟j 第三种估算上界的方法是从边长来考虑的1 1 8 1 。 厶f = m a xa 吖4 - b * w s t a * 4 - b * w s 厶4 ，6 是整数 矾= m a xc * + d ， s t c q + d * w s 形c d 是整数 那么上界就是 吒= 【铡 仅仅估计上界是不够的，因为这些简单计算的上界结果都是非常粗糙。它针 对某些特殊的情况有非常好的效果，但是不能指望它们在任何情况下都发挥同样 大的用处。 为了结合4 区块的划分设计，必须针对4 区块的摆放设计一个下界的估计， 这里参考s t e u d e l 的算法 1 9 】。 翻 l 目 。 ：a l豹 弱 劐 图3 1 04 区块的一种简单排列方式 如图3 1 0 ，四个区块都只考虑非常简单的排列方式。区块l 和区块3 都是把 小矩形竖放，而区块2 和区块4 都是横放。每个区块的摆放都是行列整齐的模式， 因此只要枚举一下每个分别放了多少个小矩形，就可以很方便的列举出来。 把边沿顺时针从1 到4 编号，逐一计算。则计算公式如下： b 例= m a x 五吖+ 晶+ r j ( s - 9 ) l + y 。s 巩佛= 1 2 3 4 ) 其中f ( s o 表示紧靠第 条边的小矩形按照一定的摆放方法，能够放下的最 大数值。 曷表示紧靠第弗条边有多少个小矩形是按长边与此边接触的方式摆放。 晶表示紧靠第一条边有多少个小矩形是按短边与此边接触的方式摆放 石和靠两个参数决定了第一条边附近小矩形的摆放方式。 风表示第栉条边的边长 品是状态变量，定义了蜀和圪的状态。 那么区块i 的大小就可以由蜀和珞，决定了。 只要枚举蜀，就逐步推算出只) 的值。 因为这里的目的只是求一个下界，所以准确度要求并不十分严格，只要能够 保证得到的结果必然存在一个摆放方式能够实现就足够了。因此，为了简单起见， 这里规定枚举的区块1 与区块3 必须相交，而且相交部分无论长还是宽都必须少 于一个小矩形的长和宽。这种情况下，区块2 与区块4 必然不相交。那么到最后 排列的时候把它们相交部分的那一个小矩形移走即可。而且这种排列方式必然是 4 区块，只用切割线是无法做到这样排列的( 如图3 1 1 ) 。 图3 1 14 区块的重叠 有了上界和下晃，接下来的工作就只不过是在p a c k i n g _ 2 d _ i m p r o v e 过程一开 始的时候加上一个判断： 3 5 层的划分方法 如果经过过程p a c k i n g _ 2 d _ i m p r o v e 的计算，就可以知道每选择一个层的高 度，就可以往该层填充多少盒子。根据这些信息，层的划分就可以做到更加准确。 假设当选择d = 西时，能够往该层填充的盒子个数为 ，那么层的最优划分 为： m a x x i v i + 动心+ + 而h s 上x l d t + x 破2 + 斗x 蠢r - = d 2t h e ng 【z 】- - - m a x ( g 【z 】，g 【z d 2 】+ v 2 ) ；e n a - i f i f z = d 3t h e ng 【z 】- - m a x ( g f z 】，g 【z d 3 】+ v 3 ) ；e n d - i f e n d - e o z z e t u z n 层的最优划分结果g 【l 】； 第4 章实验结果及分析 4 1 二维装箱的测试 尽管二维装箱的算法不是本问题的重点，但是本文的算法是建立在此基础之 上，它的好坏从一定程度上决定了三维装箱算法的优劣为此，首先对二维装箱 过程p a c k i n g _ 2 d _ i m p r o v e ( 记为p 2 d i ) 的效果进行测试。 文本的算法使用c + + 实现，并在w i n d o w s 下用开源编译器g 什( g c c ) 3 4 2 完成编译，所有测试用例均运行在p e n t i u m 41 5 0 0 g h zc p u 上。 表4 - 1f 2 d i 与y o u n g - g e n 和m a i n g - k y u 的装箱数比较( 单位：个) 表4 - 2 p 2 d i 与y o u n g - g u n 和m a i n g - k y u 的时间比较( 单位：秒) y o u n g - g u n 和m a i n g - k y u 2 0 使用了5 区块的算法对两组，总共1 7 项测试数 据进行计算。这两组数据d 1 d i i 和n 1 - n 6 分别来自于d o w s l a n d 2 l 】，以及 n e l i l k n 2 2 的实验。运行结果( 如表4 - 1 ) 与p 2 d i 完全一致，这是因为y m 算 法所使用的5 区块划分其实并不会比4 区块划分更加有效。在理论上，5 区块划 分也可以用4 区块划分来表示从时间上来看，y o u n g - g u n 和m a i n g - k y u 以1 秒为时限计算这两组数据，而p 2 d i 计算时间在0 3 秒之内。y o u n g - g u n 和 m a i n g - k y u 从s - e l e c t r o n i cc oc o n t a i n e r - l o a d i n gg u i d e 选取了多组数据进行运算， 其中有多组数据需要比较长时间( 如表化) ，它找到第一个次优解的时间都在1 秒以上，完成计算最优解最长需要1 6 秒。p 2 d i 则在1 秒内能得到y m 的最优解 ( 这个最优解只是y m 得到的最好结果，并不是数据的最好结果) 考虑上测试 环境的不同，需要给p 2 d i 的时间加上一个c p u 速度比系数( 本实验环境下c p u 速度约为前者的4 倍) 。但仍然可见，p 2 d i 对于较大规模的数据在不减弱结果的 前提下具有时间上的优势。 由d o w s l a n d 提出的方法，并生成的数据集c o v e ri 1 7 是被用于测试二维装 箱问题的最常用数据。其包含的7 8 2 7 个数据，其矩形长宽比具有如下特征： l ，隧2 1 l w 一4 l 阡肌5 0 经过测试，p 2 d i 得到了全部七千多个数据的最优解。每个数据运行时间约 0 1 秒，最大数据运行时间o 5 秒。从实验结果可以看出，算法单独运行效果很 好。 4 2 三维装箱的测试 香港大学w a i y i pk o o 2 3 】对同样问题进行过研究，并且取得比较好的结果。 本测试将沿用其数据。 用随机方式生成箱子以及盒子的大小。箱子的边长取值- 与n n 2 0 0 5 0 0 ，而 盒子的边长则在 z o ，2 0 0 中。为了集中考虑中等大小尺寸，箱子和盒子的数据都 被分成三组。总共生成5 0 个箱子，划分成三组：a 组1 0 个，边长不超过3 0 0 ： b 组3 0 个，边长介于2 0 0 到4 0 0 之间；c 组1 0 个，都是边长不少于3 0 0 的大箱 子。生成的5 1 个盒子也被分为三组：a 组1 2 个，边长范围从2 0 到1 0 0 ；b 组 2 7 个，边长范围从l o 到1 0 0 ；c 组1 2 个，边长都是不少于1 0 0 。 最后k o o 用于测试的箱子和盒子的大小分别列于表4 3 和表4 - 4 。 表4 - 3 三组箱子a ，b 和c 箱子集a箱子集b箱子集c 2 4 3 2 2 9 2 7 4 3 7 4 3 5 4 3 0 63 6 2 2 5 2 2 1 83 3 4 3 8 12 6 4 3 9 7 3 5 7 3 8 1 2 2 4 12 4 7 2 7 6 3 1 6 2 4 42 8 7 3 2 4 2 2 5 6 3 3 7 2 6 73 6 2 3 7 5 3 8 1 2 2 12 5 2 2 2 13 6 0 2 8 6 2 8 42 3 7 13 1 03 7 0 2 9 6 3 4 83 2 3 3 4 3 3 2 1 8 2 1 5 2 1 42 1 2 3 2 3 22 7 3 2 5 33 6 83 9 5 2 4 7 2 5 23 3 3 5 8 2 3 6 2 5 3 2 3 2 5 2 2 12 6 32 7 4 2 1 0 2 9 22 4 2 3 4 2 2 7 13 7 0 3 8 8 3 2 4 7 2 5 9 2 5 73 9 5 2 5 3 3 3 83 7 9 3 7 9 2 0 22 7 6 2 3 3 93 9 0 3 3 7 3 4 5 2 4 13 0 0 2 5 1 3 5 2 2 4 6 3 2 62 2 8 2 2 6 3 0 22 6 23 3 2 2 2 63 4 5 3 3 9 3 4 4 2 3 0 2 1 9 2 4 73 0 0 2 6 7 3 6 93 2 0 3 1 9 3 2 1 3 3 3 2 3 3 63 5 3 3 7 0 3 2 4 2 0 5 2 3 72 5 32 3 3 2 0 3 2 8 6 3 2 0 3 9 6 2 4 13 5 3 3 1 2 3 1 53 8 2 3 8 13 4 7 2 0 8 2 3 32 2 03 4 8 2 7 6 3 2 43 3 23 5 12 5 82 8 0 3 9 7 2 3 73 9 7 3 3 5 3 6 5 表4 - 4 三组盒子a ，b 和c 盒子集a盒子集b盒子集c 4 16 7 7 71 0 4 2 2 9 81 1 0 1 1 2 3 35 67 h 7 1 1 51 4 4 1 4 2 1 7 53 8 3 61 7 2 9 11 2 5晒1 5 6 3 11 3 81 4 5 4 81 3 7 1 9 7 1 6 1 3 3 2 3 2 44 6 1 1 16 41 4 2 1 1 9 3 74 0 7 6 1 2 41 4 4 1 8 8 1 4 3 2 82 8 6 3 1 3 3 1 9 6 1 1 63 6 4 5 1 4 72 2 1 3 4 1 4 91 8 4 1 6 2