（应用数学专业论文）集装箱装载优化算法研究.pdf

集装箱装载优化算法研究 内容提要 本文对运输行业中普遍存在的集装箱装载问题( c o n t a i n e r l o a d i n gp r o b l e m ) 进行了研究。针对目前此类问题在实际操作中 存在的效率和效益低下的问题，论文着重研究了采用何种算法以 提高集装箱装载货物的空间利用率的问题，并针对实际操作中最 常见的此类问题中的一个分支弱异类问题给出了一种新的算 法。文章首先介绍了问题的研究背景以及相关概念。其次，描述 了目前对此类问题的国内外研究情况，并且对几种经典算法进行 了较为系统的分析和评测，指出它们各自的特点和不足。再次， 根据对不同算法的特点的分析比较发现，由于装载问题是n p h a r d 问题，故单纯地采用构造型启发式算法或基本遗传算法或二 者简单的结合来解决此类问题都有本身无法克服的缺陷。因此提 出了一种基于构造型启发式规则和自适应技术的混合遗传算法来 尝试求解集装箱装载问题。最后，通过模拟实验得到了较以往算 法更好的测试结果，因此表明本文算法的可行性和有效性。 关键词：集装箱装载，弱异类，n p h a r d ，构造型启发式，遗传 算法，自适应技术 集装箱装载优化算法研究 a b s t r a c t 1 1 1 et h e s i si sc o n c e r n e dw i t hc o n t a i n e rl o a d i n gp r o b l e m ( c l p ) ， w h i c hh a sw i d e l yc o n s i s ti nt h ec a r r y i n gt r a d e i na i l u s i o nt o1 0 w n e s s o ft h ee m c i e n c ya n dt l l eb e n e f i to f 廿l ec l pi na c t u a lw o r kp r e s e n t l y , t h et h e s i sm a i n l ys t u d i e sa l g o r i t h m s 血a tc a l lg r e a t l yi m p r o v et h es p a c e u t i l i z a t i o ni nac o n t a i n e r a n d 也et h e s i sh a sg i v e nan e wa l g o r i t h mi n t h ec o n d i t i o no ft h ew e a k l yh e t e r o g e n e o u s 。w h i c hi st h em o s tf a m i l i a r b r a n c ho ft h ec l pi na c t u a lw o r k f i r s t l y ，t h et h e s i si n t r o d u c e st h e b a c k g r o u n do f t h ec l pa n ds o m ec o r r e l 砒i r ef u n d a m e n t a lc o n c e p t i o n s s e c o n d l v t h et h e s i se x p o u n d st h ed e v e l o p m e n ta b o u tt h ec l pa th o m e a n da b r o a d ，a n dp o i n t so u tt h es t r o n g p o i n ta n dl i m i t a t i o no fs o m e c l a s s i ca l g o r i t h m s ，b ys y s t e m a t i c a l l ya n a l y z i n ga n d e v a l u a t i n g t h i r d l y , b yt h ec o n t r a s to ft h ea f o r e m e n t i o n e da l g o r i t h m s ，t h ea r t i c l ec o n s i d e r s t h a ti ft ou s et h es i n g l eh e u r i s t i ca l g o r i t h m so r s i n g l eg e n e t i c a l g o r i t h m so rt l l es i m p l ei n t e g r a t i o no f t h e mt os o l v et h ec l p , w h i c h i s b e l o n gt on p - h a r dp r o b l e m s ，t h e r ea l em a n yd e f a u l t st h e yc a n n o t o v e r c o m e s ot h et h e s i sb r i n g sf o r t hah y b r i dg ab a s e do nt h e h e u r i s t i cr u l ea n dm o d i f i e da d a p t i v ep r o b a b i l i t i e so fc r o s s o v e ra n d m u t a t i o nt ot r yt os o l v et h ec l p f i n a l l y , b yt h es i m u l a t ee x p e r i m e n t s t h ea r t i c l eo b t a l n st h ep r c f e m b l er e s u l ti te x p e c t s 。w h i c hs h o w $ t h e a l g o r i t h m 也e 也e s i sg i v e si sf c a s i b l ea n de 伍c i e n c yt o 也ec l p - k e y w o e d ：c l p , w e a k l yh e t e r o g e n e o u s ，n p h a r d ，h e u r i s t i ca l g o r i t h m ， g e n e t i ca l g o r i t h m ，a d a p t a t i o nm e t h o d - 2 - 集装精装载优化算法研究 第一章引言 1 1 课题背景及意义 随着中国加入w t o 的重大利好消息，福州乃至全国的集装箱 运输业将面临前所未有的发展机遇。但由于物流规模和物流成本 在不断上升，使得在生产和运输规划中，有效的利用空间的重要 性越来越突出。大型零售连锁企业、船公司和船务公司、进出口 公司等在集装箱中进行不同货物拼装时，对拼装的效率和效益有 很高的要求。现在的人工估计拼装方法，往往在确保全部装下的 前提下，需要保留足够空间，浪费了宝贵的远洋货运空间，提高 了运输成本。因此，降低运输成本，提高集装箱利用率以及装箱 效率，将显现出可观而直接的经济价值和社会价值。利用计算机 强大的数据处理功能可以生成科学、高效的装箱编排方案。集装 箱装载问题( c o n t a i n e rl o a d i n gp r o b l e m ，以下简称c l p ) 就是从 该应用背景中抽象出来的模型问题。 本文所提出的课题是在与福州港城国际船舶代理有限公司合 作开发船舶代理管理系统过程中由港城国际提出的迫切需要解决 的问题。福州港城国际船舶代理有限公司目前在福建省远洋运输 领域居第四位，是一家实力雄厚的船舶代理企业。业务范围主要 包括船舶和货物代理。本课题是整个船舶代理管理系统中的一个 子系统，根据实际调研，我们了解到目前绝大多数的货物运输代 理企业在利用集装箱装载货物时。完全依靠人工调度来进行。调 度员在现场凭借经验估计被装入的几种盒子的数量及所需集装箱 数，并开出装箱单据。然后，装箱工人按照单据将盒子放入集装 集装箱装载优化算法研究 箱。这种操作程序存在两方面的问题：一方面，虽然调度员经验 丰富，可是单凭直观经验估计出来的数字却很难保证集装箱的高 利用率，因而经常出现集装箱未被装满的情形；另一方面，装箱 工人在装箱时没有任何装箱方案的依据，完全是随意地或经验式 地将盒子装入集装箱内。这种装载的随意性同样造成由于盒子摆 放不合理而导致的集装箱利用率很低的问题，甚至经常出现装箱 单上的盒子不能装入集装箱而重新改写单据的现象。 事实上，集装箱装载问题是货物运输中的重要环节，是一类 具有广泛行业背景的问题。如何摆脱人工操作的落后局面，同时 给出一个合理的布局及装载方案，以提高集装箱的空间利用率和 装箱的效率，是本课题的主要研究目标。实现这些目标，将会给 许多行业带来巨大的经济效益。 1 2 裁剪与装填问题概述 集装箱装载问题实际上是一种三维装箱问题，这类问题属于 裁剪与装填问题( c u t t i n ga n dp a c k i n gp r o b l e m s ) 的一个分支。 1 2 1 裁剪与装填问题 裁剪问题，通常是指在一种材料上寻找各种形状的最佳布局 以使材料的浪费率最小。装填问题则通常是指将若干小的物体以 最佳方式组合并装入一个大的空间从而使得空间的利用率最大 1 1 。 集装精装载优化算法研究 图卜1 下料问题( 二维裁剪问题) 侈够 待装入的盒子 图卜2 三维装箱问题 对裁剪与装填问题的研究最早出现在大约五十年代。当时人 们试图使用线性规划求出在一大片材料上合理放置矩形块的最优 解。但是，随着问题规模的增大和不规则形状的引入，人们发现 不可能遍历全部的搜索空间，于是近年来出现了对不同材料与形 状、不同目标、不同约束等情况的裁剪装填问题的各类算法研究。 1 2 2 裁剪与装填问题分类 尽管从称谓上看，裁剪问题与装填问题属于完全不同的两类 问题，而且被很多人当作两类不同的问题进行研究，但就本质而 言，这两类问蹶有着天然的内在联系，以致于很难有一个严格的 界限将它们区分开 i 。首先，它们都有两组最基本的数据，一组 集装葙装载优化算法研究 是大的空间或原料，另一组是小的物体或形状；其次，它们在本 质上都是一种几何组合，即将小的物体或形状进行某种组合，使 之能充分利用大的空间或原料。具体来讲，在装填问题中，可以 把向大空间( 比如集装箱、卡车、货架等) 中装入小物体的过程看 作是将大空间以最小的浪费为目标裁剪成若干小空间，每一个小 空间对应一个小的物体：反之，在裁剪闯题中，可以将裁剪过程 看作是将小的形状以最大的原料利用率为目标组合装入大的原料 中。因此，我们把这两类问题当作一类大的问题来讨论。例如， 图卜1 既可以看作是一个二维裁剪问题，又可以看作一种二维装 填问题。图卜2 既可以看作是一个三维装箱问题，又可以看作是 一个三维长方体裁剪问题。 裁剪与装填问题是在一维、二维、三维物理空间中进行的。 从这个角度出发，裁剪与装填问题可以分为：各种原材料的裁剪 问题( s t o c k c u t t i n gp r o b l e m ) ，包括一、二、三维裁剪问题 ( m u l t i d i m e n s i o n a lc u t t i n gp r o b l e m ) 。各种装填问题，即布局 问题，包括：一、二、三维装填问题( m u l t i d i m e n s i o n a lp a c k i n g p r o b l e m ) 。其中，三维装填问题又可细分为单元装箱问题( b i n p a c k i n gp r o b l e m ) 、集装箱装载问题( c o n t a i n e rl o a d i n g p r o b l e m ) 、货盘装填问题( p a l l e tl o a d i n gp r o b l e m ) 等。上述分 类又可进一步按物体的形状分为规则形状问题、不规则形状问题 等等。 1 2 3 裁剪与装填问题的常用算法 对于裁剪与装填问题的研究最终耍落实在给出具体算法。目 前这领域常用的算法分为确定性和启发式两种。确定性算法主要 集装箱装载优化算法研究 包括线性规划、整数规划、动态规划等传统算法。这类算法只能 解决小规模问题，由于这类问题已被证明是n p - h a r d 问题，情况 更加复杂，确定性算法就会因为涉及的变量太多而大大提高计算 的复杂性，因而不能在合理的时间内给出最优解 2 。所以，我们 只能依赖于启发式方法来解决这类问题。 1 3 集装箱问题概述 集装箱装载问题( 以下简称c l p ) 的研究始于国外。自1 9 3 9 ( k a n t o r o v i c h ) 、1 9 4 0 ( b r o o k s 等) 以来，由于行业需要，国 外开始出现裁剪与装填问题( 以下简称c p ) 的研究。研究的重 点开始集中于一维、二维问题上，且多见于使用确定性算法。二 十世纪八十年代以后，对三维c p 问题的研究才逐渐展开。此时， 随着问题解空间的加大，确定性算法逐渐被抛弃，取而代之的是 各类启发式算法。作为c p 问题的一个重要分支。新西兰的g e o r g e j a 和r o b i n s o nd f 给出了c l p 的第一个启发式算法。此后， 许多科学家就不同层面的c l p 提出了各自的算法或解决方案，并 使用了公开的测试数据进行测试，以求探索一种解决问题的有效 算法。迄今为止，还没有一种算法能够肯定在各个方面均优于其 它算法，所以仍旧有许多人对c l p 进行研究。从国内情况看，对 此类问题的研究工作开展得较少，以致于绝大部分运输行业或运 输环节都处于一种人工管理的落后阶段。由此看出，无论从理论 角度，还是从实际应用出发，探讨一种有效的算法，以更好地解 决c l p ，并将装载策略付诸实旅是非常必要的。为此，有必要充 分了解、分析已有的算法，为算法的改进打下扎实的基础。 集装箱装载优化算法研究 1 3 1 集装箱问题分类及常用算法 针对三维集装箱装配问题，从目前的文献来看主要可以分别 从集装箱和货物两方面考虑，大致有4 种配装情形，即单个集装 箱序贯配装与多个集装箱的并行配装、相同体积货物与不同体积 货物的配装 1 。对于不同体积货物的配装情形，b o r t f e l d t 将只 有少数几种不同体积的货物但每种货物数量较多的情况称为弱差 异情形( w e a k l yh e t e r o g e n e o u s ) ，反之多种不同体积的货物但每 种货物数量较少则称为强差异情形( s t r o n gh e t e r o g e n e o u s ) 3 。 研究方法有线性规划、动态规划方法、启发式算法及严谨启发式 算法( 包括模拟退火算法、禁忌算法、基因算法) 等等。 1 3 2 集装箱问题描述 根据目前文献，集装箱装载问题的研究主要集中在：从集装 箱方面来看，集装箱个数不多且种类少( 在远洋运输中，集装箱 的规格是严格定义的，对于较特殊的货物需要较特殊的集装箱， 一般的企业是不允许代理的) ；从货物方面来看，企业代理的货物 大都是种类不多，但每种货物的数目较多的情况即弱差异情形。 此类问题可以描述如下： 对于一个已知尺寸的标准集装箱( 2 0 英尺或4 0 英尺) ，以及 一组( 九类) 已知尺寸的带装箱的长方体盒子，本文的目的是确 定一种集装箱装载方案，以便尽可能将所有的盒子装入集装箱； 如果不能将所有的盒子装入集装箱，则本文的目的是找到一个待 装盒子的子集，以使集装箱的空间利用率以及装载效率最高。 该问题的数学模型是： 假定集装箱的长、宽、高为d 、j 形，待装箱的”类长方体 集装箱装载优化算法研究 盒子的长、宽、高为吐，w f ，曩( f - l ，2 ，疗) 。问题的目标函数为； 上 m a xf = 4 w , h , d 聊 l = 1 约束条件如下： ( 1 ) 方向的约束：在装载中，货物的摆放方向受约束，例如有 些货物的包装标有向上的箭头等。一般货物装载时的方向约束可 归纳为三种约束，既任意旋转、水平旋转、不能旋转。 ( 2 ) 承载能力的约束：在装载过程中，货物所能承受的最大 压力受限制，否则下面的货物会被上面的货物损坏，所以装载层 数、装载顺序要受限制。 ( 3 ) 稳定性的约束：装载完后，货物的重心应在集装箱的几 何中心附近，以利于运输安全。 ( 4 ) 货物的配置位置：货物的种类千差万别，货物不能任意 摆放。有些货物不能摆放在其它货物之上。 ( 5 ) 货物装载顺序：不同的货物在装载中应按不同的优先顺 序装载，例如货物的到站顺序不同，因此装载顺序相应的不同，先 到站的货物要后装。 ( 6 ) 装载的均匀性：在多集装箱装载中，有时要考虑多个集 装箱之间的平均高度或平均重量。 对于上述模型，有必要进行如下的补充说明： ( 1 ) 本文研究的是单一集装箱的装载问题。 ( 2 ) 本文采用的坐标系为三维笛卡儿坐标系( 如图卜3 ) ， 该坐标系以集装箱的长度( 或用深度表示) 方向为x 轴，集装箱 的宽度方向为y 轴，集装箱的高度方向为z 轴。集装箱的左后下 集装箱装载优化算法研究 角为坐标原点( 0 ，0 ，o ) 。 ( 3 ) 本文的问题如上所述，属于单个集装箱序贯配装弱差异 情形的货物，并且货物的的长、宽、高不能超出集装箱的长、宽、 高。 ( 4 ) 包装盒子的摆放必须于坐标轴平行或正交，而不能斜放 且不能悬空放置。 ( 5 ) 为了保证货物的稳定性，集装箱的几何中心即为重心。 上述的假定可以使问题模型简化，并且足以适用于很多实际 环境。 僻) o 1 4 国内外研究概况 图1 - 3 坐标轴 目前，国外的研究主要也是集中在单个集装箱配装的情况， 一般先假定货物的体积与其运费相当，因此问题转化为求集装箱 的最大容积利用率。单集装箱配装又可进一步分为相同体积货物 和不同体积货物的配装情形。 ( 1 ) 相同体积货物的配装 s c u l l i 和h u i 、h a r t 和g e o r g e 针对同等体积大小的货物分别给 出了启发式配装方法 4 6 。s c h e i t h a u e r 给出了基于动态规划前 向策略的近似算法，对于1 0 0 件左右的货物的配装。运算时间是可 集装箱装载优化算法研究 以接受的 7 。富佩珊针对单一产品无摆放限制的情况提出一种递 归的方法 8 。 ( 2 ) 不同体积货物的配装 对于体积大小不等的货物装配，大多数方法假定配装对象为 弱差异情形，见l i u 、l o h 、m o r a b i t o 、n g o i 、g e o r g e 等人论文 9 1 3 。从概念上讲，弱差异情形下装箱的方法也适合于强差异情形， 但根据b i s c h o f f 分析，方法的性能取决于货物的种类和数量，同 样数量达几百件的货物，如果把针对十几种体积规格的配装方法 用来解决只有两三种体积规格的货物情况，效果并不见得理想 1 4 。b o r t f e l d 提出一种适合于弱差异情形的禁忌算法( t a b u s e a r c ha l g o r i t h m ) 1 5 。另) b g e h r i n g 提出遗传算法可以很好地 解决强差异和弱差异货物地配装问题。 相对地，目前国内的集装箱装载问题( 包括广义的三维装箱 问题) 及其相关问题的研究相对较少，主要有： 1 北方交通大学机电工程学院的何大勇等人 1 6 提出了一种 利用三叉树结构描述三维矩形物体布局状态的方法来解决集装箱 装载问题。该算法是一个构造型启发式算法。算法中，盒子的尺 寸由计算机随机产生，算法没有提到盒子的特征以及所属问题的 类别。这种算法相当于2 4 2 的算法。盒子被逐一放入，没有处理 空隙问题。 2 天大机械工程学院的王金敏等人用标准模拟退火算法求解 三维布局问蹶 1 7 。该算法没有提到三维矩形物的种类情况，即 没有具体的问题背景。算法中给出了目标函数及约束条件，求解 的初始温度和退火策略( u p d a t e ( ) = 0 8 5 - 0 9 9 ) 。该算法的初始 集装鲫装载优化算法研究 解采用随机解。邻域解通过随机移动操作产生。算法收敛速度较 慢，同时没有明确给出和其它算法的比较测试结果。 3 中国科技大学计算机科学技术系的曹光彬等人先后给出了 采用遗传算法和免疫遗传算法解决装箱问题的算法 1 8 1 9 。但 算法没有给出问题的实际背景。他们的第一个算法是一个标准遗 传算法。第二个算法是对第一个算法的改进。遗传算法改用免疫 遗传算法。在免疫遗传算法中编码仍旧采用二进制编码，选择抗 体采用了一般轮赌法。 算法给出了实验结果和布局平面图。由于算法只是从随机产 生的0 ，l 染色体编码出发，采用标准的遗传算法和标准的免疫遗 传算法来解决问题，难以保证解的优异性。另外，该算法没有涉 及如何保持由下而上的每层中小长方体高度一致的问题。从该算 法的结果来看，小长方体会出现悬浮放置或倾斜放置的问题。 1 5 本文的主要工作 如前所述，较好地解决c l p 问题将具有十分重要的意义。本 文将就工作人员在集装箱装载的实际操作过程中存在的效率不 高，空间浪费多等问题着力进行如下的工作：提出一种利用构造 型启发式算法的成熟性和改进的遗传算法的优势相结合的有效的 集装箱装载算法，即将几种不同规格的长方体盒子( 经包装后的 货物) 合理有效地放入单个集装箱，以提高集装箱的空间利用率， 并为类似问题的解决提出种新的思路。 1 6 本文的结构 本文的第一章介绍了问题的背景，问题所属的研究领域，对 1 0 集装箱装载优化算法研究 本文研究方向的描述以及国内外的研究情况。 第二章对构造型启发式算法在集装箱装载问题上应用的进行 研究，并且通过对几种经典算法系统地分析，指出其所具有的优 点和不足之处。 第三章首先介绍了遗传算法的相关概念，接着描述基本遗传 算法的工作原理及理论依据，最后简述了遗传算法的发展情况和 在集装箱装载问题上的应用情况，并较为详细地分析了此类应用 的一个典型算法一- - g e h r i n g 和b o r t f e l d t 算法。通过g b 算法的结 果，我们可知采用遗传算法来解决集装箱装载问题是一个可行的 方案。但是，要想得到更优的结果则必须寻找更好的技术来提高 和改善已有的算法。 第四章具体阐述了本文所提出的算法并通过模拟实验给出结 果及分析。通过前面两章的叙述和分析，作者提出了遗传算法的 基础上结合构造型启发式算法的优点，以及对遗传算法的控制参 数进行改进的思路，并且通过m a t l a b 进行了模拟实验，结果证明 了本文思路的可行性和有效性。 集装箱装载优化算法研究 第二章构造式启发式算法在o l p 中的应用 2 1 启发式算法概述 在最近的二十多年中，启发式方法已经成为一个重要的科研 领域。其引人之处在于它能够迅速得到复杂最优化问题的近似最 优解，同优化领域的纯数学方法相比更具有艺术性和创造性，因 此吸引了众多的科技工作者。启发式方法的起源要追溯到 s i m o n 2 0 的有限合理性原理( b o u n d e dr a t i o n a l i t y ) 。而 p e a r l 2 1 在其关于启发式方法的专著中对启发式方法进行了详 细的论述，并给出了启发式算法( h e u r i s t i ca l g o r i t h m ，h a ) 的 定义。所谓启发式算法是指一组指导算法搜索方向的、建议性质 的规则集，按照这个规则集，计算机通常可在解空间中寻找到一 个较好的解，但并不能保证每次都能找到较好的解，更不能保证 找到最优解。换句话说，所谓启发式算法就是那些从大量的实验 数据来看，算法的实际计算性能较好，但理论上证明这些算法的 最坏解题性能并不好，或者理论上并不能证明这些算法具有优良 的性能。由于启发式算法的设计不依赖于纯数学中优化理论的突 破和发展，因此其研究和应用在近二十年来获得了突飞猛进的发 展。 z a n a k i s 2 2 和s i n c l a i r 2 3 通过对1 9 7 3 年到1 9 9 3 年发表 的关于h a 及其应用文章的研究，将h a 分为1 2 类。从其分类可以 发现，启发式方法的特点是把知识同搜索相结合，用搜索来弥补 知识的不足。对已有知识如何组织以及采用什么样搜索方法是上 述划分的重要依据。 集装箱装载优化算法研究 启发式方法大多基于特定的应用领域，不同的方法在不同的 应用领域所收到的效果是不同的，很难找到一个通用的样题来测 试和评价不同方法的优劣。另外，启发式方法的问题求解过程是 一个求解时间和解的质量的协调过程。要想尽快得到问题的近似 解，就必须减少搜索量，这必然导致解的质量较差：若想得到高 质量的解，必须增大搜索量，但要付出大量的时间。从某种意义 上来说，求解时间和追求解的质量是一对矛盾。因此，很难说哪 种方法最优，只能在具体应用时根据问题的实际情况选择合适的 方法或方法组合，以求得二者的最佳折衷。 2 2 层的概念 在求解c l p 的诸多启发式算法中，为了便于装填，大都引入 了层( 1 a y e r ) 的概念 2 4 2 5 。即把集装箱的装入看作一层一层地 装入。所谓层，有水平和竖直之分。水平方向的一层是指，铺满 x y 平面，但是沿集装箱的高度方向只装填了一个基本单位的所有 盒子( 本文简记为x y 一 z 层) ；竖直方向的层则是指，铺满y z 或x z 平面，但是沿集装箱的深度或宽度方向只装填了一个基本单 位的所有盒子( 本文简记为y z - x 层和x z - y 层) 。在引入了层的 算法中，装箱的顺序是：从原点出发，开始装填一层，一层装好 以后。再开始新层的装填，直至将集装箱装满或将盒子全部放入。 每一层的深度由这一层中第个盒子的长度决定。这种按层装入 的方法通常也叫做砌墙法( w a l lb u i l d i n g ) 。 2 3 利用构造型h a 求解c l p 的研究情况 构造型h a 是一类凭借专家经验建立直接的搜索策略和搜索规 1 3 集装箱装载优化算法研究 则，并依此规则在搜索空间中求解的算法。由于采用经验机制， 没有任何严格的理论证明，所以这类算法无法保证找到最优解。 而另一方面，由于规则的建立具有一定的合理性，虽然不能保证 得到最优解或近似最优解，但通常也能得到一个令人满意的可行 解。再加上算法描述直观，易于实现，非常具有实用价值。所以 目前c l p 的大量研究集中在这类算法上。以下列举此类算法中几 种具有代表性的算法。 2 3 1g e o r g e & r o b i n s o n 算法 g e o r g e 和r o b i n s o n ( 以下简称g r ) 首先采用构造型 a 来解 决c l p 2 4 。他们把研究的问题集中在多种盒子( 8 种至2 1 种， 且每种盒子的数量很多) 的装填上，这些盒子可以以任意的方向 放置。在算法上他们首次给出了层的概念，这一概念对后来相继 出现的算法产生了很大的影响。 他们的算法中有两个非常关键的地方：一是层的概念的引入 ( 他们使用的是竖直的y z 一 x 层) ，二是如何确定待装填盒子的优 先顺序( 即应该先装入哪类盒子) 。 盒子的优先级别涉及到两个方面：首先，每一类盒子被赋予 两个状态：打开状态( o p e n ) 和非打开状态( u n o p e n e d ) 。如果某类 盒子中已有一些盒子被装入箱内，则该类盒子被认为处于打开状 态；反之，处于非打开状态。处于打开状态的盒子将先被装入。 通常选取处于打开状态且尚未装入的盒子数量最多的那一类作为 新层的开始，因为，如果用数量较少的某类盒子来决定一层的深 度。会出现该类盒子不能把一层装满的情况。当一层中有两类以 上的盒子时，很容易造成不同盒子之间出现空隙，从而导致集装 集装较装载优化算法研究 箱的空间利用率下降。其次，对于处于非打开状态的盒子，g r 进 一步给出了一个含有三个级别的优先级标准，即先对每一类盒子 的长、宽、高三个尺寸中的最小尺寸进行排序，最小尺寸越大， 盒子级别越高，这样做的目的是考虑到最小尺寸最大的盒子，越 到后来越难以装入：对同处于这一级别的盒子，再按盒子的数量 分级，数量多者级别为先，之所以这样做，是考虑到一层中就尽 量装填同一类型的盒子，以提高层的空间利用率；如果按前两种 规则排序后，仍有两类盒子处于同一级，再对每一类盒子的长、 宽、高三个尺寸中的最大尺寸进行排序，最大尺寸越大，级别就 越高。这样做是为了尽早装入特别长的一类盒子。 优先级确定下来以后，就开始按照建层的方式装箱。前己述 及，g r 采用的层是y z 一 x 层，即装满y z 平面的沿深度方向的某 一竖直层。具体做法是：从原点出发，先装填第一层。一层中第 一个盒子的选取至关重要，因为，它决定了这层的深度。由于 装入第一层的第一个盒子之前，肯定没有处于打开状态的盒子， 所以按三级标准选出第一个盒子。对于以后各层，第一个盒子应 该从处于打开状态未被装入的盒子数量最多的类中选取，如果 没有处于打开状态的盒子，再按那三级进行选取。至于应把第一 个盒子的哪个尺寸作为层的深度，g r 并没有详细提及。 一旦装入了个盒子，就会在盒子周围产生三个空闲空间， 即它的正上方、右方和前方( 图2 - 1 ) 。装入下个盒子时，应以 前一个盒子为基准，按照先向上、再向旁边、最后向前的遍历方 式，选取优先级较高的盒子进行装填。一层装填完毕后，再沿集 装箱深度方向装填新层，直至盒子全部装入箱内为止。 集装箱装载优化算法研究 甘方曲窀州申旧 嘲夺两 图2 - 1g e o r g e 和r o b i n s o n 算法中的空间分割 在g r 算法中，还有一点需要特别提及。如果一层中出现了不 同类型的盒子，j 艮可能会使这一层的横截面产生一个或几个凹陷 ( r e j e c t e ds p a c e s ，被拒绝空间) 。g r 注意到了这个问题，并给 出了补救措施。他们将这个凹陷的深度及宽度保留起来，在对新 层进行装填时，将新层中的剩余空间与其前一层的凹陷空间有效 地融合在一起，作为新层中统一的可用空间一并处理，从而提高 了空间的利用率。 i ：二：= ：代表融音以币 舶待装填空问 图2 2g e o r g e 和r o b i n s o n 的融合空间 g r 算法中，有许多值得借鉴之处。如按层装填的思想使得算 法在一定程度上得以简化；优先级的确定可以保证较整齐地利用 集装箱空问：融合被拒绝的空间以提高集装箱的空间利用率等等。 g r 算法同样有值得商榷和改进的地方。 集装箱装载优化算法研究 1 按层装填的思路可以使问题简化，然而，在g r 的层装填中， 盒子是被一个一个放入的，而且是按照先向上、再向右、再向前 的递归方式进行的，每放入一个盒子，都要重新分析集装箱空间 的变化，这势必带来几方面的问题： 算法的时间效率低。很多盒子逐一被分析和处理，会浪费 大量宝贵的计算时间。 孤立地看待每个盒子会造成不同类型的盒子在同一层摆放 时出现可以避免的空隙。例如，假设有两类数量足够多的盒子， 一类底面积较大，但由于高度所限，沿高度方向只能装入个。 沿高度方向剩余的空间可以装入另一类底面积较小的盒子中的一 个。在一层中先自下而上装填第一条，按照g r 的装填机制，层中 第二条的结构显然与第一条相同，这会造成最上面的两个盒子之 间存在不应该有的空隙，从而降低集装箱的空间利用率( 图2 - 3 ) 。 如何尽量减少空隙的存在，应该是算法的改进方向。 固白 图2 3 ag r 的装填模式 图2 - 3 b 理想的装填模式 孤立地将每一个盒子按照先向上、在向右、再向前的模式 装入，会降低工人的装箱效率。相反，如果把一类盒子作为一个 整体考虑，给出一个装填方案，会大大方便工人的装卸工作，提 高实际的装卸速度。 2 g r 算法中，优先级的确定是结合他们所遇到的盒子的情形 而定，不具有广泛的代表性。 集装籍装载优化算法研兜 3 g r 算法中的空间融合是一个很好的考虑，但同样存在需要 改进的地方。从图2 3 可以看出，g r 只是将前一层中的一个被 拒绝的空间与新层中的可用空间进行了一次融合，事实上，仅仅 相邻两层之间的一次融合还不是理想的空隙融合技术。应该使前 面每一层内未被填充的相邻空间都可以融合在起，以对空隙进 行充分的填补和利用( 图2 4 ) 。 图2 4 较理想的空间融合技术 2 3 2 l o h & n e e 算法 l o h 和n e e ( 以下简称l n ) 的算法 1 0 主要考虑到待装载的盒 子有很多都具有相同的尺寸这一特点。即，他们研究的是弱异类 问题。在他们的算法中，层以水平的形态出现，即x y 一 z 层，各 层由下向上摆放，最终完成装箱工作。为了构建平坦的截面，该 算法按盒子的高度设置优先级别。为了分隔已被装填和未被装填 的区域，算法中定义了一个移动的边界。另外，为了能够跟踪盒 子之间高度的差异，算法设置了若干个节点。然而，由于集装箱 为后部开门，所以l n 的这种自下而上的装填算法不适于实际的集 装箱装载工作。 需要指出的是，l n 算法中给出的1 5 组检测数据被很多算法 用作标准的测试数据。本文也将其作为本文算法的测试算例。 集装精装载优化算法研究 2 3 3b i s c h o f f 和r a t c l i 仟算法 b i s c h o f f 和r a t c l i f f ( 以下简称b r ) 算法 2 6 与前面提及 的基于层的算法有许多相似之处。但由于他们考虑到会存在多目 的地运送的问题，所以他们的算法不是以层为构筑单位，而是以 一个由盒子组成的柱( 相当于前面提到的层中的每一条，以下简称 盒柱) 为构筑单位。尽管如此，b r 算法并不是一个纯粹的多目的 地运送算法。他们的算法完全适用于单目的地问题。他们的算法 中，盒子可以任意方向放置。算法既适用于弱异类问题，又适用 于强异类问题。 b r 算法依然基于空闲空间的装填，而且他们采用了n g o i 等人 2 7 使用的特殊空间表示技术来确定和描述空闲空间。该算法有 它的独到之处：在一个盒柱的构建当中，算法力争将相同的盒予 放在一起。而且盒子装填的优先级别并没有采用n g o i 等人的六个 级别，而是给出了一个新的优先级标准。 b r 算法中，盒子的优先级标准是整个算法最具特色的地方。 算法共确定了四个级别： 第一级空间利用率最大者。算法中的空间利用率的定义很具 特色。假设当前剩余空间的深度、宽度和高度分别为：x 、y 、z 其左后下角的坐标为( a ，b ，c ) ，待装盒子的尺寸用x 、y 、z 表示。 m 表示某类待装盒子的数量。只有当盒子的尺寸在各方向不超出 空闲空间的尺寸( 即x = xa n dy = - ya n dz 删，f ) 弓警【1 - 只篱。删 式畔a f ( h ，) 一模式在第t 代中适应性的平均值； ( r ) 一群体在第，代中适应性的平均值： 只一交叉概率； 匕一变异概率； 艿( ) 一模式的定义距离： o ( h ) 一模式的阶； n ( h ，t ) 一模式仃在第r 代中样本的期望值： ，一字符串的长度( 即位数) 。 公式只鱼等中的是模式日的一个样本通过交叉操作后被破 坏掉的概率；只- o ( h ) 是样本在变异操作后被破坏掉的概率i 而 公式项n ( h , t ) 等是模式日在经过选择操作后得到的样本 数。 模式定理是遗传算法的理论基础，其意义是深远的。它说明 集装箱装载优化算法研究 在遗传算法操作下，低阶、短距、高适应性的模式以指数级增长。 但为什么这样一种性质就有利于找到全局最优解呢? 统计确定理论中的双角子机问题表明：要获得最优的可行解， 则必须保证较优解的样本数呈指数级增长。而模式定理保证了较 优的模式( 遗传算法的较优解) 的样本呈指数级增长，从而给出 了遗传算法的理论基础。 3 3 2 积木块假设 模式定理中描述的这种较优模式有一个特殊的名字：积木块 ( b u i i d i n gb l o c k ) 3 2 。 定义4 具有低阶、短定义距离以及高于群体平均适应性的模 式称为积木块。 与搭积木类似，这些较好的模式在遗传算子操作下，互相拼 合，产生出更好的模式来，从而最终找到最优解，这就是积木块 假设的内容。 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) 积木块在遗传 算子的作用下，互相结合，能生成高阶、长定义距理、高平均适 应性的模式，最终生成全局最优解。 模式定理保证了较优的模式( 遗传算法的较优解) 的样本数 呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法 存在着找到全局最优解的可能性。而积木块假设则指出，遗传算 法具备找到全局最优解的能力，即积木块在遗传算子的作用下， 能生成高阶、长定义距、高平均适应性的模式，最终生成全局最 优解。 虽然积木块假设还只是一个假设，还没有得到理论上的证明， 集驶榭皴拽优化算法研究 但遗传算法在许多实际应用中的效果都支持这一假设。 3 3 3 遗传算法欺骗问题 提到积木块假设，这里就必须说明一下遗传算法欺骗问题 3 3 ( g ad e c e p t i v ep r o b l e m ) 。应用实践表明，存在着一类用遗传算 法难以求解的问题，称为“g a h a r d ”的问题。这类问题往往不 满足积木块假设，即由基因块之间的拼接，往往会欺骗遗传算法， 使其进化过程偏离最优解。 各种研究结果表明，属于“g a h a r d ”的问题一般包含有孤 立的最优点，即在这个最优点周围是一些较差的点，从而使得遗 传算法较难通过基因之间的相互拼接而达到这个最优点的模式。 实际上，目前也尚无解决这类问题的较好的方法。所幸的是，现 实所遇到的各种应用问题中，很少有这种奇怪的性质。 3 3 4 遗传算法的收敛性分析 虽然遗传算法作为一种有效的搜索算法，在实际应用中往往 能获得令人满意的结果，但该算法的全局优化的收敛性的理论尚 待解决。r u d o l p h 证明了h o l l a n d 的模式定理并不隐含着标准遗 传算法求解优化问题时能收敛到全局最优点 3 4 3 。这是因为s g a 的不可约性造成的，即其根本不可能收敛。 定理2 如果变异概率为己( o ，1 ) ，交叉概率为【o ，1 】， 同时采用比例选择法( 按个体适应性占群体适应性的比例进行选 择) ，则s g a 不能收敛至全局最优解。 这无疑是一个令人沮丧的结论。然而值得庆幸的是，只要对 s g a 做一些改进，就能保证其收敛性。r u d o l p h 用m a r k o v 链证明： 集装箱装载优化算法研究 如果改进的遗传算法采用了优秀个体的保护策略( 即优秀的个体 可直接进入下一代解群中，采用复制算子) ，那么改进的遗传算法 渐进地收敛于全局最优解。 由此可以看出，s g a 在任意初始化，任意交叉算子，以及任 意适应性函数下，都不可能收敛至全局最优解。然而通过改进遗 传算法，即在选择操作前或后保留当前的最优解，就能保证算法 收敛到全局最优解。因此，收敛至全局最优解，实际上是由于不 断地保留当前最优解的结果。 以上理论构成了利用遗传算法求解优化问题的理论基础。 3 4 遗传算法的缺陷 遗传算法是一个通用算法，可以被广泛应用到众多的领域。 但另一方面，在遗传算法的实际应用中也出现一些不尽如人意的 问题。最突出的问题是容易产生早熟现象、局部寻优能力较差等 等。 ( 1 ) 优化算法出现“早熟”现象所谓“早熟”现象指的是在 末达到最优解以前，搜索已经停滞，即成熟前收敛。之所以出现 如此现象，一方面是由于在基本遗传算法中经过许多代迭代后， 遗传操作中最重要的交叉操作使群体染色体具有局部相似性，父 代染色体的信息交换量太小，使搜索停滞不前：另一方面，选择 的变异概率太小，以至于不能驱动搜索转向其它的解空间进行搜 索。 ( 2 ) 非均匀地在优化空间中搜索最优解基本遗传算法在交 叉操作中一般选取单点交叉或两点交叉的方法，尽管在交叉位置 设置方式有所不同，但是其实质都是在人体所有基因位中等概率 2 r 集装箱装载优化算法研究 地随机选取一个基因位作为交叉位置。个体是对优化变量的编码， 一般来说，不同的码位具有不同的权值，改变人体中不同的基因 位值，将引进优化变量空间不同的变化量。因此，如果等概率地 选取交又位置并在此基础上改变相应的基因值，将不能均匀地在 优化空间搜索最优解，从而影响遗传算法的寻优性能。 3 5 遗传算法的发展 由于s g a 的缺陷，使得遗传算法在实际应用中受到了很大的 限制。因此，为了使遗传算法能在工程应用中得到更好的效果， 许多研究人员主要采用了两种方法：改进遗传算法( i m p r o v e dg a ， i g a ) 和混合遗传算法( h y b r i dg a ，h g a ) 。 3 5 1 改进遗传算法 为了克服基本遗传算法的缺陷，很多学者对遗传算法提出各 种各样的改进方案 3 5 。如：针对原来的二进制编码方案，提出 动态编码、实数编码、扩展串等改进方案：针对按比例的选择机 制，提出了竞争选择、按序选择等改进方案；针对原先的一点杂 交算子，提出了两点杂交、多点杂交、均匀杂交等算子；还提出 了退化遗传算法、自适应遗传算法等，此类算法使得控制参数在 进化过程中通过不断的调整收敛到全局最优解或近似最优解。 特别是在传统的遗传算法中，交叉概率、变异概率等控制参 数与种群进化过程无关，从始至终都保持定值。近年来的研究表 明 3 6 ，控制参数对系统性能有重要的影响。交叉概率的高低将 决定解群体的更新和搜索速度的快慢