（机械设计及理论专业论文）切割与布局问题的算法分类研究.pdf

中文摘要 中文摘要 摘要：布局问题是一种经典的组合优化问题，具有建模和求解上的双重复杂 性。自从该问题问世以来，就被应用到许多工程领域，吸引了来自工程、数学、 计算机等领域的学者对其进行研究，并取得了大量成果。由于布局问题在求解上 具有n p 完全性，且布局问题本身种类繁多，因此出现了大量算法对其进行研究和 求解。 1 9 9 0 年d y c k h o f f 发表的布局问题分类法论文和2 0 0 7 年g e r h a r dw a s c h e r 等人 发表的改进的布局问题分类法论文都对布局问题的分类进行了归类和编码。他们 都对纷繁复杂的c & p 问题进行了系统的组织和归类，并各自得到了一套关于布局 问题分类的编码系统。这两套编码简单易懂，解决了c & p 问题之间可参考性不足 的问题，其影响力相当大。 本文以近年出现的关于布局问题的文献为基础，研究这些文献所应用的算法、 证明手段、达到的效果，把各种算法进行归类和总结，编制了针对布局问题求解 算法的两类代码系统；同时，通过对典型文献所使用的算法进行研究和归类，给 出求解方法的发展趋势和各种算法适合求解的问题类型。这样，我们在面对新问 题的时候，就可以根据这套系统对算法进行合理选择或指导新算法的系统产生， 克服手工设计新算法的缺点。 本文首先，对求解布局问题的文献结构进行研究，找到各类求解文献的共同 点，提出算法分类系统的总体结构。其次，提出分类系统的各分类标准并对各分 类标准进行细化，按照分位原则对代码进行编写建立起第一类编码系统。再次， 根据研究深度的不同，将算法分类系统进行分级建立起第二类编码系统并给出编 码的文字表达形式；通过对典型算法分类实例的代码编写验证了该套编码系统的 有效性和实用性。然后，对所编代码进行网上建立及运行，以方便研究者进行查 询、研究和分析。最后，对全文进行了总结，同时展望了后续的研究方向。 本文的工作为总结布局问题求解算法的体系以及理清不同算法之间纷繁复杂 的关系提供了方法和工具。另外本文在分类研究的基础上，也将统计各类算法的 使用频率以及它们与c & p 问题的对应关系，从而掌握算法设计的总体趋势和原则， 用于指导算法设计。 关键词：切割与布局问题：算法分类；求解分类 分类号：t p 3 1 2 a b s t r a c t a bs t r a c t a b s t r a c t ：p a c k i n gp r o b l e mi sac l a s s i cc o m b i n a t o r i a lo p t i m i s t i cp r o b l e m ，a n di s c l a i m e dt oh a v ed o u b l e h a r d n e s sb o t hi nm o d e l i n ga n ds o l v i n g s i n c et h eo r i g i n a t i o no f t h i sp r o b l e m ，i th a sb e e na p p l i e dt om a n ye n g i n e e r i n gf i e l d s ，a n da t t r a c t e dm a n y r e s e a r c h e r sf r o me n g i n e e r i n g ，m a t h m a t i c sa n dc o m p u t e rs c i e n c et od or e s e a r c h i n g w o r k e do nt h ep r o b l e m b e s i d e s ，n u m e r o u sg o o dm e t h o d sh a v eb e e np r o p o s e df o rt h e p r o b l e m b e c a u s eo fi t sn p h a r d n e sa n dt h et y p ev a r i e t y , t h e r ea r em a n ya l g o r i t h m s a p p e a r e dt os o l v ei t t h ep a c k i n gp r o b l e mt y p o l o g yp a p e rd e l i v e r e db yd y c k h o f fi n19 9 0a n dt h e i m p r o v e dp a c k i n gp r o b l e mt y p o l o g yp a p e rd e l i v e r e db yg e r h a r dw i s c h e ri n2 0 0 7w e r e b o t hc l a s s i f i e da n dc o d e dt h ep a c k i n gp r o b l e m o r g a n i z e da n dc l a s s i f i e ds y s t e m l yt h e n u m e r o u sa n dc o m p l i c a t e dp a c k i n gp r o b l e mt oo b t a i nas e to fc l a s s i f i e dc o d i n gs y s t e m b o t ht h e s ec o d e sa r es i m p l ea n dc l e a rw h i c hs o l v e dt h el a c ko fr e f e r e n c e sa b i l i t ya m o n g d i f f e r e n tc & p p r o b l e m sa n dt h e i ri n f l u e n c e sa r ef a i r l yl a r g e b a s e do nt h el a t e l yd e l i v e r e dp a p e r so nc u t t i n ga n dp a c k i n gp r o b l e m s ，t h i sp a p e r r e s e a r c h e so nt h ea l g o r i t h m s ，p r o o fa p p r o a c h e s ，a c h i e v e dr e s u l t se t c ，t h e nc l a s s i f i e sa n d s u m m a r i z e sd i f f e r e n tk i n d so fa l g o r i t h m sa n de s t a b l i s h e st h et y p o l o g yc o d i n gs y s t e m ；a t t h es a l t l et i m e ，t h ep r o p e r t i e sa n da d a p t a b l em e t h o d sa r es t u d i e d ，t h ed e v e l o p m e n t 骶n d a n dt h ea d a p t a b l et y p eo fb e i n gs o l v e dp r o b l e ma r ea l s oo b t a i n e d t h u s ，w h e nt h en e w p r o b l e mi sc o m i n go u t ，w ec a r ls o l v ei tb yu s i n gt h i ss y s t e mt or e c o m m e n dr e a s o n a b l e a l g o r i t h mo rt o l e a dt ot h eg e n e r a t i o no ft h en e wa l g o r i t h m sf o ro v e r c o m i n gt h e d i s a d v a n t a g e so nm a n u a ld e s i g n i n g f i r s t l y , r e s e a r c ho nt h es t r u c t u r eo fl i t e r a t u r ep a p e r sa b o u ts o l v i n gp a c k i n gp r o b l e m t of i n do u tt h ec o m m o np o i n t so fd i f f e r e n tp a p e r st h e np r o p o s e st h eg e n e r a ls t r u c t u r eo f t h et y p o l o g ys y s t e m s e c o n d l y , p r o p o s e se a c hc r i t e r i aa n dr e f i n e st h ec r i t e r i a , c o d i n gt h e c o d e sb a s e do nt h eb i tp r i n c i p l e t h i r d l y , a c c o r d i n gt ot h ed i f f e r e n tr e s e a r c hd e p t h ，t h i s p a p e rg r a d e st h et y p o l o g ys y s t e ma n de s t a b l i s h e st h es e c o n dt y p ea n dg i v e st h ew o r d e x p r e s s i o n ；m a k ec o d e sf o rt h et y p i c a la l g o r i t h mt y p o l o g ye x a m p l e st oi d e n t i f yt h e v a l i d i t ya n dp r a c t i c a l i t y t h e n ，b u l i d su pan e t w o r kf o rt h ec o d e sa n dr u ni tt om a k et h e r e s e a r c h e r sf e e lc o m f o r t a b l e ；a tl a s t ，c o n c l u s i o n sa r ed r a w na n dt h ef u t u r er e s e a r c h d i r e c t i o n sa r es u g g e s t e d i nt h i sp a p e r , t h ea u t h o rs u m m a r i z e st h es y s t e mo fa l g o r i t h m sf o rp a c k i n gp r o b l e m s ， v l l 北京交通大学硕士学位论文 a n ds t r a i g h t e n so u tt h ec o m p l e xr e l a t i o n s h i p sb e t w e e nd i f f e r e n ta l g o r i t h m sw h i c hb o t h t os u p p l yt h em e t h o d sa n dt o o l s a l lo fa b o v eh a sa l li m p o r t a n tv a l u e k e y w o r d s ：c u t t i n ga n dp a c k i n gp r o b l e m ；a l g o r i t h mt y p o l o g y ；s o l u t i o nt y p o l o g y c l a s s n 0 ：t p 31 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 参潞 签字日期：纠叩年彳月，乡日 翮躲形事 签字嗍伽脚月户 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：多如参 签字日期：m 唧年莎月，? 日 致谢 本论文的工作是在我的导师陆一平副教授的悉心指导下完成的。导师不遗余 力的谆谆教诲，使我的专业理论水平和科研能力得到进一步的巩固、拓宽和提高。 陆老师严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感 谢几年来陆老师对我的关心和指导，并致以我深深的敬意和诚挚的感谢。 特别感谢陆老师在课题研究及论文创作过程中给予的大力支持和无私的指导 与帮助，论文的完成凝聚着陆老师的心血和汗水。他的博学和谦逊使我受益匪浅， 他在日常生活中对学生的关爱也使我深深感动，使我在学习、工作和生活上得到 了很好的启发。 在校学习与科研期间还得到了查建中老师、刘阶萍老师、刘伟老师等老师的 指导和帮助，在此一并表示衷心的感谢。 感谢实验室的李楠、于加晴、马国通、王志刚、黄晓鸿、张钰、刘安军、孔 令军等同学；同宿舍的陈彦飞和王曦鸣同学；以及孙长江在学习和工作中对我的 热心帮助和关心支持。在相处的日子里，他们给予了我关心和支持，同时与他们 探讨和争论，既开阔了我的视野，又给与了我的论文写作很大的启发，在此向他 们表达我的感激之情。 借此机会要感谢我的父母，是他们用勤劳朴素的双手把我培养成材，感谢他 们多年来对我的关心和爱护。他们的关心和默默无闻的支持帮助我走到了今天。 再次向所有关心、支持和帮助过我的人们表示衷心的感谢，祝福大家健康、 快乐! 作者：王璐 2 0 0 9 年6 月于红果园 绪论 1 绪论 1 1布局问题概述 布局问题( p a c k i n gp r o b l e m ) 最早可以追溯到公元1 0 世纪波斯数学家a b u l w e f a 构造的正方形分割问题。早期的布局问题是指寻求若干几何体在几何空间 内的合理摆放的离散组合最优化问题，具有n p 完全性。 现如今，布局问题一般是指给定一个布局空间和若干个待布物体，在满足某 些约束的条件下，将待布物体摆放到布局空间中，使其达到某种最优性能指标。 布局问题较常见的目标函数( 或价值函数) 有空间利用率最大、重心最低、成本 最低或所装物体最多等。常见的约束条件一般为待布物体之间不产生干涉、待布 物体与布局空间之间不产生干涉、待布物体之间的相互位置制约等。布局问题的 对偶问题称为切割问题( c u t t i n gp r o b l e m ) 。因为两者在求解问题时具有相同的特 点，研究者一般将它们合并为同一问题进行讨论，并将它们统称为c u t t i n ga n d p a c k i n g ( c & p ) 问题【2 j ，即切割与布局问题( 本文以下简称为布局问题) 。 布局问题在工程实际中有着广泛的应用，它大量出现在机械制造、航空航天、 皮革服装、交通运输、大规模集成电路( v l s i ) 的设计等许多领域。具体应用问 题有车间布局、服装下料、集装箱及内部货物摆放、加工车间工件装盘、仪器舱 内的仪器布局以及飞机、车辆的布置设计等。因此，研究布局问题具有良好的实 际意义。 1 2布局问题的复杂性 研究布局问题首先要充分认识到布局问题的复杂性。一般来说，布局问题的 复杂性表现在建模和求解两个方面【3 】： ( 1 ) 建模的复杂性 建模复杂性主要表现为以下两个方面： a 布局空间和待布物体的建模涉及怎样描述布局空间及待布物体的几何 特征和非几何特征。布局物体不仅限于是矩形、圆形、六面体等简单几何形体， 也可能是不规则形状。 b 布局过程的建模描述布局问题的约束和求解目标。这些约束和目标有 些可用数学模型描述，有些则无法用数学方法描述。另外，布局过程涉及大量人 北京交通大学硕士学位论文 类专家的认知活动。其中有些可以找出规律性，但也有些认识活动无法用模型来 表示。 ( 2 ) 求解的复杂性 布局问题是一种组合最优化问题。一些最简单的一维和二维布局问题已经被 证明是n p 完全问题，如o 1 背包问题( 0 1k n a p s a c kp r o b l e m ) 、矩形装填布局问 题。n p 完全问题的复杂性在于：在有限合理的时间内，不可能求得大规模n p 完 全问题的精确解。即，随着问题规模的不断扩大，解空间呈指数倍增加，只能求 得问题的满意解而非最优解。原因是当问题的规模达到一定程度时，会产生“组 合爆炸”，精确算法将耗尽任何已有或可预见的计算机资源。 因此，布局问题的求解具有相当的难度，其彻底解决还需要一个漫长的过程。 同时，该问题涉及的研究领域又极其广泛，所以近些年涌现了大量求解布局问题 的文献，其所应用的求解方法多种多样，达到的布局效果也千差万别。 1 3布局问题的建模 布局问题的建模是描述布局问题的一个前提。下面对建模所用的知识模型以 及复杂问题的建模方法进行归纳。 1 3 1知识模型 布局问题的建模即对问题知识模型的定义和表达，涉及多种形式的知识。一 般来讲，简单的一维和二维布局问题可以通过建立数学模型来描述。但是对于复 杂布局问题，由于是多约束多目标的组合优化问题，因此单一的数值优化模型无 法对这种类型的布局问题进行表达【4 j 。布局问题的知识模型主要包括数学模型、图 论模型、复合知识模型等。 ( 1 ) 数学模型( m a t h e m a t i c a lm o d e l ) 现有的大部分布局问题的模型，一般都是将原问题进行简化( 包括几何形体、 约束条件和目标知识) ，建立单纯的数学模型，然后用组合优化中广泛应用的线性 规划法、整数规划法、动态规划法或分枝定界法等数学方法进行问题的求解【5 j 。 v a l e r i od ec a r v a l h o 等【6 】用线性规划模型来描述两阶段下料问题，并用列生成 技术对得到的模型进行求解。 b e a s l e y 7 1 将布局问题抽象为o 1 整数规划模型进行求解。 u d y 等【8 】利用序列二次规划和广义简约梯度法来解决小型三维布局问题。 黄文奇和陈亮p j 提出一种求解布局问题的拟物方法。 2 绪论 滕弘飞等o j 以人造卫星舱的布局为背景，建立简化的规则物体布局优化模型， 利用惩罚因子将布局约束转化为目标函数惩罚项，提出了旋转锥体空间中圆柱体 群和长方体群的布局优化算法。 对布局问题进行抽象简化够建立数学模型，可以为求解提供便利。但是，当 原问题涉及一些不易用数学模型表达的约束条件或由于问题规模增大使得解空间 急剧增加时，采用各种近似的方法得到的数学模型往往会与原问题产生较大的偏 差，或者很难甚至无法得到有效解。 ( 2 ) 图论模型( g r a p h t h e o r e t i c a lm o d e l ) 以图中的结点代表待布物体，弧线代表待布物体之间的关联关系，由此将布 局问题转化为在一个在已知的连接图中寻找最大独立集或最大权平面子图的问题 称为对布局问题建立图论模型。 d o w s l a n d 等【l l j 首先建立了布局的图论模型即将矩形或立方体待布物体看 作图的结点，若两个待布物体之间相邻或相关，则各待布物体的结点之间存在一 条连接弧线；否则没有弧线连接。 随后又有学者先后提出了相邻拓扑图模型、长方体布局问题的立体正交图模 型和约束图模型等。 虽然图论方法具有广泛的应用领域和良好的求解结果，但应用于布局问题的 图论模型仍然不能充分表达布局知识及约束，所以只限于求解小规模规则物体的 布局问题。 ( 3 ) 复合知识模型 由于复杂布局问题不仅涉及可以用数学模型描述的知识，还涉及无法用数学 模型描述的知识，如布局问题的材料性能以及装卸工艺，特别是人类专家的布局 领域知识等。所以，任何单一模式的知识模型( 如数学模型，图论模型等) 都不 能精确合理的表达该问题，所以应该建立复合知识模型。 钱学森、于景元等【12 j 著名科学家提出了从定性到定量的综合集成方法论。 孙守迁等1 13 】对面向人机工程的布局问题进行研究，提出了人机工程约束模型， 即将人作为特殊的布局单元，并以人的坐标位置为参照点，建立一个新的约束表 达模型，这样充分考虑了人机工程对布局设计的影响。 王彩红1 1 4 1 提出了适用于布局设计过程不同阶段的复合知识模型。建立数学、 符号知识、仿真复合知识模型，过程模型及模型本身的转换和相互变换，实现了 复杂系统布置设计问题中定性和定量的结合。 北京交通大学硕士学位论文 1 3 2 不规则物体建模 待布物体可分为规则形物体( 如矩形、圆形、长方体) 和不规则形物体。由 于不规则形物体的形状复杂，所以，早先的布局算法在处理对象上大多只局限于 规则形物体。但是，随着人们对布局问题本身及其求解理论的深入研究，不规则 形物体的布局问题逐渐受到越来越多的重视，如： 唐飞等【1 5 l 将航天器中一种复杂插座板上插孔的布局设计问题简化为二维圆形 装填问题。 戴佐、查建中等【1 6 - 2 0 将八叉树数据结构引入到三维实体的计算机仿真布局及 智能最优布局领域，并给出了三维物体的实体造型和干涉检验的八叉树方法，为 布局问题提供了良好的解决基础。 王金敏、查建中等陟2 2 1 给出了一种新的三维实体八叉树模型的生成算法，较 好地解决了复杂物体之间距离的计算问题。 c a g a n 等 2 3 】提出了表达实体的一种改进的八叉树方法及相应的干涉检验算法。 王爱虎、查建中【2 4 彩1 提出利用二叉树结构表达矩形物体布局状态空间的方法， 并提出了解决简单多边形裁剪和交并计算的统一算法。 1 4 课题的提出 切割与布局问题( c u t t i n ga n dp a c k i n gp r o b l e m ，c & p 问题) 是一种经典的组合优 化问题，有很多的实际领域。因应用点不同，c & p 问题有不同的定义，并且条件 稍微改变，其问题的性质和求解复杂性就会有很大的变化。以往对布局问题的命 名往往采用问题来源命名，比如线材下料问题，板材下料问题，集装箱装载问题。 然而实际上任何这样的问题都附加有特殊的要求，从而造成繁多的c & p 问题种类。 现实中经常见到具有类似特征的c & p 问题之间的实际差异很大，甚至造成参考文 献之间失去参考意义。同时，由于布局问题的种类繁多，求解方法也多种多样。 1 9 9 0 年d y c k h o f f 发表了第一篇c & p 问题的分类文章。2 0 0 7 年g e r h a r dw 酗c h e r 等人发表了另一篇改进的布局问题分类法文章。目前c & p 问题研究者公认这两篇 文章是梳理繁杂c & p 问题的里程碑，几乎近年来发表的c & p 文章都会使用他们 的分类来界定自己的问题性质，以使得其他研究者知道自己的工作内容。从2 0 0 5 年以来，分类学( t y p o l o g y ) 成为c & p 研究领域的一个方向，在历次欧洲运筹学 学会下属的c & p 研究组所组织的切割与布局问题研究年会上都作为一个主题来讨 论。 与c & p 问题本身一样，其求解算法也纷繁复杂。同一个c & p 问题可以用各 4 绪论 种不同的算法去求解，从标准的数学规划方法到各种精确算法再到各种不断涌现 的启发和元启发式算法，加上各种混合算法，其混乱程度比c & p 问题本身更为严 重。现在关于求解c & p 问题的文献已经达到了几千篇，很难说哪两个文献的算法 是完全一样的。但到目前为止还没有对求解布局问题的算法提出一个分类系统， 这同样造成了不同研究之间的可参考性不足，不利于c & p 问题的进一步研究。 因此本文提出关于布局问题求解算法的分类系统研究。类比d y c k h o f f 和 g e r h a r dw a s c h e r 对布局问题的编码，建立起对应用于布局问题求解算法的分类编 码系统，为总结布局问题求解算法的体系以及理清不同算法之间纷繁复杂的关系 提供了方法和工具。另外本论文在分类研究的基础上，也将统计各类算法的使用 频率以及它们与c & p 问题的对应关系，从而掌握算法设计的总体趋势和原则，用 于指导算法设计。 1 5 本文主要工作 本文的主要工作集中在对求解布局问题的算法进行分类、编码上，具体说来 主要包括以下三个方面。 ( 1 ) 总结归纳了布局问题的求解结构和常用的求解算法； ( 2 ) 在对历史文献的研究基础上，针对不同类型的布局问题，类比问题的分 类方法，将涉及求解算法的标准分为五类：研究目的、算法新颖性、算法大类、 算法子类和衡量算法应用效果的标准。并将该五类标准进一步细化，按照分位方 式将涉及求解布局问题的算法进行编码。同时，为了适应不同的研究深度及记忆 方便，本文还将该套编码分为三个级别，并根据基本类型的编码提出文字表达的 方式，得到第二类编码。 ( 3 ) 通过对典型算法的布局文献进行编码，得到了布局问题求解算法的求解 趋势和各类问题适宜的求解算法。 ( 4 ) 利用网络数据库编程技术，在网上建立及运行所得到的结果，为广大研 究者搭建了一个用于查询及分析的网络平台。 全文各章的主要内容简述如下： 第一章为绪论。首先，对布局问题的起源、定义进行了概括。然后，就布局 问题自身的建模复杂性和求解复杂性进行了总结和归纳。第三，详细介绍了布局 问题的建模方法和良好建模的重要意义。第四，对本课题的提出进行了说明。最 后比较详细的提出本文具体的研究内容、研究目的、课题的实际应用点以及工程 与学术意义。 第二章归纳了历史上对布局问题的著名分类方法。包括最初的一般分类方法， 北京交通大学硕士学位论文 19 9 0 年d y c k h o f f 分类方法和2 0 0 7 年w 瓠c h e r - h a u s s n e r s c h u m a n n 分类方法。其中， 重点介绍了d y c k h o f f 分类方法和w 如c h e r - h a u s s n e r - s c h u m a n n 分类方法，并对两种 分类方法的优缺点、分类标准、命名规则和编码方式进行了详细的描述。本文所 述的算法分类方法就是参考这两种分类方法而提出的。 第三章对布局算法分类系统的提出进行了阐述。对其提出的意义、与求解类 型的关系进行了简要介绍。然后，对布局算法分类系统的总体结构进行描述。 第四章是本文的一个研究重点。对布局算法分类系统的结构中的各分类标准 进行了详细的介绍。包括研究目的子类、算法新颖性子类、算法大类、算法子类 和算法有效性可评测度五个方面的内容，以及每种子类标准所包括的具体内容。 第五章也是本文的一个研究重点。通过第四章对布局算法分类系统结构的研 究，提出布局算法分类的编码设计。首先对编码设计的意义和总体结构进行阐述。 其次，提出第一类编码，对编码的各位进行详细说明并给出编码示例。同时为了 研究的方便和适应不同深度的研究，本文根据信息完备性的不同，又提出了第二 类编码，并给出编码示例。 第六章通过查阅1 9 9 6 2 0 0 9 年间公开发表的典型算法的布局文献( 大部分来源 于欧洲运筹学报) ，对本文所提出的分类系统进行验证。除给出每一篇文献的具体 编码形式，统计各类算法的使用频率以及它们与c & p 问题的对应关系，还通过注 释的方式给出了推荐算法。 第七章是基于算法分类体系的算法设计支持的原型建立。将本文提出的算法 分类编码系统通过网络数据库技术进行系统建设。将网站用户的查询等级分成三 类，方便不同用户对文献或问题的算法进行查询、分析、比较和记忆，并根据统 计结果给出每一类问题的推荐算法。 第八章为总结和展望。总结了全文的研究工作，指出了成果和不足，对今后 的研究工作进行了展望。 本文的结构安排如图1 1 所示。 6 绪论 1 6 本章小结 图1 1 全文的章节结构 f i g1 一it h ea r c h i t e c t u r eo ft h et h e s i s 首先，对布局问题的起源和定义进行了概括。第二，阐述了布局问题在建模 和求解上的双重复杂性，并对布局问题建模方法的现状进行了总结和归纳。然后， 对本课题的提出、学术意义进行了说明。最后，给出了本文的主要工作和章节结 构。 7 历史上对布局问题的著名分类方法 2 历史上对布局问题的著名分类方法 2 1一般分类方法 布局问题有多种分类方法，如按照待布物体形状、布局空间的形状和布局空 间的维数等，大致情况如下。 ( 1 ) 一维布局( o n ed i m e n s i o n a lp a c k i n g ) 背包问题( k n a p s a c kp r o b l e m ) ，一维切割问题( o n e - d i m e n s i o n a lc u t t i n g s t o c k p r o b l e m ) 等。 ( 2 ) 二维布局( t w od i m e n s i o n a lp a c k i n g ) 二维矩形块布局问题( r e c t a n g l ep a c k i n g ) 、二维矩形块条带布局问题( r e c t a n g l e s t r i p p a c k i n gp r o b l e m ) 、装盘问题( p a l l e tl o a d i n gp r o b l e m ) 等。 ( 3 ) 三维布局( t h r e ed i m e n s i o n a lp a c k i n g ) 三维长方体布局( t h r e ed i m e n s i o n a lb i np a c k i n g ) ( 将长方体包装好的货物装入 集装箱内) 、三维不规则实体布局( 如车辆动力舱内部件的布置设计) 。 2 2 d y c k h o f f 分类方法 1 9 9 0 年d y c k h o 甜2 】通过归纳c & p 问题的主要性质，借助编码形式，实现了对 c & p 问题的划分。d y c k h o f f 主要从以下四个方面进行考虑。 ( 1 ) 维度方面：包括一维、二维、三维及n 维( n 3 ) 。 ( 2 ) 任务类型：将待布物体布置到布局空间中( b ) ；选择布局空间放置待布 物体( v ) 。 ( 3 ) 布局空间方面：仅有一个布局空间( o ) ；多个相同的布局空间( i ) ：多 个不同的布局空间( d ) 。 ( 4 ) 待布物体方面：数量较少的不同待布物体( f ) ；数量较多的不同待布物 体( m ) ；待布物体数量较多，但尺寸种类相对较少( r ) ；待布物形状完全相同( c ) 。 在编码时，将每类问题分成四位，每一位用相应的数字或字母表示，如装盘 问题的编码为2 b o c 。这样，应用d y c k h o f f 分类方法实现了对布局问题的归类， 同时，对该问题的研究起到了非常好的促进作用。 9 北京交通大学硕士学位论文 2 3 w a s c h e r - h a u s s n e r - s c h u m a n n 分类方法 后来人们发现，d y c k h o f f 的分类方法也存在不足，容易让人产生混淆，这主 要体现在以下三个方面： ( 1 ) 对于同个问题可能会出现两种编码方式。如机动车装载问题( v e h i c l e l o a d i n gp r o b l e m ) ，即可以被编码为1 i f 也可以被编码为1 v i m ； ( 2 ) 有些问题划分界限不清楚。如条带布局问题( s t r i n gp a c k i n g ) ，d y c k h o f f 将其编码为2 n d m ，但是大多数研究者认为该问题被编码为2 v o m 更合适。 这主要是由于研究者对布局空间尺寸固定与否的考虑不同。因此布局空间尺寸是 否固定也影响了问题的分类。 ( 3 ) 对于一些问题，应用d y c k h o f f 的分类方法，不能达到所期望的目的。如 一维切割问题( o n e d i m e n s i o n a lc u t t i n gp r o b l e m ) ，d y c k h o f f , 恪它们统一归为 1 v d r 。然而，被切割物料形状全同与形状完全不同时，所应用的研究方法完全 不同，将它们简单的归纳为同一种情况显然是不合适的。 鉴于上述问题，w a s c h e r 等【2 6 】对d y c k h o f f 的分类方法进行了改进，他们从维 度、布局方式、布局空间的多样性、待布物体的多样性以及待布物体形状五个方 面对c & p 问题进行了重新分类总结。其前面的4 个标准与d y c k h o f f 分类方法标准 所考虑的对象基本相同，但是内容有所不同。考虑到德文相对不如英文的应用广 泛，在布局方式编码中，采用字母i ( i n p u tm i n i m i z a t i o n ) 和字母o ( o u t p u t m a x i m i z a t i o n ) 代替d y c k h o f f 分类方法中的字母v ( v e r l a d e p r o b l e m ) 和b ( b e l a d e p r o b l e m ) ；对布局空间的多样性和待布物体的多样性进行了重新定义和 补充。增加第五条标准，从规则形物体( 如矩形、圆形及椭圆形等) 和不规则形 物体角度对待布物体进一步做了区分。同时，布局方式和待布物体多样性不再单 独作为划分c & p 问题的依据，而是将它们组合起来用来定义基本问题类型；布局 空间多样性将用于定义中间问题类型；待布物体形状用于定义改进问题类型。为 了使分类更准确，采用分级方式划分。对于标准的c & p 问题，以基本问题类型一 中间问题类型一改进问题类型为主线的递进分类模型。在每一分类级别上，存在 着添加与该问题一般属性有关的非标准c & p 问题，划分时将这些条件作为问题变 量而不改变其所划分的类型。这样层次划分和每个层次添加问题变量相结合，可 以动态合理的划分出各种c & p 类型。【4 】 下面对基本问题类型，中间问题类型以及改进问题类型做一下简单介绍。 基本问题类型：该类型由布局方式和待布局物体多样性两个标准构成，图2 1 给出基本问题类型结构图。 l o 历史上对布局问题的著名分类方法 待布物多 样性 羰望慝照圃圃圆圆 图2 一i 基本问题类型 f i g2 - 1b a s i cp r o b l e mt y p e s 其中待布物体全同、弱异性、强异性分别对应于d y c k h o f f 分类中待布物体多 样性的c ( 待布局物形状全同) 、r ( 待布局物体数量较多、尺寸种类相对较少) 和m ( 待布局物数量较多，尺寸种类也较多) 。为了简化描述，对c & p 问题的类 型一般采用头字母进行缩写，如i i p p ( i d e n t i c a li t e mp a c k i n gp r o b l e m ) ，p p ( p l a c e m e n t p r o b l e m ) ，o d p ( o p e nd i m e n s i o np r o b l e m ) ，c s p ( c u t t i n gs t o c kp r o b l e m ) 。同样， 对于中间问题类型和改进问题类型，它们是在基本类型的基础上发展的递进类型， 所以也是采用的这种简化描述方式进行描述。 中间问题类型：中间类型是在基本类型的基础上，通过增加考虑待布空间多 样性标准，实现了对全同问题的进一步定义。下面表2 1 、表2 2 分别给出输出最 大化和输入最小化的中间问题类型的情况。 表2 1 中间类型问题描述表：输出最大化 t a b2 - 1d e s c r i p t i o nt a b l eo fi n t e r m e d i a t ep r o b l e mt y p e s ：o u t p u tm a x i m i s a t i o n 、：淤! 全同弱异性强异性 布局空间特性、 单布局空间i i p ps l o p ps k p 所有维度 m i l o p pm i k p全同 固定 相异性m h l o p pm h k p 北京交通大学硕士学位论文 表2 2 中间类型问题描述表：输入最大化 t a b2 - 2d e s c r i p t i o nt a b l eo fi n t e r m e d i a t ep r o b l e mt y p e s ：i n p u tm i n i m i s a t i o n ：淤： 弱异性强异性 布局空间特性 全同s s s c s ps b s b p p 所有维 弱异性 m s s c s pm b s b p p 度固定 强异性 r c s pr b p p 单一布局空间维度可变 o d p 表l 中缩写说明：s ( s i n g l e ) ，l o ( l a r g eo b j e c t ) ，m i ( m u l t i p l ei d e n t i c a l ) ， m h ( m u l t i p l eh e t e r o g e n e o u s ) ；表2 中缩写说明：s s s ( s i n g l es t o c ks i z e ) ，s b s ( s i n g l eb i ns i z e ) ，m s s ( m u l t i p l es t o c ks i z e ) ，m b s ( m u l t i p l eb i ns i z e ) ，r ( r e s i d u a ) 。将上述缩写符添加到基本类型缩写符( p p ，k p ，c s p ，b p p ) 前，就 可用于描述中间类型了。 改进问题类型：改进类型只需在中间类型符前面添加维度信息和待布局物形 状信息，就可以简单而准确地用于描述改进问题类型。 2 4本章小结 本章将历史上对布局问题的分类方法进行了总结和概括。主要介绍t d y c k h o f f 分类方法和w i i s c h e r - h a u s s n e r - s c h u m a n n 分类方法的主要思想、分类标准和代码命 名规则。 布局算法分类系统的提出 布局算法分类系统的提出 3 1提出布局算法分类系统的意义 与c & p 问题本身一样，其求解算法也纷繁复杂。同一个c & p 问题可以用各 种不同的算法去求解，从标准的数学规划方法到各种精确算法再到各种不断涌现 的启发和元启发式算法，加上各种混合算法，其混乱程度比c & p 问题本身更为严 重。现在关于求解c & p 问题的文献已经达到了几千篇，很难说哪两个文献的算法 是完全一样的。由于算法直接影响布局求解的结果，系统地研究布局的算法分类 也更加具有意义。但到目前为止还没有对求解布局问题的算法提出一个分类系统， 这同样造成了不同研究之间的可参考性不足，不利于c & p 问题的进一步研究。为 此提出布局算法及其研究方法的分类系统。以下先给出布局算法的总体分类结构， 在第四章给出分类的具体设计，第五章给出分类的具体编码表达方法及典型问题 的算法分类。第六章是通过对既往算法的研究给出了一个统计结果并验证了该编 码的有效性。 3 2布局文献的一般求解步骤及其与求解类型的关系 通过阅读文献发现，一般来讲，布局文献具有相似的求解步骤，可以概括为 以下五个阶段。 ( 1 ) 待求问题的一般描述、应用领域、求解复杂度等基本性质。可以根据这 些特点将待求问题进行类型划分。本文中，以w 融c h e r 等f 2 7 1 人提出的分类方法的 中间问题类型为标准将所有待求问题划分为1 4 种类型。 ( 2 ) 阐述该问题的附加约束、已有的研究方法、研究结果和不足。建立该问 题的数学模型，并依据难易程度追加附加约束。最后提出自己的求解方法或对已 有算法进行改进以及期望达到的效果。 ( 3 ) 对求解方法的原理做详细描述。包括：求解方法的原理、所属类别、证 明过程、应用情况等，并将该方法应用于布局问题中得到针对布局问题的求解算 法和伪代码。 ( 4 ) 对该算法进行实现并用数值算例证明算法的有效性，同时给出算例收敛 的类型。有时，对新算法进行算例验证时，会与其它算法进行比较。这时，两算 法应用的计算环境应基本相同。 北京交通大学硕士学位论文 向。 ( 5 ) 对提出的新方法进行总结与展望，提出优势、不足以及该问题的求解方 本文就是按照上述五方面的顺序对布局问题的求解进行研究的。 3 3布局算法分类系统的总体结构 同布局问题的分类一样，对算法进行有效的划分，可以使研究者清醒的认识 到各类算法的优缺点、各种算法擅长求解的问题类型，并总结出各种问题的求解 趋势，给出推荐算法，更有助于进一步的科学研究。 由于布局问题自身具有的复杂性和多样性，导致求解算法多种多样，求解效 果也千差万别。而且为了便于比较以及达到更广泛的应用目的，本文的分类不仅 仅针对算法本身，还包括算法达到的求解效果。所以，本文的分类系统采用五个 标准：研究目的子类、算法新颖性子类、算法大类、算法子类和算法有效性可评 测度。同时将该分类系统进行分级划分以适应不同研究深度的需要。主要把该五 类标准分为三级：基本级、中间级和精确级。具体为：研究目的子类、算法新颖 性子类和算法大类用来定义基本问题类型，算法子类用来定义中间问题类型，算 法有效性可评测度包括衡量算法应用效果的标准和支持算例数两方面，用来定义 精确