（机械电子工程专业论文）集装箱布局问题求解方法研究.pdf

摘要 塞菱擅查旦装载问题是应用背景较强的离散组合最优化问题，在 其固有的n p 完全计算复杂性的基础上又增加了许多复杂的约束条件 和布局物体及布局空间的几何复杂性。所以集装箱布局问题很难求得 最优解，也很难应用数学模型精确求解。本文对该问题的求解理论和 方法进行了深入研究，将基于空间分解的启发式算法和遗传算法引入 到该问题的求解。f 主要研究内容如下： 首先对布局问题国内外研究现状进行了深入细致的了解，阅读了 大量文献，发现三维布局问题研究薄弱，确定集装箱布局问题为研究 对象。作者在现场进行了大量调研实践，进一步明确了本文研究内容 的可行性、方法、意义。 随后分析了现有应用于布局领域的启发式算法的特点和不足，提 出了应用空间分解的布局启发式算法处理集装箱装载问题。经过算例 比较，说明了其有效性。基于该算法，在大量数值实验的基础上，定 量地表达了空间利用率、待装物体总体积和待装货物类型三者之间的 关系，对货运生产提供了有力的决策支持。 通过现场调研发现，现场集装箱布局问题大多为多目标、多约束 优化问题，即复杂集装箱布局问题。遗传算法本身的鲁棒性、并行性 以及在n p 完全问题求解中的广泛应用，表明遗传算法是解决复杂集 装箱布局问题的有效途径。本文探讨了遗传算法在求解这一复杂问题 中的应用，给出了有效的编码形式和解码运算。算例求解结果显示出 很好的效果。 最后对全文工作进行了总结并对以后的研究方向做出了展望。上 他 关键词：集装箱装载问题、碡墀、启发式算法、遗传算法 a b s t r a c t c o n t a i n e r - l o a d i n g p a c k i n gp r o b l e m i s c a t e g o r i z e d a sd i s c r e t e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mw i t hs t r o n ga p p l i c a t i o nb a c k g r o u n d e x c e p t f o ri t si n t r i n s i c n p c o m p l e t ec o m p u t a t i o n a lc o m p l e x i t i e s ， c o n t a i n e r l o a d i n gp r o b l e m a l s oi n v o l v e s m a n y c o n s t r a i n t sa n dt h e g e o m e t r i cc o m p l e x i t yo fp a c k i n go b j e c t s a n dc o n t a i n e r t h e r e f o r e ，i ti s r a t h e rd i f f i c u l tt o p r e c i s e l ye x p r e s sc o n t a i n e r - l o a d i n gp r o b l e mu s i n g m a t h e m a t i c a lm o d e la n dg e tt h eo p t i m a ls o l u t i o no ft h ec o n t a i n e rp r o b l e m i nt h i s d i s s e r t a t i o n ，d e e p r e s e a r c ho nt h e t h e o r ya n dm e t h o d o l o g yo f c o n t a i n e r - l o a d i n gp r o b l e mi sc a r r i e do u t ，a n dt h eh e u r i s t i cm e t h o db a s e d o ns p a c ed e c o m p o s i t i o na n dg e n e t i ca l g o r i t h ma r ea p p l i e di n t ot h es o l u t i o n o f c o n t a i n e 卜l o a d i n gp r o b l e m t h em a i n w o r kc a nb eo u t l i n e da sf o l l o w s ： ad e t a i l e dr e v i e wo fc u r r e n tr e s e a r c hs t a t u sb o t hi n l a n da n da b r o a di s m a d eb yt h o r o u g ha n a b r s i so fl o t so fp e r t i n e n ta r t i c l e s ，b yw h i c ht h e r e s e a r c he m p h a s i so ft h i sd i s s e r t a t i o ni sf o c u s e do nt h ec o n t a i n e r _ l o a d i n g p r o b l e mb e c a u s eo f l i r l ee f f o r to nt h i sp r o b l e m t h ec o n t e n t ，s i g n i f i c a n c e ， f e a s i b i l i t yi s f u r t h e rm a d ec l e a ro nt h eb a s i so fo n t h e - s p o ti n v e s t i g a t i o n a n d s t u d y b a s e do nt h e a n a l y s i s o ft h ec h a r a c t e r i s t i c sa n ds h o r t c o m i n g so f v a r i o u se x i s t i n gh e u r i s t i cp a c k i n g a l g o r i t h m s ，ah e u r i s t i cp a c k i n ga l g o r i t h m b a s e do ns p a c e d e c o m p o s i t i o ni sd e v e l o p e dt o s o l v e c o n t a i n e r - l o a d i n g p r o b l e m t h es o l u t i o no fn u m e r i c a le x a m p l e ss h o w st h a tt h ea l g o r i t h mi s e f f e c t i v e w i t ht h e a t g o r i t h r aa n d l o t so fn u m e r i c a lt e s t ，t h er e l a t i o n s h i ph e x p r e s s e dq u a n t i t a t i v e l ya m o n g c o n t a i n e r u t i l i t yr a t e ，t o t a lv o l u m eo f b o x e s ， n u m b e ro ft h eb o xt y p e s ，w h i c hp r o v i d e ss t r o n gd e c i s i o ns u p p o r tt ot h e f r e i g h tp r o d u c t i o n i ti sf o u n di nt h eg o o d sy a r di n v e s t i g a t i o nt h a tt h ec o n t a i n e r - l o a d i n g p r o b l e mo c c u r r i n gi nf r e i g h tp r o d u c t i o ni so f t e nw i ms e v e r a lc o n s t r a i n t s a n do b j e c t i v e s ，i e c o m p l e x c o n t a i n e r - l o a d i n gp r o b l e m t h er o b u s t n e s s ， p a r a l l e l i s m ，a n dav a r i e t yo fa p p l i c a t i o n si nt h es o l u t i o no fn p c o m p l e t e p r o b l e mo fg e n e t i ca l g o r i t h md e m o n s t r a t eg e n e t i ca l g o r i t h mi sa ne f f e c t i v e a p p r o a c ht o s o l v ec o m p l e xc o n t a i n e r - l o a d i n gp r o b l e m i nt h i st h e s i s ，t h e g e n e t i ca l g o r i t h mf o rc o m p l e xc o n t a i n e r l o a d i n gp r o b l e mi ss t u d i e d ，a n d t h ee f f e c t i v ec o d i n ga n d d e c o d i n gm e t h o d i sg i v e n t h en u m e r i c a ls o l u t i o n o fe x a m p l es h o w st h a tt h ea l g o r i t h mi se f f e c t i v e f i n a l l y , c o n c l u s i o n s o ft h ew h o l ed i s s e r t a t i o na r ed r a w na n dt h e p e r s p e c t i v eo f r e s e a r c hd i r e c t i o n si sg i v e n k e y w o r d s ：c o n t a i n e r - l o a d i n gp r o b l e m ，p a c k i n g ，h e u r i s t i c ，g e n e t i c a l g o r i t h m 北方变盟大学士论文嘉簟靖布局问i 的求解方法研究 第1 章引言 1 1 布局问题 布局问题在我们日常生活中经常可以遇到口i ，如：货架的合理摆放，服装 面料、板材毛坯的合理切割以及一些棋盘形、方块形的数学智力游戏等。早在 十世纪，波斯国的a b u l w e f a 就构造了一个正方形分解( s q u a r ed i s s e c t i o n ) 问 题，该问题至今仍时常出现在许多文章中，h e n r ye m e s td u n e d i n 的迷宫分解问 题在本世纪初也相当著名。p i e th e i n 提出的三维布局问题，即不仅要将小布局 物体全部放入布局容器内，而且还要保持容器重心的平衡，以使小物体具有稳 定性，也许是当今最具魅力的布局问题。 近百年来，布局问题吸引了学者们的广泛注意，主要因为： 布局问题广泛地出现在金属切割、服装、玻璃、皮革、造纸、造船、交通 运输、机器人手臂运动规划、军事及航天工业中。对工业布局问题研究的动机 是明确的：只要对布局结果有少许改进，如稍微减少切割损耗，便可望收到明 显的经济效益。 由于应用领域不同，所求问题目标和约束不同，各领域必须借鉴相关领域 成功算法并加以改造，以适应本领域。 尽管人们进行了大量研究，但是由于问题的复杂性，人们一直寻找更快的 算法，更能接近全局最优解的算法。 布局问题的一般提法是这样：给定一批待布物和容器，按一定要求将这批 待布物不干涉地摆放在容器内，使某项性能最优，有时还应满足一定的约束条 件，如冲裁落料的不搭边要求，航空器的动平衡等等。布局问题按待布物形状可 分为规则形状( 通常为矩形) 布局和不规则形状布局；平面布局按切割( 落料) 方式 可分为剪切( 一刀切) 、冲裁、裁剪或切割( 线切割、火焰切割、激光切割) 等。 根据待布物的形状、容器形状及装填方式，本文将布局问题划分为以下八 种基本类型： 装盘问题( p a l l e tl o a d i n g ) ：将许多相同大小的小矩形排放在个大矩形板 材上，使其某性能最优，比如排放的个数最多。这是集装箱装货、载货托盘 上的货物摆放所面对的问题。 一刀切问题( g u i l l o t i n ec u t t i n g ) ：将某些种不同大小的小矩形按照一刀切 北方交趣犬掣嘎j 曲文 嘉蕈辅布再问l 的求麓 方游研，b 的原则排放在一个大矩形板材上，使面积浪费最少，这是剪床落料、玻璃切割、 纸张切割中遇到的主要问题。所谓一刀切，是指切割总是从矩形板材的边开 始直切到其对边，即每切一刀都将一个矩形分割成两个小矩形。这类问题往往 根据每种小矩形的个数是否限定分为无约束一刀切问题( 每种小矩形的个数无限) 和约束一刀切问题( 每种小矩形的个数是给定的) 。 、二维矩形件布局问题( r e c t a n g l ep a c k i n 曲：将许多不同大小的矩形件排 放在一张或几张大的矩形板材上，使板材的利用率最高。 、冲裁件布局问题( m e t a ls t a m p i n g ) ：将一种形状( 一般为复杂的不规则形 状) 的工件，按某种摆放方式等距连续地排放在一较长的带状板材上，使材料利 用率最高。这类问题是冲压落料中遇到的主要问题。根据冲头数目，该问题可 分为单排、双排及多排排样。 、二维不规则图形布局问题i ：将许多任意形状、大小的图形排放在一 张或几张大的矩形板材上，使某种性能最优，一般为板材的利用率最高，这是 许多行业中经常遇到的问题，如服装裁剪的放样、机械行业中的板材切割下料 等。 、不规则图形布局问题i i ：将许多任意形状、大小的图形排放在张任 意形状的不规则板材上，使板材的利用率最高，有时板材上还带有不可利用的 疵点，如皮革制品行业中的皮革落料问题。 、三维布局i ：一- - - 维箱体布局，即将许多不同大小的待布局箱体放入长方 体容器中以使某一性能最优。如集装箱内具有长方体包装的货物的装载。 、三维布局i i ：不规则三维实体的最优布局，即将许多任意形状、大小和性 能的三维实体摆放在一个任意形状、大小的三维容器中以满足某些约束或使某 一目标最优。如火箭仪器舱内的仪器布置等。 布局问题在文献上始见于1 9 3 0 年l v k a n t o r o v i c h 的俄文文章( 1 9 6 0 年译 为英语刊登在m a n a g e m e n ts c i e n c e 上) 。 有关布局的综述性文章，请见文 2 】 3 】f 4 】 5 】 6 】。 d o w s l a n dka 和d o w s l a n dw b 啪的论文“p a c k i n gp r o b l e m s ”是一篇用运 筹学方法求解二、三维布局问题的较为全面的综述性文章。除了布局问题建模 及其求解之外，作者还回顾了布局问题的算法及启发式解法。文章比较侧重一 些具体问题的实际解法。s w e e n e y 和p a t e m o s t e r t 3 1 对切割和布局( s t o c kc u t t i n ga n d p a c k i n g ) 问题也做了综述，论文中包含有4 0 0 多篇分好类的、面向应用的参考 文献，其中包括书籍、学位论文和工作论文等。d u c b o f f i 一】综合考虑各种切割和 布局问题，提出了一种一致性的、系统的方法，由此来实现在运筹学中的各种 有关切割和布局问题的概念的统一。通过这样做，作者试图为每种相关的问题 找到一种恰当的求解方法；反过来，可以确定用某种方法求解的问题类型。二 2 北方j 灌大增霸精文j l 簟麓薯r 月 问l 的爿镰力培研究 维和三维布局问题及其实用的求解方法的综述也可以从d o w s l a n dwb 的另一 篇文章中看到吲。在这篇综述文章中，大部分的应用是基于二维布局技术的， 许多三维布局问题通过的一层一层上应用二维技术来处理。从该文可以看出： 由于三维布局问题的复杂性，在布局问题的研究中，关于三维布局的研究是有 限的，只有少许与集装箱装载问题有关的论述。该文还总结了底盘装载问题 ( p a l l e tl o a d i n gp r o b l e m ，p l p ) 中需考虑的一些实际问题，如所装载货物垛的稳 定性、堆垛中货物本身的承重性、码垛货物的难易程度及某些货物对空气流通 的要求等。 文 6 】包含较全较新的二维布局的综述，文章对截止到1 9 9 8 年的文章做了 分析，较【2 】【3 】【4 】【5 】收集了较多的智能型启发式算法，如模拟退火，遗传算法 等。文 2 3 对二维不规则物体布局问题进行了详细综述，并对今后研究提出一 些看法和建议。 由于以上人的杰出贡献，对布局问题总体概述本文不再介绍，从 2 - 6 d p 可以看出人们对两类问题较少涉及，而三维规则物体布局又是不规则三维 实体布局的基础，三维不规则物体布局一般转化为规则物体布局【2 2 】，如求最小 包络立方体【7 1 ，故本文研究重点为类问题中的集装箱装载布局问题。下面对 集装箱装载问题做一综述( 对于应用于二维规则物体布局的方法，理论上可以 应用到三维布局，而文章未做详细论述的，本文综述不包括) 。 集装箱装载问题广泛地出现在铁路货车车厢装载，汽车车厢装载，轮船配 载，集装箱装载等情况。 问题的提法是：将一批待布箱体( 长方体) 装入长方体容器中，目标是使 得容器空间利用率最高，同时要考虑到的约束有：( 1 ) 箱体本身的承重性( 易 碎性) ：( 2 ) 箱体搬运的难易性；( 3 ) 一些货物必须隔离；( 4 ) 箱体运输到达的 不同地点；( 5 ) 重心与几何形心偏差不应太大；( 6 ) 货物码放的稳定性等等。 按最终目标分为三类： 对已有货物，减少容器的装箱长度； 对已有货物，减少容器所需个数： 对已有的容器，装尽可能多的货物。 以码头集装箱装载为例，海洋和陆地运输中越来越多采用2 0 或4 0 英口尺的 集装箱，装箱是一个复杂的问题，涉及到货物形状、重量、尺寸、材质，一般 来讲都会有空间浪费，尽管待装货物体积小于集装箱体积，但一般很难将这些 待装货物都放入箱中。 3 北方交琏大掌硬哇呻e 丈薯埔爿r 一向的爿u 矗懈习| ，0 作者在某海洋运输代理部门了解到，集装箱装箱分为两阶段，第一阶段， 代理积累货物，并计算到达某地的货物体积，当体积达到一定数量时，停止接 定单，代理整理出一份待装货物清单( 包括尺寸、重量、体积、特殊说明等) 。 第二阶段，码头工人将清单上货物装入集装箱。若有空隙，则填充上某些 隔离材料，或用金属丝固定，码头常常因为以下原因遇到困难： 货物清单上货物尺寸不准； 货物清单上某种货物数量不准或又有额外的货物需要装入。 许多情况，码头经常装上，卸下，再装上，几遍下来，也会有该装的没有 装入，装载结果不尽人意。 再如铁路货运部门，将集装箱租给货主后，货主想尽可能地多装货物，常常经 过多次装卸才满意，耗费大量人力物力。作者在铁路某货运部门了解到，铁路上 篷车装货利用率一般在6 0 7 0 若能提高1 0 ，每年利润可观。 这就要求计算机辅助制定可行的装载计划，虚拟出装箱过程，避免手工重 装，为码头装卸提供决策支持。 据s w e e n e y 截止到1 9 9 2 年所作统计【3 】，三维布局两类共有38 篇文章。 1 9 9 2 年至今没有详细统计。 这3 8 篇文章按照启发式算法分类如下： 1 顺序分配法( s e q u e n t i a la s s i g n m e n th e u r i s t i c s ) 。通过一些分配原则( 如 适合优先) 将布局物体逐个放入布局容器内。大多数启发式方法包括确定待布 局物体的放入顺序( 定序) 和摆放位( 定位) 两个步骤，共2 2 篇【3 】。 2 单模式生成法( s i n g l e p a t t e r ng e n e r a t i n g ) 。先将布局物体单个或成组放 入一些相同的模板( p a t t e r n ) 中，形成若干新的、具有统一形状与大小的“布 局物体”，然后对这些新物体进行布局。通常这种模板都是具有某些特殊性质的 规则物体，如正方形、正六边形、正六面体等。例如，在三维矩形布局问题中， 可以通过构造小的包含立方体来求解大立方体的布局问题【 】，共1 8 篇。 3 多模式生成法( m u l t i - p a 自t e mg e n e r a t i n g ) 。先将布局容器划分为多种模 式的组含，由此，每个模式形成一个小的布局容器，然后将布局物体装入各个 模式中。共l l 篇吼 2 、3 两种方法主要是解决不规则三维布局问题的，即两步法求解，般是 将不规则三维物体求最佳包络，包络成规则的三维规则立方体f 1 1 ，然后采用三 维规则物体的布局方法，再通过压缩算法求解。 对于集装箱装载问题，主要是应用顺序分配法。 r o b e r t sa n dt a y l o r t 8 1 描述了在火车厢中放置金属搁物架的算法，由于搁物架 底部尺寸有限，并且必须放置安全，这就减轻的问题的复杂性，由三维布局变 为二维布局，算法第一步在高度方向求最小，第二步在宽和长度方向求最大利用 4 北方，：鱼大掣埙t 地文 嫩辅爿r - 问由求i 力法研兜 率。 h a e s s l e r l 9 1 描述了一个类似于r 和t 的算法，将许多一轴一轴的纸装到列 车中，这比r 和t ( 8 1 的算法更简化，变成在一个矩形内寻找放入最多的圆的方 法。j o h na 和g e o r g e 【2 4 j 等采用遗传算法、整数规划，在考虑稳性的前提下求解 这一简化问题，并作以比较。 c h e n 和l i u 【l o 】采用单纯定序的启发式算法求解电路板元器件布置，该算法 从结果上看并不理想。 m a n n c h e n o - l 设计树搜索算法，理论上对三维箱体布局有效，但由于三维箱 体布局属n p 完全问题，随着布局箱体增多，解空间爆增，计算效率较低。 u d y t ”坪0 用序列二次规划( p q p ) 和广义简约梯度法( g r g ) 来解小型三维布局 问题，但其解的质量过分依赖于初始位置的选择。 吴惠中【l ”提出了一个长方体布局问题的立体正交结构图( s o l i do r t h o g o n a l s t r u t u r a lg r a p h ，s o s g ) 模型。该文首先提出了a i 中的同态变换求解思想，即 经过离散化的同态变换方法将一个原始布局问题转化为一个非严格数学意义的 同态布局模型，然后利用图生成算法定义的相应的布局模型，进而进行具体的 布局求解。算法从一个含有零个结点的s o s g 出发，以满足布局约束为要求， 逐步确定待布局的布局物体的空间位置关系。并通过树搜索方法、特定领域的 启发式原则和各种如截枝、限制后继结点等控制策略建立相应的估价函数，生 成完全的s o s g 模型，进而对生成的s o s g 模型进行具体的布局求解。该方法 成功地解决了诸如微型计算机结构布局的长方体空间布局问题，并可推广到有 关应用领域。但该方法存在两个缺陷：( 1 ) 当长方体增加到一定数目时，解空间 的爆炸问题不可避免；( 2 ) 这种纯图论的方法只限制在小规模的规则物体的布局 设计，还不能有效地建立一种能表达空间与空间位置关系的计算机模型，所以在 解决实际问题中没有得到广泛的应用。 杨传民，陈少为等口5 1 【2 6 1 通过全面枚举搜索方法研究相同大小的立方体的装 箱优化。 潘云鹤等1 2 7 】采用启发式搜索方法，求解集装箱装船的调度问题，主要考虑 捣箱、稳性，未涉及空间利用率，与本文讨论问题不同，但其处理捣箱，稳性 方法，对本文有借鉴作用。 文”4 】l ”1 是该问题求解的比较经典的文章，以后的算法大部分或者沿用这两 种思路，或是对这两种方法的补充，本文详细介绍【1 4 】【1 5 。 g e o r g ea n dr o b i n s o n 的方法【j4 】按阶段填充，在深度方向按层布局，尽量使 某一层的外表面平整，待布物分为两类：o p e n ，u n o p e n ，若该物体己被使用，则 为o p e n ，若未使用，则为u n o p e n 。o p e n 类型在下一层开始时优先，每一层的 第一个盒子是关键，因为它决定这一层布局的深度，并决定这层的相同数目 5 北方空丑夫增域j 螗支 乞麓布问【的j 嶙力哼研竞 的盒子的数目，其它盒子逐一布这一层的剩余空间。 算法开始，找出第一个待布盒子，有三种选择规则： 找出盒子长宽高最小尺寸中的最大值： 找出盒子数最大的； 找出盒子长宽高最大尺寸中的最大值。 在布剩余空间时，若有多个o p e n ，则布局顺序： 选盒子数最多； 按前面找第一个盒子的定序顺序找出级别最高( 此标准好一点) 。 g 和r 的算法中，有个k 参数限制该层的深度，对于k 没有讨论，但实 验表明k 对布局效率影响很大。 b i s c h o f f a n d d o w s l a n d 方法【”1 是一层层的开始布局，但有两点不同。 每一层仅由单一类型箱体开始布局； 每一层的布局通过二维平面布局( 该算法即底盘装载布局p a l l e tl o a d i n g ) 方法求解。 该算法的思想是最大利用每一层。关键是决定每一层的深度，长宽高轮流检 验是否合适，若深度确定每一截面的盒子数目也就确定了。设容器尺寸：l 、 w 、h ，盒子尺寸：l 、w 、h ，若w 做深度，则计算出i h 的矩形在w h 中能 布的数目，若盒子总数小于该数目，则该选择不好，不采用。若有几种情况能 布入的盒子数多于该数目，就要有取舍判断标准： 取截面利用率最大； 在一层中尽可能布入较多的盒子这样就可以减少剩余盒子数目。 当再不能形成完全整层后，采用ga n dr t l 4 1 算法。 eb i s c h o f f 【1 6 】比较 1 4 与 1 5 ，将【1 4 方法中的选择标准与 1 5 】中的判断标 准交叉组合，组成1 4 种启发式算法，并对这1 4 种算法性能进行比较，经过大 量试验，给出结论，对于盒子种类小于5 种的采用b 和d 【”1 的方法，而对于大 于1 0 种类型的，采用g 和r 【“i 的算法，并提议依此设计复合启发式算法，针对 箱子类型的数目，采用不同算法。 文 1 7 分析认为文 1 4 用于多种箱体布局比较合适，但实际应用中大量存在 单一箱体的布局，为此提出一种类似于货盘布局的启发式算法。 在工业应用方面，1 9 9 4 8 月g e n s y mt e c h n i c a lb u l l e t i n # 3 刊登：g e n s y m 公 司将g i i 软件用于集装箱空间规划( s p a c ep l a n n i n g ) 。即货物布局问题上，国内 未发现有这方面的应用。但铁道部曾在铁道部科技司立项指南中建议开展这方 面研究，我们也正在申请这一项目，这说明国内国外，集装箱的空间规划处于刚 刚开始研究阶段。 6 j e 方交通犬掣嚏t 船支 1 3 课题提出 以上这些三维布局方法都由一系列从常识导出来的启发式规则组成，由于 各启发式方法适用于不同领域，很难说孰优孰劣。本文设计一种基于空间分解 的不同尺寸的集装箱布局方法，显示出较好的求解效果，丰富了集装箱布局求 解方法。 许多实际约束，如装载稳定性、重心平衡使得集装箱布局问题更加复杂( 本 文定义这种问题为复杂集装箱装载问题) 。通常需将这些约束考虑到启发式规则 中。而不能只考虑空间利用率，待布局完成后再检查约束，这种复杂的布局很 难凭经验检查出是否满足约束。因此，对于某一特定的应用背景，最重要的是 选择一种方法满足实际约束，当然这需要牺牲一些空间利用率。因此，开发实 用的综合各种约束的集装箱布局算法有待于进一步研究。本文在采用遗传算法 处理复杂集装箱装载问题方面作了一些尝试。 本文属布局方面应用基础研究，受国家自然科学基金资助，课题名称：基于人 机智能的复杂布局自动化理论、方法与实现，编号6 9 9 7 4 0 0 2 。 全文分4 章，各章内容如下： 在绪论中，概述了布局问题的研究现状，并详细叙述了三维规则物体布局 的研究现状。指出该问题研究的意义，提出采用基于空间分解的启发式方法和 遗传算法求解这一问题。第二章介绍了空间分解算法的思想，求解过程，并给 出算例，丰富了三维规则物体求解方法。采用此方法分析了空间利用率与待布 物类型数，及待布物体积总和三者之间的定量关系，给出一变化趋势曲面结合 该曲面，探讨了如何提高空间利用率。第三章采用遗传算法求解多约束，多目 标的集装箱布局，介绍了该方法的原理、遗传算子设计、改进措施，并给出了 一个较优的数值结果。第四章对全文总结并提出以后研究方向的展望。 7 北方变趣大掣日曩j 螗文 第2 章应用空间分解的启发式算法求解集装箱装载 问题 集装箱布局问题是复杂的几何组合最优化问题( g c o m c 仃i cc o m b i n a t o r i a l o p t i m i z a t i o n ) ，并且在几何组合最优化问题原有复杂性的基础上又增加了布局物 体和布局空间的形状复杂性。组合最优化问题在数学上属n p 完全问题即在有 限时间内找不到问题最优解，因此目前绝大部分算法都是启发式算法。而且对n p 完全问题的研究也可看出f j 8 j ，在串行机上解决这类问题只能依赖启发式算法。 2 1 启发式算法 在最近的二十多年中，启发式方法已经成为一个重要的科研领域。其引入 之处在于它能够迅速得到复杂最优化问题的近似最优解，同优化领域的纯数学 方法相比更具有艺术性和创造性，因此吸引了众多的科技工作者。启发式方法 的起源要追溯到s i m o n t ”】的有限合理性原：l 珲_ ( b o u n d e dr a t i o n a l i t y 、。 s i m o n 从心理学出发，分析并研究了人类活动的特点，注意到尽管人自身 的能力和知识有限，但却能自如地解决那些看来难以胜任的问题，并作出正确 的决策和反应。秘密在于：人通常不是采用系统的、精确的方法去追求问题的 最佳解，而是通过逐步尝试的方法，达到有限合理的目标，即取得足够满意的 解。这就是有限合理性原理，即所谓的启发式( h e u r i s t i c ) 问题求解方法。人类就 是采用这种方法，克服了计算复杂度高的困难，使原来是n p 完全复杂度的问 题迎刃而解。 p e a r l i t 9 1 在其关于启发式方法的专著中对启发式方法进行了详细的论述，并 给出了启发式算法的定义。所谓启发式算法是指一组指导算法搜索方向的、建 议性质的规则集，按照这个规则集，计算机通常可在解空间中寻找到一个较好 的解，但并不能保证每次都能找到较好的解，更不能保证找到最优解。换句话 说，所谓启发式算法就是那些从大量的实验数据来看，算法的实际计算性能较 好，但理论上证明这些算法的最坏解题性能并不好，或者理论上并不能证明这 些算法具有优良的解题性能。由于启发式算法的设计不依赖于纯数学中优化理 论的突破和发展，因此其研究和应用在近二十年来获得了突飞猛进的发展。 8 北方交迥大掣嘲t 螗，： 鲁q 鼻麓布再问的求 方法研兜 z a n a k i se ta l t 2 0 ls i n c l a i r l 2 1 】通过对1 9 7 3 年到1 9 9 3 年发表的关于启发式算法 及其应用文章的研究，将启发式算法分为如下1 2 类： 1 构造法( c o n s t r u c t i o n ) ：次加入一个组元( 结点、弧或变量) 直到产生可行 解。大多数的贪婪( g r e e d y ) 算法都属于构造式启发算法。其应用成功的范例是t s p 问题和整数背包问题。 2 改进法( i m p r o v e m e n t ) ：从一初始可行解开始，通过局部搜索，每次用一 个或几个局部结点代替原来的结点以改进初始解的质量，直到得到局部最优解。 所有基于局部搜索的算法都属于这类算法。 3 数学规划法( m a t h e m a t i c a lp r o g r a m m i n g ) ：利用某一优化问题的数学模 型，通过修改该模型的精确求解过程得到有效的启发式算法。 4 分解法( d e c o m p o s i t i o n ) ：将原问题分解为一系列相关的易于求解的小问 题，一个小问题的输出是下一个小问题的输入，最后通过递归合并得到原问题 的解。 5 划分法( p a r t i t i o n i n g ) ：将原问题分解为不相关的子问题，每个子问题独立 求解，最后通过合并得到原问题的解。 6 解空间约束法( s o l u t i o ns p a c er e s t r i c t i o n ) ：通过限制解空间的大小使问题 变得易于求解。 7 松驰法( r e l a x a t i o n ) ：通过放松约束增大解空间而使问题变得易于求解。 8 模拟退火法( s i m u l a t e da n n e a l i n g ) ：是模拟物理学上的退火过程而得到的 启发式方法。通过逐步降低温度以达到最小能量状态，得到的最小能量状态对 应于优化问题的局部最优解。 9 禁忌搜索法( t a b us e a r c h ) ：其思想直接借鉴于人工智能，用于指导其他 方法如改进法的搜索方向，避免重复，并能从局部最优点跳出进而得到全局最 优解。该方法需要记忆搜索过程及得到的较好可行解，用这些信息来决定下一 步的搜索是继续还是从以前的可行解开始重新搜索，常常能得到较好的解。 1 0 遗传算法( g e n e t i ca l g o r i t h m ) ：该方法基于适者生存的生物进化论思 想，保留上一个解的精华并在此基础上产生下一个解，如此反复进行直到找到 最优解。 1 1 特大洪水算法( g r e a td e l u g ea l g o r i t h m ) ：不断提高水位，在始终未湿的 地方搜索，最终能找到问题的局部最优解。此方法同模拟退火方法有相似之处。 1 2 记录更替法( r e c o r d - t o r e c o r dt r a v e l ) ：同特大洪水算法极其相似，此 时将水位同到目前为止得到的最优解联系起来，当水位继续升高时，若得到的 解不如记录下的解好便不接受，否则修改最优解的记录。 从以上的分类可以发现，启发式方法的特点是把知识同搜索相结合，用搜 索来弥补知识的不足。对已有知识如何组织以及采用什么样搜索方法是上述划 9 j 匕方j 潍大茸u 曩j ：论文j 漕爿r 问【9 爿u 方法研竞 分的重要依据。 上述的1 2 种方法是启发式方法的基础，每一个具体的启发式算法都可看作 是其中的某一方法或几种基本方法的有机组合。前八种方法是较传统的启发式 方法，后四种是八十年代后期发展起来的，并逐步得到重视。s i n e l a i f 2 ”称后四 种为超越算法( m e t aa l g o r i t h m ) ，因为其中的任何一种都可加在前八种中的某一 方法之上，指导该方法的搜索以得到比原来的单一方法更好的解。 启发式方法大多基于特定的应用领域，不同的方法在不同的应用领域所收 到的效果是不同的，很难找到一个通用的样题来测试和评价不同方法的优劣。 另外，启发式方法的问题求解过程是一个求解时间和解的质量的协调过程。要 想尽快得到问题的近似解，就必须减少搜索量，这必然导致解的质量较差：若 想得到高质量的解，必须增大搜索量，但要付出大量的时间。因此很难说哪种 方法最优，只能在具体应用时根据问题的实际情况选择合适的方法或方法组合。 2 2 基于空间分解的启发式算法的思路 s w e e n y 3 】通过对1 9 4 0 年到1 9 9 0 年5 0 年间发表的4 0 0 多篇关于布局文章的 归纳发现，现有的启发式布局算法可分为如下三类： 顺序分配法( s e q u e n t i a la s s i g n m e n th e u r i s t i c s ) ：遵循一定的分配原则( 如 适者优先) 将布局物体逐个放入布局空间。 单模式生成法( s i n g l ep a t t e mg e n e r a t i o n ) ：将布局物体放入形状和大小完 全相同的模板中，最后通过合理摆放这些模板而得到问题的解。模板的形状大 多为相互间可以任意拼凑的正方形、正六边形、正十二边形和正六面体等。 多模式生成法( m u l t i p l ep a t t e r ng e n e r a t i o n ) ：将原始布局空间划分成多种 模块的组合，然后将布局物体布入各模块中。 如果按上一节优化领域启发式方法的分类规则进行分类，顺序分配法属于 单纯的构造式启发算法，而单模式生成法和多模式生成法则是构造法和划分法 的组合。可见，尽管优化领域中常用的启发式方法有1 2 种之多，但对于某一特 定的应用背景，使用较多的往往只是其中的几种。 尽管s w e e n y 将布局启发式方法分为三种类型，但从本质上来说这三种类 型的布局方法都是以构造法为基础的。之所以表现为三种类型是因为根据布局 的具体情况对布局空间作了不同的处理，因此可以将单模式生成法和多模式生 成法作为顺序分配法的变种。d o w s l a n de ta 1 ”】贝u 认为所有的顺序分配算法都是 由两大类规则组成的。第一类为定序规l j ( o r d e r i n gr u l e ) ，用来确定布局物体布 入的先后顺序；第二类为定位规, 1 ( p l a c e m e n tr u l e ) ，用来确定布局物体在布局 空间中的具体位置。从以上的分析可以看出：分析某一具体的启发式布局算法 1 0 珊骨竞追大掣闼l - 艟支j u 鼻箱布月问的爿嶙方法研，b 要从该算法对布局空间的处理以及采用什么样的定序和定位规则入手。 尽管现有的绝大部分研究都集中在规则物体的布局上，但很少有人对布局 过程中布局空间的状态变化这一问题进行深入的研究，研究的重点大多集中在 搜索策略上。然而，布局空间是布局策略的“用武之地”，必将对布局策略的效 果产生重要的影响，因此作者将对三维物体布局过程中布局空间状态的有效表 达进行深入的探讨。 三类布局启发式算法中，单模式生成法和多模式生成法在布局开始便将布 局空间进行了分割和划分，这仅仅是为了方便各模块最后的拼合。暂且不考虑 模块拼合后造成的布局空间的损失( 如六边形模块的拼合) ，仅就模块的划分来 说，因为布局物体的尺寸是随机的，各模块尺寸的确定无迹可循，几乎每一个 小的布局空间中都将有一定的剩余空间被浪费掉，这势必造成总布局空间的大 量浪费，因此这种布局空间预先划分的方法不适合三维箱体的布局，大多用于 不规则物体布局问题的近似求解。 大部分布局启发式方法都是顺序分配式的。一般是按定序规则确定的顺序 将布局物体逐一放入布局空间，每个物体的位置由定位规则来确定，直到布满 整个布局空间或没有布局物体可布入时为止。这种方法重点考虑布局物体间的 拼合，仅将布局空间作为一个约束条件，只要得到的布局方案不超出布局空间 便是可行的。然而，每布入一个布局物体，布局空间的状态就要发生一定的变 化，这些变化必将对剩余布局物体的布入产生一定的影响，因此对布局过程中 布局空间的变化及其对布入过程的影响进行研究是必要的。 仔细分析发现：尽管原始布局空间是立方体形区域，但在布局过程中剩余 布局空间却是不规则的。在简单多面体的布局空间中确定某一布局物体的最优 位置很难，所以现有的大部分布局启发式算法都采取尽量避免对布局空间的直 接处理，而是采取将其作为一个布局约束条件的间接方法处理。 综上所述，现有布局启发式算法一般采取布局空间的预先分割或“避实就 虚”的方法来处理布局空间。王爱虎博士【2 8 1 提出空间分解算法，成功的解决了 二维规则物体布局，并指出这一方法可用于三维规则物体求解。作者基于王的 算法，将空间分解算法引入三维布局中，并利用三叉树结构表示这一处理过程。 布局空间分解过程采用三叉树数据结构表示。先对原始布局空间求解，此 时原始布局空间为当前布局空间，对应于三叉树的根结点。按定序规则从可选 布局物体中选择一个相对于当前布局空间为最优的布局物体，按定位规则将其 定位于当前布局空间后部的左下角，如图2 1 位置。这样原布局空间的剩余空 间可分为三个子空间，如图2 1 所示l 、m 、r 三个空间，分别对应于三叉树根 结点的左、中、右三个子结点剩余的布局空间就变成三个独立的布局空间， 按深度优先的原则分别对这三个布局空间重复上述分解过程，直至没有待布局 j 匕方交趣大掌习i 啦丈j 啦j 爿喁问l 的哺方法研，b 物体满足要求时停止。 可见，该方法是上述布局空间的 预先分割和“避实就虚”法的折衷。 通过布局空间的动态分割，将已变成 多面体的布局空间分解为规则的、便 于处理的布局空间。从某种意义上 讲，该方法是单模式生成布局启发式 算法的发展。它同样是单模式的，只 不过所用模式不是相互间可以紧密拼 凑的正方