（管理科学与工程专业论文）机载装箱方案研制与中海物流系统软件开发.pdf

课题“机载装箱方案研制与中海物流系统 软件开发”为： 国家自然科学基金资助项目( 批准号7 0 3 7 1 0 2 4 ) 山东省自然科学基金资助项目( 批准号y 2 0 0 3 h 0 1 ) 的相关子课题。 篁= 兰! ! 蔓一 摘要 过去几十年中，国内外许多学者对布局问题进行了深入研究，并提出了许多算 法。如何根据实际问题，选择合适的算法解决现实中的装箱问题，是当前研究的热 点。在国外，对该问题的理论研究成果已经运用蓟了生产、生活的各个方面，如集 装箱装载等：在国内该领域的应用相对落后。 本文以中海物流装箱系统为应用案例，根据箱子的大小和彩电的分类建立系统 模型。然后采用启发式算法、遗传算法和模拟退火算法对该问题进行求解。 另外，本文提出了“空间布局点”的概念，对布入空间的物体所造成的新的可 以放置物体的位置进行描述。 最后，本文将装箱的三种算法在计算机上实现，通过与图形显示的程序相结合， 可以直接将布局结果显示出来，对现场工人的实际操作具有直接的指导。 硕士研究生：郭宏伟( 管理科学与工程) 指导教师：胡劲松教授 关键词：布局闯题，遗传算法，启发式算法，模拟退火 青岛大学硕士学位论文 a b s t r a c t d u r i n gt h ep a s ts e v e r a ly e a r s ，m a n yr e s e a r c h e r sh a v eb e e ns t u d y m gt h el o a d i n g p r o b l e ma n dp u tf o r w a r dm a n yk i n d so f a l g o r i t h m s i ti sa c o l eq u e s t i o nh o wt of i n da e f f e c t i v em e t h o d st os o l v et h el o a d i n gp r o b l e ma c c o r d i n gt op r a c t i c a lr e q u i r e m e n t s i n d e v e l o p e dc o u n t r i e s ，t h ee f f e c t i v er e s u l t sh a v e b e e na p p l i e di nm a n y f i e l d sa b o u tl i v e sa n d p r o d u c t i o n s u c h c o n t a i n e rl o a d i n g ，b u ti n0 1 1 1 c o u n t r y , t h et e c h n o l o g yi sc o m p a r a t i v e l y l a g g e d t h i sa r t i c l et a k e st h ee x a m p l eo fz i - i o n g h a il o g i s a , ：sc o n t a i n e rl o a d i n gs y s t e m a n db u i rt h es y s t e ma c c o r c l i l l gt ot h es i z eo fb o x e so f t v t h e n , h c z a i s f i c sa l g o r i t h m g e n e t i ca l g o r i t h ma n d s i m u l a t e d a n n e a l i n ga l g o r i t h mi sa p p l i e x l t os o l v et h ep r o b l e m m o r e o v e r , t h i sa r t i c l ef o r w a r d st h ec o n c e p to f p l a c i n gc o m e r , w h i c hd e s c r i b e st h e n e w p l a c i n gs p a c ea f t e rw ep u ts o m eb o x e si n t ot h ec o n t a i n e r a tl a s t , w er e a l i z e dt h e s ea l g o f i t h m si nc o m p u t e r b yj d 土e 簪蒯吨t h ep r o g r a m so f p i c t u r ed i s p l a y i n g , t h er e s d tw a sd i s p l a y e dd i r e c t l y0 1 1t h ec o m p u t e rw h i c hi sv e r y p r a c t i c a lt ot h eo p e r a t i o nw o r k e r s p o s t g r a d u a t es t u d e n t ：h o n g w e ig u o ( m a n a g e m e n t s c i e n c e e n g i n e e r i n g ) d i r e c t e db y p r o f ：j i n s o n g h u k e yw o r d s ：l o a d i n gp r o b l e m ，g e n e t i ca l g o r i t l n n ，h e u r i s t i c sa l g o r i t h m , s i m u l a t e d a n n e a l i n ga l g o r i t h m 蔓二兰! ! 童一 1 1 研究背景与意义 第一章弓l 言 随着经济全球化趋势的加强，科学技术尤其是信息技术的飞速发展以及跨国公 司作用的日益增大，物流作为一种实现经济高效运行、融高新技术为一体的先进管 理技术与组织方式，通过计划、实施、控制与协调等手段对运输、仓储、装卸、包 装、配送、流通加工、信息各环节的系统整合，以最低的费用和最少的资金占用， 安全、准时、高质量地为用户提供多功能、一体化的综合服务，在世界范围内受到 了广泛的关注发展十分迅速。实施并加强物流管理，降低流通费用已成为当今全 球经济发展的一个熏要内容。 现代物流作为现代经济的重要组成部分，在国民经济和社会发展中发挥着重要 作用，因而受到了各国政府和企业的高度重视。我国国民经济和社会发展“十五” 规划，就将“物流配送”作为重点支持发展的服务产业。 物流与商流、信息流并称为是现代经济的三大支柱。由于物流对国民经济的重 大影响，物流系统化、合理化能创造巨大的经济利益，因此物流被誉为继劳动力、 资源之后的“第三方利润源泉”。根据1 9 9 7 年国际货币基金组织( i m f ) 的统计数 据，我国的物流成本占g d p 的比重为1 6 9 ，达7 1 8 亿美元，而英美发达国家的物 流成本占g d p 的比重约为l o ，新加坡、香港、台湾的这一比例也只有1 3 左右。 现代物流不仅要降低成本，更要满足客户的需求，因此如何在满足用户需要的 前提下，进一步降低物流成本已成为国外许多理论、应用学者们关注的焦点。我国 是在8 0 年代才接触“物流”概念的，比国外落后了二三十年，对其研究相对滞后。 随着改革开放进程的纵深发展，我国国民经济、对外贸易迅猛发展，且日益融入世 界经济体系中，物流这一新理念已被提到了我国服务业发展的战略高度，对物流的 研究因此也具有非同寻常的意义。而作为物流中装箱这一环节的研究既有理论价值， 又有实际意义。 1 2 项目背景 中海物流公司是一家对彩电等家用电器产品进行配送的大型企业。公司对海信 等公司生产出来的产品放入不同规格的集装箱车内，然后根据要求运到不同的目的 地和。由于家用电器本身的特性，存放电器的合资在集装箱内的摆放要求正面向上。 青岛大学硕士学位论文 在这个前提下，盒子要尽量紧密地放入集装箱内，以提商集装箱的利用率，降低运 输成本。同时，由于人力，物力及家电本身的要求，盒子只能一次性地装入，而不 能反复装卸。 到目前为止，将盒子装入集装箱的工作完全依靠人工调度来进行。调度员在现 场凭借经验估计被装入的几种盒子的数量及所需集装箱数，并开出装箱单据。然后， 装箱工人按照单据将盒子放入集装箱。这种操作程序存在两方面的问题：一方面， 虽然调度员经验丰富，可是，单凭直观经验估计出来的数字却很难保证集装箱的高 利用率，因而经常出现集装箱未被装满的情况；另一方面，装箱工人在装箱时没有 任何装箱方案的依据，完全是随意地或经验式的将盒子装入集装箱内。这种装载的 随意性同样造成由于盒子摆放的不合理导致的集装箱利用率的问题，甚至经常出现 装箱单上的盒子不能装入集装箱而重新改写单据的现象。中海物流公司致力于生产， 销售的科学化管理，然而，在货物运输的环节中的这种人工装箱方式无形中增加了 产品的成本，降低了企业的效益。 事实上，集装箱装载问题时货物运输的重要环节，是一类具有广泛行业背景的 问题。如何摆脱人工操作的落后局面，同时给出一个合理的布局及装载方案，以提 高集装箱的空间利用率和装箱效率，是我的主要目标。实现这些目标，将会给许多 行业带来巨大的经济效益。 为此，本文将就上述环节中存在的两个问题着力进行如下的工作：寻求一种有 效的集装箱装载算法，将几种不同规格的长方体盒子合理有效地放入集装箱，以提 高集装箱的空间利用率，并为类似问题的解决提出一种新的思路。同时，结合算法 实现集装箱装载程序。该程序以图形方式给出每个盒子在集装箱内的准确位置，以 指导工人的装箱工作，提高装箱工作的效率。 1 3 本文的主要工作、创新点与组织 1 3 i 本文的主要工作和创新点 本文提出了“布局点”的概念。并在此基础上提出了一种用遗传算法解决布局 问题的新的思路。 从解决方法的角度来看，本文将重点放在启发式算法和遗传算法的介绍上，这 是由布局问题的复杂性来决定的。本文首先介绍了解决布局问题的几种常见的解决 方法，然后，在深入地了解了企业的需求，业务流程和现状的基础上，结合一般的 布局问题模型，本文对实际问题进行了适当的抽象和简化，从而确定了该问题的基 本模型，并利用启发式算法，遗传算法和模拟退火算法分别对其进行了求解，并用 计算机实现。 1 0 第一章引言 本文最后，对装箱方案的图形显示方法进行了研究，并利用v b 和c 两种计算机 程序对布局问题的解决方法和装箱方案的显示进行了集成。 1 3 2 本文的组织 本文分为三大部分： 第一部分为前言，主要从理论和实际两方面讨论了问题提出的背景与该问题的 研究意义。 第二部分包括第- - - 章、第三章，第四章，第五章，该部分是本文研究工作的理 论基础。 第二章首先简要介绍了布局问题的一些简单概念，并在此基础上对布局问题的 一些常用的解决方法进行了概括。 第三章，第四章，第五章分别具体的介绍了一种解决布局问题的方法，并加以 实例分析。 第六章介绍了基于启发式算法及遗传算法装箱系统结构设计，以及系统的主工 作流程。 青岛大学硬士学位论文 第二章装箱问题的国内外研究方法综述 2 1 装箱的相关概念 2 1 1 装箱问题简介 装箱问题仍i np a c k = i n g p r o b l e m ) ) 是指将已知形状和大小的几何群体进行布局， 使得所有群体所占用的某一形状的外包络区域的测度( 即长度、面积或体积) 最小， 或者将这些几何体布局为若干组，要求每组的某一形状的外包络区域之测度不得大 于某一给定值，总目标为所布局的组数最少。 对于装箱问题的研究，除要求空间利用率最高外，还要求满足如下条件： 可容性：各布局块须完全含于给定布局空间区域内； 不干涉：各布局块之间不得发生空间干涉( 即不发生叠迭) ： 平衡性：放置后，所有布局块构成的系统的静不平衡量小于某一给定的容许值； 聚集性：全部布局块向给定布局空间区域中心高度聚集，即整个布局模式的外 包络区域达到最小。 此外，实际中的布局设计还往往带有其它的习惯性要求，比如，某些布局块要 安置于给定区域中的某一特定的区域内，某些布局块之间要相隔一定距离等等。 装箱问题在建筑业中的房间布局，工业中的模板布局( t c m p k i t el a y o u t ) 、新闻报 纸、广告等版面布置，集成电路布图设计及其它一些工程设计等实际中有着广泛应 用。 2 1 2 装箱问题的复杂度 在实际的装载中除要求空间利用率最高，且满足可容性、不干涉、平衡性、聚 集性等要求以外，还要满足多种装箱条件： ( 1 ) 方向的约束：在装载中，货物的摆放方向受约束，例如有些货物的包装标有 向上的箭头等。一般货物装载时的方向约束可归纳为三种约束，既任意旋转、水平 旋转、不能旋转。 ( 2 ) 承载能力的约束：在装载过程中，货物所能承受的最大压力受限制，否则下 面的货物会被上面的货物损坏，所以装载层数、装载顺序要受限制。 ( 3 ) 稳定性的约束：装载完后，货物的重心应在集装箱的几何中心附近，以利于 运输安全。 ( 4 ) 货物的配置位置：货物的种类干差万别，货物不能任意摆放。有些货物不能 摆放在其它货物之上。 ( 5 ) 货物装载顺序：不同的货物在装载中应按不同的优先顺序装载，例如货物的 到站顺序不同，因此装载顺序相应的不同，先到站的货物要后装 1 2 第二章装箱问题的国内外研究方法缘述 ( 6 ) 装载的均匀性：在多集装箱装载中，有时要考虑多个集装箱之间的平均高度 或平均重量。 因此装箱问题是一个具有复杂约束条件的组合优化问题。国外自5 0 年代以来便 开始广泛研究，目前尚未形成一个统一的、一般性的处理方法，主要从一切实际应 用出发，针对不同特定背景的具体问题，从多种角度和方式不断提出其求解方法。 2 1 3 装箱阃隧的分类 实际问题中装箱要求和装箱象件的不同，装箱问题也将产生相应的变化。如当 布局物体的数量己知而布局容器的个数未知，则要求用尽可能少的容器装下所有的 布局物体；如果已知布局容器的数量，未知布局物体的数量，则要求每个布局容器 装下尽可能多的布局物体。 考虑到装箱问题中布局物体之间的装载顺序、布局物体的数量及布局容器的数 量关系的不同要求，对装箱问题的求解方法和求解目标的影响较大。为此根据是否 有装载顺序的要求将装箱问题分为： 点到点配载问题。货物的到站顺序相同，不同的货物在装载中没有优先顺序约 束： 点到多点配载问题。货物的到站顺序不同，不同的货物在装载中应按不同的优 先顺序装载，先到站的货物要后装。 根据布局物体的数量及布局容器的数量关系将装箱问题分为： 背包问题。即已知布局容器的数量，未知布局物体的数量，要求每个布局容器 装下尽可能多的布局物体： 容器问题。即当布局物体的数量已知而布局容器的个数未知，要求用尽可能少 的容器装下所有的布局物体。 由此可将装箱问题分为四种类型： 点到点配载问题点到多点配载问题 背包问题点到点配载背包问题点到多点配载背包问题 容器问题点到点配载容器闻题点到多点配载容器问题 2 2 装箱问题的国内外研究方法综述 布局问题属于复杂的组合优化问题，它涉及许多学科和领域，如运筹学，人工 智能、计算机图形、计算机辅助设计、计算机几何，建筑设计和航空航天等领域。 布局问题在文献上始见于1 9 3 0 年l v k a n = 【o v o n e h 的俄文文章( 1 9 6 0 年译为英语刊 登在m a n a g e m e n ts c i e n c e 7 7 上) 。有关布局问题的综述性文章，请见 3 3 ，3 4 ，7 8 ，7 9 ，8 0 l 。 d o w s l a n d k a 和d o w s l a n d w b 的论文 p a c k i n g p r o b l e m 是一篇用运筹学求解二、三 青岛大学硕士学位论文 维布局问题的较为全面的综述性文章。除了布局问题建默及其求解之外，作者还回 顾了布局问题的算法及启发式解法。文章比较偎! l 重一些具体问题的实际解法。 s w e e n c y 和p a t e m o s t e r 3 4 对切割和布局( s t o c kc u t t i n g a n d p a c k i n g ) 问题也作了综述， 论文中包含有4 0 0 多篇分好类的、面向应用的参考文献，其中包括书籍、学术论文 和工作论文等。d u c h o 珥7 8 】综合考虑各种切割和布局问题，提出了一种一致性的、 系统的方法，由此来实现在运筹学中的各种有关切割和布局问题的概念的统一。通 过这样做，作者试图未每种相关的问题找到一种恰当的求解方法；反过来，可以确 定用某种方法求解的问题类型。二维和三维布局问题及其实用的求解方法的综述也 可以从d o w s l a n d w b 的另篇文章【7 9 】中看到。在这片综述文章中，大部分的应用 是基于二维布局技术的，许多三维布局问题通过在每一层上应用二维技术来处理。 从该文看出：由于三维布局问题的复杂性，在布局问题的研究中，关于三维布局的 研究是有限的，只有少许与集装箱装载问题有关的论述。该文还总结了底盘装载问 题p a l l e tl o a d i n gp r o b l e m , p l p ) q a 需考虑的一些实际问题。如梭装载货物垛的稳定性、 堆垛中货物本身得承重性、码垛货物的难易程度及某些货物对空气流通的要求等。 相对于其它学科而言，目前国内外对布局问题的研究还不够深入，因此在这方面的 进展不是很大，以外的布局问题的求解方法归纳起来有如下几类： 2 2 1 象域模型 象域模型用于解决二维布局问题，它表达平面布局的方法是将某一物体占据的 平面空间赋予特定属性，构成一个象域以区别该物体周围的空间，根据物体布局问 题的具体要求不同，基于象域模型的布局方案生成算法有两类。一类是用于设备布 局，这类问题的特点是平面区域、待不物体的形状及大小都已定。算法的思想是通 过不断扫描二维数组，提取一些空间关系属性来指导物体的布置或修改物体的位置。 另一类是区域划分类，比如在布置一个工厂的各个车间时总是力求使原材料、半成 品的加工路径最短。对于这类问题，一般把路径长度和工件在该路径上往返运输的 频率这两项的加权值作为目标函数。先构造初始布局，然后再通过排列组合不断的 变换初始布局，直到找到一个是目标函数最小的布局方案为止。由于在布局过程中 总有许多空间是不规则的，用象域模型来描述空间，往往需要很大的计算机内存， 尤其是对于较复杂的实际问题。另外，活动空间之间的位置相互关系没有直接记录 下来。空间关系属性的获取需要庞大的数组进行扫描、分析来计算，由于消耗的计 算机内存与时问过多，因此到目前为止还没有实用的基于象域模型的平面布局方法 出现。值得一提的是有些象域模型的改进模型，如四叉树、串表达、相邻结构表达 等，虽然相对的节省了内存量，但仍没有完全解决占用内存太大这一问题。 2 2 2 数学规划法 将布局问题抽象简化为一定的数学模型，用组合最优化中广泛应用的线性规划 1 4 第二章装箱问题的国内外研究方法综述 法，整数规划法，分制定界法 1 ，8 和动态规划法等进行闻题求解，即所谓的数学 规划法。 分枝定界法是一种隐枚举法或部分枚举法。在大量有关矩形物体布局问题尤其 是板材加工业的一刀切问题上被广泛使用。分支定界法的关键是分枝和定界，原问 题有可能产生多个后继问题( 分枝) ，所有的后继问题的可行域中包含原问题的所有 可行解。根据需要各后继问题可以类似的产生自己的分枝，如此不断继续，直到获 得问题的较优解为止。定界是指在分枝过程中若某个后继问题恰巧获得问题的一个 可行解，那么它的目标函数就是一个“界限”，可作为衡量处理其他分枝的一个依据。 由于原问题的可行解集的一个子集，前者最优解的目标函数不会优于后者最优解的 目标函数值。所以，对于那些相应松弛问题最优解的目标函数值比上述“界限”，则 以它来取代原来的界限，这样可以提高定界的效果，使最后所得解的质量更好些。 有上面分析可以看出“分枝”为求得最优解的出现创造了条件，而“定界”则可以 提高算法的搜索效率。经验表明，在某些情况下根据对实际问题的了解事先选择 个合理的“界限”，可以提高分枝定界法的搜索效率。对于布局问题而言，分支定界 法是通过构造一棵搜索树遍历所有的布局形式，因而该方法还是通过原始的穷举法 来解决问题的。对于一些小规模的布局问题该方法是很有效的，如毛胚切割( 主要 是关于矩形物体布局问题，尤其是板材加工业中的一刀切问题) 等。但是随着规模 的增大树中的节点树目将迅速增加，从而导致分枝定界法的存储量和计算时间急剧 增加，所以该方法具有一定的局限性。 v a l e r i od ec a r v a l h o 8 2 等将两阶段下料问题抽象为约束优化问题，并用一 简化的线性规划模型来表达该约束优化问题，最后用列生成技术对得到的线性规划 模型进行求解。为克服线性规划模型中变量过多的情况，使用一个预处理过程并利 用特定的规则删除了一些不良模式，从而使问题得到解决。 b e a s l e y 8 3 则将布局问题抽象为o 一1 整数规划模型，基本思路是用一个二值变 量表示某类型特定物体的可行位置，代表布局容器的长方形则可表示为可行位置左 上角点的坐标分割成的网络。只要每个网络位置仅被不多于一个的布局物体所占据， 得到的一组布局物体的位置是可行的。 数学规划方法将布局物体抽象简化为一定的数学模型，当时的问题涉及一些易 用数学模型表达的约束条件时。采用各种近似方法得到数学模型往往会原文题产生 较大的偏差，并且当问题规模增大、解空间急剧增加时，他们的时间复杂性变得很 坏，但是，它在纯数学推导中加入了启发式经验，极大提高问题求解能力，这一思 想值得借鉴。 2 2 3 形态与形态法则 形态即定义在笛卡尔坐标系中得一组线段与标号；形态法则是有一个初识形态 青岛太学硕士学位论文 转化为另一些形态的规则集合这两项构成。用形态表示平面布局，用形态法则表示 布局设计的规则，则计算机布局的过程就是从初始形态开发，利用形态法则中的规 则进行自动推理的过程。人在设计时除了用图形表达布局外，还用到许多概念，如 拓扑结构、几何属性以及空间之间的相互关系等。有些因素显然不能用形态来表达， 从而形态的“语义”也很难抽取。如果计算机不能懂得它所产生的形态到底表示什 么，则计算机用形态法则的推理是盲目的，会产生一些毫无意义的方案。另外，怎 样构造形态法则也是一个困难。在实际问题总往往有太多的规则，根本不可能全部 获取并存贮与计算机中。这些因素使得形态法则只能用来处理具有某特殊的问题。 2 2 4 图论方法 图论作为组和数学的重要组成部分，是反应对象问关系( 如两种物品能否同时 放入同一个库房里) 的一种工具，它已经被广泛的应用在物理学、化学、控制论、 信息论、电子计算机等各个领域。早在1 9 6 4 就有人 9 提出以图论作文工具进行建 筑片面设计， d i t c h e l l 等人提出 1 9 了一个较为可行的方法，他们将平面布局问题 分两步来求解。首先求出满足相邻拓扑关系的无尺寸的平面布局，然后确定平面布 局中每个房间的尺寸。尽管许多学者已经进行了大量的研究，易产生组合爆炸，因 而该方法只限于解决小规模物体的布局问题。 在各种各样的图中，树作为一种简单而很有用的图在布局领域中有一定的应用 前景。文 1 0 中给除了基于二叉树结构的布局算法。 2 2 5 优化算法 在各种布局算法中，由于数值优化方法具有较为成熟的理论和相应算法，因而 被广泛用于工程设计领域，取得了许多令人满意的成果。布局问题也是它的一个应 用分支，u d y 1 1 利用序列二次规划和广义简约梯度法来解决小型三维布局问题，但 其解的质量过分依赖于初始位置的选择。k i m 和g o s s a r d 3 通过惩罚银子将布局约 束转化为目标函数惩罚项，然后用无约柬优化方法来求解，黄文奇等 1 2 ，1 3 提出了 一种求解布局问题的拟物方法。这种方法用物体间的“相互挤压弹性势能”来度量 物体间的相互嵌入程度，其中计算两物体间的距离仍没有很好的解决。 腾宏飞 “ 等以人造卫星舱的布局为背景，提出了旋转锥体空间中圆柱体群和 长方体群的布局优化算法。该算法以拟物法为基础，利用惩罚因子将布局约束转化 为目标函数惩罚项，然后用无约束优化方法进行求解。 优化方法依赖于数学模型，且只能找到局部最优解，所得解的质量在很大程度 上依赖于初始解的选择。当布局问题的规模较大或布局物体的形状较复杂时，优化 过程中进行的计算将变得相当复杂。 2 2 6 遗传算法 遗传算法是本世纪6 0 年代中期提出的，它是通过模拟生物进化的过程来求解复 1 6 第二章装箱问题的国内外研究方法综述 杂的优化问题 1 4 ，1 5 。由于利用了交叉和变异等遗传算子，该方法的求解范围可 以遍布整个解空间，有可能求出全局最优解。遗传算法根据适者生存、优胜劣汰等 自然进化规则，一代一代的优选适应性能评价函数的参数，重组后构成新的参数组 合。与许多传统的搜索算法不同遗传算法在搜索最佳组合时间时考虑搜索空间中 的多个点，而非仅考虑一个点。该算法使用参数集的数字串作为工作模式二不直接 使用参数本身。他的缺陷是处理大规模的连续变量有困难，因而一般需要与其它方 法组合实用。 i s r e n i 和h o n 9 3 通过每两个布局块间的空间的相对坐标和方位编码来定义一 个独立的解串，每个解的适应性能评价函数是面积利用率和干涉惩罚的组合，所用 的操作是一点交叉和变异。s h a h o o k a r 1 0 4 等将遗传算法用于大规模集成电路中集 成单元合理布局问题的求解。该算法的操作对象是代表各集成单元布局情形的基因 型。因为该算法同时对一组可行解进行操作并且在使用了选择、交叉和变异三种基 本操作的基础上增加了转换和倒置两种类型的操作，使得对解空间的并行搜索成为 可能，极大的提高了该算法的效率。 2 2 7 模拟退火算法 自从1 9 8 2 年k i r k p a t r i c k 9 7 等将模拟退火思想引入优化领域，模拟退火算法 因其有可能求得布局问题的全局最优解而引起人们越来越多的重视，迅速发展成为 一种求解大规模组合优化问题，特别是n p 困难组合最优化闻题的有效近似算法。 模拟退火算法的基本思想为：首先选取一可行状态作为初始状态，同时计算出 该状态的目标函数值，然后从当前状态的邻域中随机的产生下一状态并对此状态进 行评价，如果该状态的目标函数值有所提高，那么就接受该状态为新的当前状态， 否则以一定的概率接受该状态为新的当前状态。如此循环下去，直到找到一个满意 的最优解或达到终止条件为止。与遗传算法相似，如何针对实际问题构造出便于用 模拟退火算法解决问题的模型，是应用方法的关键。 布局模拟退火算法可归结为布局问题的改进启发式算法。其求解过程从一个初 始方案和一个较高的初始温度开始按给定的规则在前一方案的邻域内进行随机搜索 产生新的布局方案。按照评价函数和接受函数确定是否接受这个新方案为当前方案， 并缓慢的降低温度经过一段时间后可以获得更好的布局结果。模拟退火算法理论 上要求退火过程相当缓慢，即要求计算时间无限长，这样可以求得全局最优解。实 际上由于各种条件的限制做不到这一点，往往只能求得一个较为满意的近似最优解。 布局模拟退火算法的特点为： - 1 ) 当采用各种构造启发式算法不能求出被实际生产所接受的布局方案时，模 拟退火算法可适用于对布局方案的结果要求高而计算时间的限制较宽松的情况： 2 ) 模拟退火算法能够对布局方案必须满足的约束条件进行松弛化处理，而且 青岛大学硕士学位论文 将该约束条件的要求加入评价函数中，因此当布局问题存在多种约柬时，模拟退火 算法尤为适用。 3 ) 模拟退火算法的缺点是需要考虑各种因素以确定适当初始参数值，如果取 职不当会导致算法求解效果低下，甚至不能取得较好的布局方案。 s z y k m a n 9 8 等将模拟退火用于三维元件布局的自动生成。利用从形状语法和模 拟退火中抽象出的形状退火法生成三维元件布局问题的优化布局方寨，该方法以牺 牲全局最优解来换取较快的问题求解速度。 尽管模拟退火算法是目前一种有可能得到优化问题的全局最优解的问题求解方 法并且已经成为一种用于优化问题求解的一般的、通用的方法，但这是以极其漫 长的退火过程及问题求结果成为代价的。 2 + 2 ，8 启发式方法 工程实际中的一些问题往往可以借用一些标准的优化模型和求解算法有效的解 决，得出问题的最优解决方案。这些标准的模型和算法往往是针对某类实际问题而 设计的，针对性很强，但适用面窄，而且它们仅对良性结构问题是有效的。 但是很多实际布局问题不具有良性结构，当套用传统的优化算法处理时。就难 以得到满意的结果。这时与其偏离事实忽略或修正某些重要的条件，勉强适用某种 标准模型使问题得到简化而易于求解，还不如保持问题的本来面目，建立基本符合 问题实际情况的非标准模型，从与问题有关的基本模型核算法中寻求其中的联系， 从中得到启发，发现可用于解决该问题的思路和途径。人们称这种方法为启发式方 法，相应的，用这种方法建立的算法启发式算法。p e a r l 9 0 在其关于启发式方法的 专著中对启发式方法进行了详细的论述，并给出了启发式算法的定义，是指一组建 立在经验或判断的基础上指导算法搜索方向的、建议性的规则集，计算机通常可在 解空间中产生有关问题的一个好的解，但不能保证产生这个问题的最优解。即就是 那些从大量的实验数据来看，算法的实际计算性能较好。但理论上证明这些算法的 最坏解题性能并不好，或者理论上并不能证明这些算法具有优彘的解题性能。启发 式算法的设计不依赖于纯属数学优化理论的突破和发展因此其研究和应用获得了突 飞猛进的发展。 启发式算法建立在经验和判断的基础上，体现了人的主观能动作用和创造力。 用启发式方法解决问题强调“满意”，长长得到“满意解”，丽不苛求最优性和探求 最优解。之所以如此，原因主要有以下几点： 1 有很多问题不存在严格最优解( 倒如目标函数之间存在矛盾的关系，常常会 遇到两难选择或更加难以处理的情形) ，这时目标的满意性常常比最优性更能准确的 描述人们的意愿和选择行为： 2 对某些问题，要得到最优解需花费很大的代价，不实际，也不合算： 兰三皇鳖塑塑壁堕里堕苎要塞銮生! ! 兰 3 从实际决策的需要出发，有时不必要求解决方案具有过高的精度。 用启发式方法求解问题用通过迭代过程实现的，因而需拟定出一套科学的搜索 规则。未能得到满意的解，在整个迭代过程中要不断吸收出现的新信息，考察采用 的求解策略，必要时改变原来拟定的不合适的策略，建立新的搜索规则，注意从失 败中吸取教训，并逐步缩小搜索范围。以下是几种常用的策略： 1 分解合成策略 在解决一个复杂的大问题时，可首先将它分解为若干个小的子问题，再选用合 适的方法按一定顺序求解每个子问题。根据予问题之闯以及各子问题与总问题之间 的关系( 例如包含关系，平等关系等) ，将子问题的解作为下一阶子问题的输入，或 在某种兼容原则下进行综合，最后得到总问题合乎要求的解。 2 改进策略 在运用这一策略时，首先从问题的一个解决方案或初始解出发，然后对方案或 解的质量( 包括其可行性，可接受程度，目标函数值的优劣，对环境的适应性、可 靠性等) 进行评价，并采甩某种改进规则，对解决方案或初始解进行改进，直到满 意为止。 本策略包括确定搜索方向、拟定搜索方法、建立发现和收集在搜索过程中出现 的新信息的机制，并根据对新信息的分析结果，重新确立或改变原来的搜索方向， 修正搜索参数，消去不必要的搜索范围，目的在于提高搜索效率，加快收敛速度， 尽快获得合乎要求的解决方案( 问题的解) 。 总之，启发式方法可以分为两类。其一是构造法，该方法是从一个空的初始解 开始，按一定的顺序逐步增加解的分量，直到操作结束生成最终方案位置；布局启 发式算法中应用最多的方法是构造式算法，通过逐个的增加解的构造元素来得到闻 题的可行解。构造式算法的循环次数与问题的构造元素个数成正比，而与解空间的 大小无关，因此其计算速度通常很快。布局问题中构造法基本上由两类规则组成。 第一类为定序规则( o r d e r i n gr u l e s ) ，它被用来确定待布局物体放入布局空间的先 后顺序：第二类为定位规则( p l a c e m e n tr u l e s ) ，它用来确定每一个布局物体的摆 放位置。由于定序规则和定位规则的不同，也就产生了不同的构造布局方法。以往 使用效果较好的定位规则有 3 3 ，5 1 ，9 2 ： 1 按照布局物体最短边边长递减的顺序进行定序； 2 按照布局物体最长边边长递减的顺序进行定序； 3 按照布局物体体积递减的顺序进行定序； 4 按照布局物体最小面面积递减的顺序进行定序； 5 按照布局物体可行域递增的顺序进行定序； 许多学者 5 0 ，9 3 ，9 4 9 1 ，4 4 对布局问题中定位规则进行了研究，提出了如下一 青岛大学硕士学位论文 些规则和策略： 1 占角策略，即首先将布局物体摆放在布局容器的某一角； 2 顺放策略，即从布局容器的某一角开始将布局物体沿着容器的某一边摆放： 3 在底盘装载中，将布局立方体先沿着边放置，最后摆放到底盘中心； 4 在三维规则布局中从布局容器的某一面墙开始，一层一层的布局：在某一 面墙上，再确定一条边：最后归结为一个角： 5 在三维规则布局中，先按“右、前、上”的顺序找寻剩余空间，然后按照“左、 后、下”的顺序摆放布局物体； 启发式方法具有简便、灵活、计算速度快的优点，但它的明显缺陷是所产生的 解与最优解的差异很难评价。某些学者在评价布局启发式方法的计算性能进行了分 析；l i 5 3 ，9 5 对三维规则布局中的某些算法的最坏情形进行了分析。 由于构造法对像布局问题这类复杂的组台最优化问题具有很强的适用性并能 在较短的时间内给出一个较令人满意的解，因而关于它的研究人们仍然会做进一步 的努力。 其二是迭代法，它是从一个可行的初始解开始，每次迭代通过改变若干解分量 以得到一个更好的解，直至不能再改进为止。迭代法比构造法慢但所的解的优化程 度更高些。 2 2 9 改进布局方法 布局启发式算法中的另一类算法为改进算法，为了提高布局效率，布局设计入 员可以先采用某种方法生成一个可行的布局方案，之后再利用改进法对所得到可行 解进行调整。即先从一个可行解开始，采用交换、合并、增加、删除等操作对可行 解邻域内的元素进行操作，以改进解的质量。a l b a n o 1 6 利用一交互系统对二维布 局问题进行了改进。算法的过程为：系统首先产生了一个初始布局方案，若用户对 该方案较为满意，则布局结束并输出布局方案，否则用户给出修改信息用以指导系 统利用上述操作对所有解进行调整。这个过程反复进行直到出现较为满意的布局方 案为止。黄文奇等 1 7 提出了方格布局问题的改进策略，方法是：先采用局部调整 策略进行改进。即在某一时刻，若位置总势能u 卜0 ，则令各布局块沿受力方向移 动一定的距离，得到下一时刻的位置，接着判断在新位置处的势能，如果在新位置 处u 2 0 ，则上述调整策略成功，停止运算。若u 虽不为零但已有所减少则按受力 方向将布局块继续移动，若u 未减少则该策略失败。当局部调整进行到总势能已无 法再减小但仍大于零时，再采用大范围调整策略，即将具有最大挤压弹性势能的布 局块放副当前状态下布局空间中空隙最大的位置。前文提到的线性规划法、优化算 第二章装箱问题的国内外研究方法综述 法、以及遗传算法、模拟退火算法和启发式算法都可用作改进算法。 2 3 问题的描述与建模 根据项目背景，本文研究的阃题可以描述如下： 对于一个已知尺寸的标准集装箱( 2 0 英尺或4 0 英尺) ，以及一组( n 类) 已知 尺寸的待装箱的长方体盒子，本文的目的是确定一种集装箱装载方案，以便将所有 盒子装入集装箱：如果不能将所有盒子装入集装箱，则本文的目的是找到一个待装 盒子的子集，以使集装箱的空间浪费率最低，或者说使集装箱的空间利用率最高。 该问题的数学模型是： 假定集装箱的长( 本文用深度表示) ，宽，高为d ，w ，h 待装箱的n 类长方体盒 子的长。宽，高为砖，毗，吩( f 2 l ，2 ，帕。问题的目标函数为 m a x f = 4 m f d w h - l 对于上述模型，有必要进行如下补充说明： 本文研究的是单一装箱的装载问题。 本文采用的坐标系为三维迪卡尔坐标系，该坐标系以集装箱的深度方向为x 轴，集装箱的宽度方向为y 轴，集装箱的高度方向为z 轴。集装箱的左后下角为( o ， 0 ，0 ) 。 鉴于实际项目背景，本文的问题限定为弱异类c l p 问题。即，盒子的种类不 是很多，但每种盒子的数量却相对较多。( 比如，一个集装箱内装有三种规格的空调 各几十台。由于每种空调包括室内杌，室外机，及配管三种盒子，所以这个装箱问 题为九种盒子，盒子的种类不是很多，但每种盒子约有几十个。这是典型的弱异类 问题。) 。 同样鉴于实际项目背景，盒子的摆放要求正面向上。即，盒子只能绕z 轴旋 转9 0 度，不能绕x 轴或y 轴旋转。 另外，为了最大限度的满足问题的需要而又不失一般性，本文的问题模型还有 如下限定： 为了保证盒子放置的稳定性，盒子的几何中心即为其重心。 盒子理论上可以放置在集装箱的任意位置，但不能超出集装箱的容纳范围， 也不能与其它盒子交叉放置。 盒子的摆放必须与坐标轴平行或正交，而不能斜放。 盒子不能悬浮放置。 上述假定可以使模型简化，并且足以适用很多实际问题。 2 l 妻璺查兰堡主兰望! 坚 一 第三章有约束的三维矩形物体布局的启发式算法研究 3 1 矩形物体布局的启发式规雯i i 3 1 1 布局空间的分解 图3 i 空闻分解图3 2 可行域 本文基于二叉树的数据结构将布局空间分解。其分解过程为：先对原始布局空 间求解，此时原始布局空间为当前布局空间，对应于二叉树的根结点：按定序规则 ( 见2 小节) 选择一个相对于当前布局空间为最优的布局物体a ，将其定位于当前 布局空间的左上角( 见图3 1 ) ；这样原布局空间变成了一个l 形区域，分成图1 所 示两个矩形a l 和a 2 ，分别对应于根结点的左、右两个子结点，然后分别对这两个 子结点重复上述分解过程，直到没有可选布局物体满足要求时停止。 3 1 2 定序规则 一般情况下。人们通过比较布局物体的某一项或某几项属性( 如体积、面积等) 来建立定序规则，从而决定布局物体放入布局容器的先后顺序。许多研究人员经过 长期的实践探索提出了许多定序规g i j 1 1 6 - 1 1 7 。概括起来有：按待布局物体面积 递减定序：按待布局物体最长边递减定序；按待布局物体最短边递减定序： 按布局物体几何可行域递增定序。 文献【1 1 7 】指出，前3 种定序规则实质上都是第4 种定序规鼹i j 的不同表现形式。 待布局物体在布局空间中所有可行位置的集合表现为一个面积区域，因此称之为可 行域。如图2 所示，待布局物体的面积越大，其可行域越小；最长边越长，可行域 越小。 本文用下列公式计算可行域的面积 f = 0 6 ) ( b 一4 ) + ( b 一6 ) ( 6 一矗) 茸f = ( a 一口) ( 8 6 ) + c 4 6 ) + ( 6 一口) 3 - ( 1 ) 3 - ( 2 ) 式中，a 、b 为当前布局空间的边长：口为待布局物体较短的边长，b 为待布 局物体较长的边长。 第三章有约柬的三维矩形物体布局的启发式算法研究 如果f 0 ，则表示待布局物体无法布入当前布局空间，将其从待布物体序列中 易0 除。 如果f = 0 ，则表示待布局物体可行域面积为零。此时，可行域可能为一条直线 或一点令d 代表可行域线段的长度。令e = 0 6 ) p 一口) ，e = 0 一口) + 一6 ) ， 若e 5e 2 0 ，表示可行域为一点。表示待布局物体刚好放入布局空间中，此时令 l d = 0 ；若只曩= o ，则令l d = m a 】【舭一6 ) p 一4 ) ；若只r = 0 ，则令 l d = m a x 始一口l o 一6 ) 。 根据上述讨论，本文提出相应的定序规则： ( 1 ) 根据待布局物体相应的可行域面积，的大小，按递增的顺序排列； ( 2 ) 将可行域面积f 小于零的待布局物体，从待布物体序列中剔除： ( 3 ) 对可行域面积f 等于零的待布局物体，比较可行域线段的长度l d ，按递 增的顺序排列。 该定序规则既具有上述的灵活性，还具有动态特性。因为该算法采用布局空间 逐步分解的方法，所以布局空间的大小是不断变化的，可选待布局物体对于不断变 化的布局空间的布入顺序也在不断变化。这样保证了每次放入的都是相对于当前布 局空间来说是最优的待布局物体。这同优化理论中最大梯度法是一致的。 3 1 3 摆放规则 根据我们目前所掌握的资料，就待布局物体摆放规则的研究还比较少。一般提 到的摆放规则有： ( 1 ) 固定的摆放规则，即固定的待布局物体长对应原始空间宽( 如图3 ) 或待 布局物体长对应原始空间长( 如图4 ) ； ( 2 ) 待布局物体长对应当前布局空间长或待布局物体长对应当前布局空间宽。 图3 3 产品长对应原始空同宽图3 , 4 产品长对应原始空间长 1 摆放规则1 青岛大学硕士学位论文 就同一待布局物体而言，不同的摆放方式，将会影响到后续待布局物体的布入 顺序甚至最后的布入结果。若将布局空间的宽和长分别记为a 、b ，待布局物体的 宽和长分别记为口、b ，则对于图3 中待布局物体长对应原始空同宽的摆放规则， 其可行域的大小记为e ， e = 乜一6 ) p 一口)3 一( 3 ) 对于图4 中待布局物体长对应原始空间长的摆放规则，其可行域的大小记为p ：， 疋= 0 一口) ( b - b ) 3 一( 4 ) 摆放规则1 的基本思路为每次在布局空间装入产品前，按照f 和f 2 的大小，确 定动态的摆放规则：f 小则按f 对应的摆放规则摆放，反之则按e 对应的摆放规则 摆放。 摆放规则i 中认为待布局物体的摆放方式与其在当前布局空间中的可行域有 关，然而由于空间分解，人为地将后续待布局物体限定在一个相对狭小的空