（计算机应用技术专业论文）基于禁忌搜索算法的集装箱装载问题研究.pdf

沈阳工业大学硕士学位论文 摘要 集装箱装载问题( c o n t a i n e rl o a d i n gp r o b l e m ，简称c l p ) 属于“切割和装入”问题， 在数学理论上为n p 完全问题，即不能在多项式时间内找到问题的最优解。c l p 虽然求 解困难，但随着计算机技术的发展，使用计算机辅助求解c l p 成为可能，但因c l p 本 身特征，实际应用中无法采用纯数学方法，而是采用基于启发式的近似求解方法。 计算机辅助布局优化能够有效提高空问装载效率，在铁路和远洋运输中能够降低运 输成本，研究成果还可以推广到计算机内存分配等空间资源优化领域，因此有着重要的 实际意义。近年来c l p 逐渐成为人们关注的焦点。 本文绪论先对c l p 的产生背景及实际意义进行论述，然后对其研究范畴和分类予 以介绍，最后在查阅大量文献的基础上阐明了c l p 的国内外发展现状。 禁忌搜索算法( t a b us e a r c h ，简称t s ) 是近年来逐渐引起人们兴趣的一种现代启 发式算法，因其特殊的“记忆”机制，表现出极好的全局寻优能力，在对一些复杂、困 难问题的求解中取得了很好效果。本文从t s 的原理、搜索技术以及收敛理论等方面进 行说明。 应用t s 求解c l p 在国内还没有相关研究，本文结合c l p 的实际特征，提出了不 同于b o r t f e l d t 和g e h r i n g 方法的新的编码、解码及邻域解构造方法；在解码中引入了新 的空间合并策略，提高了集装箱利用率；应用“组合块”思想减少了剩余空间的零碎划 分，降低了搜索代价；本文创造性的将t s 应用于求解多箱装载问题，取得了理想效果。 结果显示对于集装箱装载系统的应用有重要意义，本文给出了数据显示和图形显示 两种方式。数据显示精确描述装载方案中物体顺序、位置等信息；图形显示提供了装载 方案的可视化效果，更便于用户观察。 实例分析部分通过对4 个标准数据集进行测试，证明了用t s 求解c l p 的有效性和 实用性，同时讨论了算法中存在的优点与不足。 最后对全文工作进行总结并对以后的研究方向进行了展望。 关键词：集装箱装载问题，禁忌搜索，布局优化，胛完全问题，启发式算法 基于禁忌搜索算法的集装箱装载问题研究 r e s e a r c ho nc o n t a i n e rl o a d i n gp r o b l e mb a s e do nt a b us e a r c h a b s t r a c t c o n t a i n e rl o a d i n gp r o b l e m ( c l p ) b e l o n g st o ”c u t t i n ga n dp a c k i n g ”p r o b l e ma n dan p c o m p l e t ep r o b l e mi nm a t h e m a t i c s f o rt h i sc a s e ，i tc a nn o tb eu s e dt og e tt h eb e s ts o l u t i o ni n p o l y n o m i a lt i m e a l t h o u g hc l pi sc o m p l e x , w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e ，c l p c a nb es o l v e d 、撕t l lt h eh e l po fc o m p u t e r o w n i n gt ot h ea t t r i b u t eo fc l pi t s e l f , c l pc a nn o t b cd e a l ti no n l yp u r em a t h e m a t i cw a yi np r a c t i c e b u ti na na p p r o x i m a t ew a y , s u c ha sh e u r i s t i c m e t h o d c o m p u t e ra i d e dl a y o u to p t i m i z a t i o nc a ni m p r o v et h ec o n t a i n e rl o a d i n ge f f i c i e n c y f o r t h i sr e a s o n , t h et r a n s p o r t a t i o nc o s to f 期i l w a ya n do c e a ns h i p p i n gc a nb ec u td o w n a n dt h e p r o d u c t i o no fr e s e a r c hc a nb ee x t e n d e di n t os p a c er e s o u r c ea l l o c a t i o n , s u c h 鹤c o m p u t e r m e m o r ya l l o c a t i o n t h u s ，c l pi sb e c o m i n g a st h er e s e a r c hf o c u si nr e c e n ty e a r s t h ep a p e ri n t r o d u c t i o nf i r s t l yd i s c u s s e st h eg e n e r a t i o nb a c k g r o u n da n dp r a c t i c a lm e a n i n g o fc l p ，a n dt h e ne x p l a i n st h ec a t e g o r yo fc l p ，a tl a s tc o n c l u d e st h er e s e a r c hs t a t u si nq u o a c c o r d i n gt oag r e a td e a lo f l i t e r a t u r e s 。 t a b us e a r c ha l g o r i t h m ( t s ) i sak i n do fm e t a - h e u r i s t i ca l g o r i t h m s ，a n di sf a m o u sf o ri t s s p e c i a l m e m o r y ”m e c h a n i s m i th a sa m a z i n ga b i l i t yt os e a r c hg l o b a l l y g o o dr e s u l t so fs o m e d i f f i c u l ta n dh a r dp r o b l e m sh a v eb e e na c h i e v e df o rt h i sr e a s o n t h ep a p e ri n t r o d u c e st sf r o m p r i n c i p l e ，s e a r c h i n gt e c h n o l o g ya n dc o n v e r g e n c et h e o r yi nd e t a i l t h e r ea r en or e s e a r c h e st os o l v ec l pw i t ht si nd o m e s t i ca tp r e s e n t t h i sp a p e rp u t s f o r w a r dan e wc o d i n g ，d e c o d i n ga n dn e i g h b o rs o l u t i o ng e n e r a t i o nm e t h o d sd i f f e r e n tf r o mt h a t o fb o r t f e l da n dg e h r i n g an e ws p a c ec o m b i n i n gs t r a t e g yi si n t r o d u c e dt oi m p r o v et h e c o n t a i n e ru t i l i z a t i o n t h e ”c o m b i n e db l o c k ”m e t h o dr e d u c e st h er e s i d u a ls p a c ep a r t i t i o na n d t h ec o s to fs e a r c h i n g a p p l y i n gt st os o l v em u l t i - c o n t a i n e rl o a d i n gp r o b l e mi sac r e a t i v e a t t e m p ti nt h i sp a p e r ，a n dt h er e s u l t si sg o o df o r t u n a t e l y t h e d i s p l a yp a t t e mo fr e s u l t sh a si m p o r t a n tm e a n i n gf o rc o n t a i n e rl o a d i n gs y s t e m t h e r e a r et w op a a e m si nt h i sp a p e r ，w h i c ha r ed a t ap a n e r na n dg r a p h i c sp a t t e r n d a t ap a r e mc a n d e s c r i b et h es e q u e n c ea n dp o s i t i o ni n f o r m a t i o na c c u r a t e l y a n dg r a p h i c sp a a e mc a n # v et h e r e s u l tav i s u a la n dv i s i b l ee f f e c t w h i c hi sm o r ec o n v e n i e n tf o ru s e ro b s e r v i n g 沈阳工业大学硕士学位论文 t h ei n s t a n c ea n a l y s i st e s t s4s t a n d a r dd a t as e t s a n dt h er e s u l t sp r o v et h a tu s i n gt st o s o l v ec l pi se f i i c i e ma n dp r a c t i c a l t h ep a p e ra l s od i s c u s s e st h ea d v a n t a g ea n dd i s a d v a n t a g e o f t h ea l g o r i t h ma c c o r d i n gt ot h et e s tr e s u k s f i n a l l y ，c o n c l u s i o n so ft h ew h o l ed i s s e r t a t i o na l ed r a w na n dt h ep e r s p e c t i v eo fr e s e a r c h d i r e c t i o n si sg i v e n 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 ，t a b us e a r c h ，l a y o u to p t i m i z a t i o n , n pc o m p l e t ep r o b l e m ，h e u r i s t i ca l g o r i t h m 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：耋窒丝日期：2 竺z ：2 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：盔宝墼! 导师签名：垒：j 壶垄整日期：互! 互：7 签名：叠鬈墼! 导师签名：垄：j 叠望整日期：互! z ：7 沈阳工业大学硕士学位论文 1 绪论 1 1 课题背景及意义 伴随着我国加入世界贸易组织( w t o ) ，全国的集装箱运输业面临前所未有的发展 机遇，但由于物流规模和物流成本不断上升，使在生产和运输规划中，有效的利用集装 箱装载空间成为节约成本，提高经济效益的重要手段之一。大型零售连锁企业、船公司、 船务公司和进出口公司等在集装箱中进行不同货物装填时，对装填的效率和效益有很高 要求。现在还大量存在的人工估计装填方法，往往在确保全部装下的前提下，需要保留 足够空间，浪费了宝贵的远洋货运空间，增加了运输成本。因此，降低运输成本、提高 集装箱利用率以及装箱效率，将带来可观而直接的经济价值和社会价值。利用计算机强 大的数据处理功能可以生成科学、高效的装箱编排方案。集装箱装载问题( c o n t a i n e r l 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 2 2 分类 从名称上看，裁剪和装填问题似乎为两类问题，但本质上两种问题没有严格界限， 可以将其看作一大类问题来考虑。原因有二：首先，它们都有两组最基本的数据，一组 是大的空间或原料，另一组是小的物体或形状；其次，它们在本质上都是一种几何组合， 即将小的物体或形状进行某种组合，使之能充分利用大的空间或原料。 裁剪与装填问题是在一维、二维、三维物理空间中进行的。从这个角度出发，裁剪 与装填问题可以分为：各种原材料的裁剪问题( s t o c k - c u t t i n g p 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 gp r o b l e m ) 。其中，三维装填问题 又可细分为单元装箱问题( b i np 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 ) 等。上述分类又可进一步按物体的形 状分为规则形状问题、不规则形状问题等。三维装箱问题比二维排料问题更加复杂，要 想得到优解更不容易。本课题主要研究的是“切割和装填”问题中的集装箱装载问题。 三维装入问题是指寻找多个较小物体合理地放入较大物体( 如集装箱) 中的布局问 题。目前研究的主要对象是长方体形状的盒式物体。根据装载工具的不同，口丁分为货盘 装载和集装箱装载问题| z i 。 沈阳工业大学硕士学位论文 1 2 3 货盘装载 货盘( p a l l e t ) 是一种只有底面没有四周墙壁和顶面的托盘。货盘装载是将货物装在 侧面没有遮挡或支撑的货盘上，装载货物的边平行于货盘的边，物体之闻互不重叠，而 且物体装入的高度不能超过货盘限定的高度，使得装载的利用率最大。典型应用为自动 仓库中基于货盘的物品传输。根据待装物体尺寸的不同，可以分为生产商货盘装载和批 发商货盘装载。 生产商货盘装载( m a n u f a c t u r e sp a l l e tl o a d i n g ，简称m p l ) 涉及的待装物体都是 同样的尺寸，即它们的长、宽、高都是相等的，这种方式多用于生产同一产品的厂家。 在m p l 方式中，为了便于控制，大多数文献都是将所有待装物体沿着同一朝向放置， 这样可实现按层放置，每一层相当于二维排料中的放置算法，事实上将m p l 问题转化 为二维平面矩形排放的问题，而且都是同一尺寸的物体，约束条件比较简单，所达到的。； 优化程度比较高。 批发商货盘装载( d i s t r i b u t o r sp a l l e tl o a d i n g ，简称d p l ) 所装入物体的尺寸不相等， 主要针对一些大型批发厂家货物种类比较多的情况。批发商货盘装载算法由于物体的种 类多，实现起来比生产商货盘装载算法困难。最初的解决方法是将其转化为较容易处理 的二维装入问题，这种处理方法只有当装入物体的高度尺寸相同时才可行。后来从三维 装载的角度来考虑问题，使用了启发式方法等算法 1 2 4 集装箱装载 集装箱( c o n t a i n v r ) 是一种不仅有底面而且还有四周箱壁以及箱顶的封闭型的矩形 盒式容器，是一种重要的储存以及装载运输物体的工具，广泛的应用于生产批发商和运 输部门货物的装载运输。集装箱装入问题与货盘装载问题不同。首先，集装箱是封闭式 容器，所能利用的空间资源限制比货盘装载要严格的多；其次，由于集装箱装入的货物 只能通过侧门进入，因此不仅要得到对空间利用率的优化，对装入的过程的描述也必须 是明确和可行的。耳前集装箱装载问题的研究多数是针对多种不同种类物体的装载问 题，所以对集装箱装载问题的处理要比对货盘装载问题的处理复杂和困难。 基于禁忌搜索算法的集装箱装载问题研究 1 3 集装箱装载问题研究现状 1 3 1 主要研究方法 有关布局问题的综述性工作详见文献 2 ，3 】。目前大部分文献是研究二维或三维矩形 物体在矩形容器中的布局。研究方法主要有线性规划法、动态规划法、传统启发式方法 及现代启发式方法( 如模拟退火算法、禁忌搜索算法、遗传算法) 等等。 ( 1 ) 传统启发式方法( h e u r i s t i ca l g o r i t h m ) 的基本思想是依靠入的先验知识确定每 一步的排放策略，从而得到目标的优解。传统启发式方法的一般步骤是从与待解问题有 关的信息中得到评价函数来确定搜索方向，使过程中的每个状态向目标状态方向前进， 其中状态( 已装入、未装入和剩余空间) 的表示是个共性问题，而装入策略和评价指标随 着具体问题的变化而变化。 求解c l p 的传统启发式方法多是按某种指标( 如面积、边长、体积) 对矩形货物 排序，优先在剩余空间放置大的货物。采用传统启发式算法的好处在于它相比遗传算法 等现代启发式算法减少了盲目性，但是它得出解的质量往往不是很高。 ( 2 ) 模拟退火法( s i m u l a t e da n n e a l i n g ，简称s a ) 是模拟热力学中经典粒子系统的 降温过程来求解规划问题的极值。当孤立粒子系统的温度以足够慢的速度下降时，系统 近似处于热力学平衡状态，最后系统将达到本身的能量最低状态，即基态，这相当于能 量函数的全局极小值点。由于模拟退火法能够有效地解决大规模的组合优化问题，且对 规划问题的要求很少，因此引起研究人员的极大兴趣。当系统温度足够低时，就认为达 到了全局最优状态。按照热力学分子运动理论，粒子作无规则运动时具有的能量带有随 机性，温度较高时，系统的内能较大，但是对某个粒子而言，它所具有的能量可能较小。 因此算法要记录整个退火过程中能量较小的点 4 1 。国内外有对此问题的一些研究【4 5 一。 ( 3 ) 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是一种随机性优化算法，最初由美国 密歇根大学j h h o l l a n d 教授于1 9 7 5 年提出。它的突出特点在于包含了与生物遗传 及进化很相似的步骤，如遗传、变异、选择等。遗传算法与传统的优化算法相比，具有 以下特点： 1 ) 该算法是利用目标函数本身的信息建立寻优方向，而不是利用其导数信息建立 寻优方向，因此它对优化设计问题的限制较少，仅要求问题是可计算的。 沈阳工业大学硕士学位论文 2 ) 遗传算法利用概率转移规则，可以在一个具有不确定性的空间上寻优。与一般 的随机型优化方法相比，遗传算法不是从一点出发沿一条线寻优，而是在整个解空间同 时开始寻优搜索，因此可以有效地避免陷入局部极小值点，具有全局最优搜索能力。 3 ) 在该算法中，由于群体中每个个体的搜索是独立进行的，因此算法具有内在的 并行性【4 l 。 这些优点使得g a 能处理许多传统优化算法无法解决的复杂问题，但g a 在许多问 题的早熟( 即过早收敛于局部最优解而非全局最优解) 现象始终未得到很好的解决，在 将g a 应用于布局优化时有时得不到最优解，即存在遗传欺骗问题【刀，国内外对此进行 了一定的研究砥o l 。 ( 4 ) 禁忌搜索( t a b us e a r c h ，简称t s ) 是一种现代启发式( m e t a - h e u r i s t i c ) 搜索算 法b l , t z l 。f r e dg l o v e r 于1 9 8 6 年首次提出这一概念，进而形成了一套完整的算法。t s 通 过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免 一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局最优化。其最引人 注目的地方在于其跳出局部最优解的能力。t s 与g a 和s a 最大的不同在于，后两者不 具有记忆能力。与传统的优化算法相比，t s 算法的主要特点是： 1 ) 在搜索的过程中可以接受劣解，因此具有较强的“爬山”能力； 2 ) 新解不是在当前解的邻域中随机产生，而或是优于“b e s ts of a r ”的解，或是非 禁忌的最佳解，因此选取优良解的概率远远大于其他解。 禁忌搜索在求解一些困难复杂的问题时表现出极好的寻优能力，近年来被应用到优 化问题的诸多领域，有广泛的前景。 ( 5 ) 线性规划法和动态规划法，它们存在的主要问题是计算时间和空间代价随问题 规模成指数增长，只适合于小规模的排料问题1 ”4 1 。 1 3 2 国内外研究动态 目前的研究大多针对相对简单，但实际应用中常用的盒式物体，从己经发表的有关 文献来看，大多数研究者的工作采用寻找近似最优解的方法，通常是基于基本启发式的 方法，近年来采用现代启发式方法的研究也逐渐涌现，并取得了很好的结果 ( 1 ) 国内使用传统启发式方法求解c l p 方面的研究 基于禁忌搜索算法的集装箱装载问题研究 姜义东提出基于空间分解的启发式算法 1 5 】，采用三叉树的数据结构来处理剩余空 间，使用深度优先的处理方法处理三叉树得出布局结果。该算法采用优先放置大体积物 体策略，每次都先把最大体积的物体放入剩余空间。每放一个物体，就把当前空间划分 成三个小空间，然后在逐个对小空间进行填充。虽然这样划分剩余空间会降低问题的复 杂性，但是划分后剩余空间比较“零碎”。 樊建华的算法【1 6 1 与姜义东的算法【”1 类似，她提出了采取先放置边长大的物体的策 略，在剩余空间内先放置边长大的物体，不同的是她优先考虑多个同类物体并排放置刚 好能在空间底面的宽度或长度方向放满的情况，这样可以减少产生空间碎块，降低空间 的复杂性。同时她也考虑了剩余空间的结合问题。上述两种算法b s j 6 都提出优先放置大 物体，逐个对物体进行排放的策略。 这两种算法虽然在一定的范围内可以达到局部最优，但还可以通过针对剩余空间寻 求几个小物体的适当组合来代替简单的选用大物体以提高集装箱的空间利用率。同时也 存在一定的策略使对剩余空间的描述更加简化，以减少计算的复杂度。刘嘉敏，马广琨 的算法【1 7 】针对以上不足进行了改善。 ( 2 ) 国内使用现代启发式方法求解c l p 方面的研究 天津大学王金敏等用标准模拟退火算法求解三维布局问题【1 8 1 。该算法没有提到三维 矩形物体的种类情况，即没有具体的问题背景。算法中给出了目标函数、约束条件、求 解的初始温度及退火策略。该算法的初始解采用随机解。邻域解通过随机移动操作产生。 算法收敛速度较慢，同时没有明确给出和其它算法的比较测试结果。 中国科技大学曹光彬等先后给出了采用遗传算法【1 哪和免疫遗传算法求 2 0 1 解装箱问 题的算法。但算法也没有给出问题的实际背景。他们的第一个算法是一个标准遗传算法， 第二个算法是对第一个算法的改进，遗传算法改用为免疫遗传算法。在免疫遗传算法中 编码仍然采用二进制编码方式，选择抗体时采用轮盘赌法。算法给出了实验结果和布局 平面图。由于算法只是从随机产生的0 ，l 染色体编码出发，采用标准的遗传算法和标 准的免疫遗传算法来解决问题，难以保证解的优良性。另外，该算法没有涉及如何保持 由下而上的每层中小长方体高度一致的问题。从该算法的结果来看，小长方体会出现悬 空放置或倾斜放置的问题。 6 一 沈阳工业大学硕士学位论文 中国海洋大学的丁香乾、北京交通大学的何大勇采用遗传算法求解复杂集装箱装载 问题【2 1 9 1 ，在集装箱数目较少时有不错的表现，但是当小箱子数目很大时，两篇文献中 采用的编码方法会造成解空间急速膨胀，搜索效率降低。 ( 3 ) 国外使用传统启发式方法求解c l p 方面的研究 g e o r g e 和r o b i n s o n 建立沿着集装箱宽度的层，尽量使某一层的外表面平整，并且 结合剩余空间以提高空间利用率 2 2 1 。在建立一个新层之前，要评估哪些物体可以作为“新 开”层的物体来放置，这有赖于评定的优先级函数。第一个标准是先选择数量最大的物 体，因为这样很容易填充一层，第二个标准是物体最大维度的尺寸，如果它很大，物体 也许很难放入，装入时应该先放入这样的物体。但是当小物体的数量多，大物体的数量 少，则会使小物体优先放入，导致大物体被剩余，从而降低了空间利用率。 b i s c h o f f 和d o w s l a n d 同g 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 方法的过程有两个主要不同： 首先，每一层由单一类型物体组建；第二，层内物体的布局通过二维布局过程来决定。 它旨在最大化横截面( 集装箱的宽度和高度组成的矩形) 的面积利用率。层的深度选择 对空间利用率的影响很大。按层来放置物体，层的深度如果决定了，横截面就可以通过 二维布局来求解。通过层的划分，三维问题可降为二维问题来解决，大大的降低了问题 的复杂性，简化了剩余空间的描述。这两种方法只有在同种物体的数量很大时才会有较 明显作用。 b i s c h o f f 和m a r r i o t t 研究了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 方法，通过6 个等级规则，即待装入物体的最小边降序排列，物体最小边升序排列，物体数量的降序 排列，物体数量的升序排列，物体体积的降序排列，物体体积的升序排列，提出了1 4 种集装箱装入的启发式方法 2 4 1 。通过大量的实例进行分析，对这1 4 种算法性能进行比 较，得出集装箱装入结果的优劣在一定程度上依赖于待装物体种类多少的结论，并建议 针对物体种类和数目，采用不同的启发式方法。并提议依此设计复合启发式算法，针对 箱子类型的数目采用不同算法。该方法表明传统启发式方法的性能非常依赖问题领域， 受物体数量变化的影响也很大。由于b i s c h o f f 等人的验证和分类，后来的研究者对物体 进行不同方式的组合，如层、列、块、堆等方式，基于这种组织方式开发相应问题的启 基于禁忌搜索算法的集装箱装载问题研究 发式求解方法，如墙壁支撑( w a l l b u i l d i n g ) 方法1 2 4 - 2 7 1 、堆( s t a c k b u i l d i n g ) 方法【2 8 捌、 立方体布局( c u b o i d sa r r a n g e m e n t ) 方法【3 0 1 、剪切机方法f 3 l l 等。 d a v i dp i s i n g e r 提出了基于墙壁支撑的集装箱装载启发式方法【3 ”，把整个集装箱分 解成若干层，每一层又分解成若干条。层由一系列垂直或水平的条所组成，层的深度也 就是每条的厚度，由分枝定界法解决，而条的布局可转化为等宽或等高的一维背包问题 来处理。在此启发式方法中使用搜索算法来寻找层深度和条宽度的集合，为了减少复杂 性，并有效地控制层深度和条宽度的搜索，设计了2 7 个分类规则。该算法分别对同质 类( h o m o g e n e o u s ) 和异质类( h e t e r o g e n e o u s ) 问题进行了测试，其结果表明对于较大 规模问题有更优的解。 m i c h a e le l e y 提出了建立相同方向物体的同质块算法1 3 2 1 ，把相同的物体按照同样的 方向组合成块，然后由这些同质块填充集装箱。首先提出了一个贪婪启发式算法，它产 生预期的块布局，通过评估标准来决定物体的方向和剩余空间的最好组合。然后提出搜 索算法来改进贪婪启发式算法的解。为了简化问题的复杂性，树的分枝不是对每个不同 物体进行分配的，而是对不同类型物体进行分配的。因为不可能对所有子问题完全分枝， 因此又提出了一个评价函数，鉴别最有希望( p r o m i s i n g ) 的结点，修剪没有希望的结点。 这个函数不仅要考虑迄今得到的空间利用率，也要评估剩余物体填充剩余空间的潜力。 但是这只是一个理想的函数，没有确切的界限，只在树搜索中使用下界并且限制宽度搜 索。这样做的好处是相同的物体放置在一起，使集装箱中的物体比较稳定，装卸方便， 放置容易。 ( 4 ) 国外使用现代启发式方法求解c l p 方面的研究 国外采用现代启发式方法求解c l p 的研究主要集中在b o r t f e l d t 和g e h r i n g ( 他们的 研究在大多数评价指标上代表了目前世界最高水平) 。他们采用遗传算法1 2 8 1 和禁忌搜索 算法【3 3 l 求解c l p 并对标准数据集进行测试，测试结果相比传统的启发式方法有了很大 的提高。在用遗传算法时，采用“层”的思想进行局部填充：而在用禁忌搜索算法时， 采用“同质块”的思想进行局部填充。局部填充都是作为个基础过程被高层现代启发 式算法调用的。实验证明基于“层”思想的遗传算法更适于求解物体种类相对较多，而 每种物体个数不是很多的“强异质类”问题；而基于“h 质块”的禁忌搜索算法更适于 沈阳工业大学硕士学位论文 求解物体种类相对较少，每种物体数目较多的“弱异质类”问题。两篇文献的结果进行 比较，禁忌搜索算法要强于遗传算法。但两篇文献中都没有提到对多箱问题的求解。 1 4 本文工作及结构 c l p 如前所述是一个复杂而又有着重要实际意义的问题，但是应用中存在装载效率 不高，空间浪费多的情况。本文在查阅和归纳大量相关资料的基础上，针对一种现代启 发式算法禁忌搜索算法( t s ) 进行描述和分析，并将其应用于求解c l p ，根据具体 应用提出了新的编码、解码、评价函数设计、空间合并等方法，不仅解决了单箱装载问 题，而且解决了之前常用传统启发式方法来求解的多箱装载问题，最后通过编程实现和 算例测试对算法的正确性和有效性进行了分析。本文的组织结构如下： 第一章介绍了课题研究的背景，所属的领域，并详述了课题的常用研究方法和国内 外的研究动态。 第二章详细介绍了一种近年来日益受到关注的新型现代启发式算法禁忌搜索 算法( t s ) 。描述t s 基本原理、关键搜索技术的同时，对其收敛性理论给出证昵 第三章将t s 应用到求解c l p 中，给出了求解的主要流程及数据结构形式，并结合 c l p 问题的求解，说明了t s 关键技术的具体实现方法等。 第四章主要研究了集装箱装入结果的显示方法，包括数据形式和图形形式，从不同 角度方便用户观察、使用。 第五章采用国际标准数据集对应用本文算法实现的三维集装箱装载系统进行了测 试，将取得的结果与同行测试数据进行比较，并分析了算法优点与不足产生的原因。 第六章对本文工作进行总结，并结合作者实际工作和相关文献对课题的发展作以展 望。 9 基于禁忌搜索算法的集装箱装载问题研究 2 禁忌搜索算法 2 1 背景及原理 智能优化算法是伴随着计算机技术的发展和实际问题对优化算法的要求而产生的。 实际问题要求优化算法对目标函数、约束函数的表达形式应更加宽松，这样优化算法才 有更加广泛的应用领域，传统优化算法连续可导的要求有点过于严格。另外，实际问题 往往要求优化算法要有一定的智能性和模糊性，这对优化算法要求较高，但在实际问题 中这种不确定性是大量存在的，实际问题的这种要求是智能优化算法产生的前提。计算 机技术的高速发展，计算能力的大幅提高，内存容量的不断加大，是智能优化算法产生 的必要条件，它为智能优化算法的运算提供了可能性。在这种背景下，七八十年代提出 了几个有效的智能优化算法，其中包括遗传算法( g a ) 、禁忌搜索算法( t s ) 和模拟 退火算法( s a ) 。t s 与g a 和s a 最大的不同在于，后两者不具有记忆能力。 禁忌搜索算法( t s ) 的思想最早由g l o v e r 提出，它是对局部邻域搜索的一种扩展， 是一种全局迭代寻优算法，是对人类智能过程的一种模拟。禁忌( t a b u 或者t a b o o ) 表 示禁止的意思，来源于汤加语，居住在汤加群岛的土著人用这个词来表示神圣不可触犯 的东西。t s 通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过 特赦准则来赦免一些被禁忌的优良状态，进而保证多样化的有效搜索以最终实现全局优 化。t s 也是人工智能的一种体现，其最重要的思想是标记对应的己搜索到的局部最优 解对象，并在进一步的迭代搜索中尽量避开这些对象，而不是绝对禁止循环，从而保证 对解空间中的不同区域进行有效搜索。 2 2 禁忌搜索技术 考虑一个组合优化问题： ( 尸) ：m i n 咖i z ec o ) s u b j e c t t o x e x 互e 这里，e 是满足某些基本约束的可行解空间，x 是满足应用问题规定的约束条件的 可行解集。目标函数c 是将一个代价值c “) 与一个解x 对应起来的线性或非线性映射。 问题( 尸) 也可以描述为：对所有的x 卫找到一个全局最优解x + 兄使得c “勺c 0 ) 。 0 沈阳工业大学硕士学位论文 许多用于解决问题( p ) 的优化方法都是从一个初始解开始重复地在当前解的邻域中 构建新解的迭代过程，禁忌搜索也不例外。算法不断地生成邻域解，直到满足某个停止 准则为止。从图论的观点来看，一个迭代求解方法可以看成在一个由邻域结构生成的图 g i ：- ( v , ) 中的移动。这里，y e 。对每一个x e x , 都有一个相应的邻域丘当且 仅当x e n ( x 3 时，弧a r c ( x ；x 1 e 彳存在。每一个从工斗x e n ( x ) 的步骤叫做一个移动。 禁忌搜索是一种人工智能算法，是局部搜索算法的扩展。下面按照禁忌对象、禁忌 长度、候选解集的构成、评价函数的构造、特赦准则、记忆频率信息和终止规则的顺序 分别给予介绍i 2 2 1 禁忌对象、禁忌长度与候选解集 禁忌表中的两个主要指标是禁忌对象和禁忌长度。顾名思义，禁忌对象指的是禁忌 表中被禁的那些元素。因此，首先需要了解状态是怎样变化的。我们将状态的变化分为 解的简单变化、解向量分量的变化和目标值的变化三种情况。在这三种变化的基础上， 讨论禁忌对象，本小节同时介绍禁忌长度和候选解集的经验方法。 ( 1 ) 解的简单变化。这种变化最为简单，假设x , y e d ，其中d 为优化问题的定义域， 则简单解变化为： x y 即从一个解变化到另外一个解。 ( 2 ) 向量分量的变化这种变化考虑的更为细致，以解向量的每一个分量为变化的 最基本因素，仅以( a b c d e ) 变化到c b d e ) 为例，它的变化实际是由b 和c 的对换引起 的。但口和c 的对换可以引起更多解的简单变化，如 似日- - - h “c b d e ) ( a b d c e ) - - h 似c d b e ) 似c b e d ) - - h 似b c e d ) 等。设原有的解向量为( 毛，t ，五+ ，) ，用数学表达式来描述向量分量的最基本变 化为： ( 一，一- l t ，+ l ，) ( x i ，x j 十只，x ，一，吒) 即只有第i 个分量发生变化。向量的分量变化包含多个分量发生变化的情形。 基于禁忌搜索算法的集装箱装载问题研究 ( 3 ) 目标值变化。在优化问题的求解过程中，我们非常关心目标值是否发生变化， 是否接近最优目标值。这就产生一种观察状态变化的方式：观察目标值或评价值的变化。 就犹如等高线的道理，把处在同一等高线的解视为相同。这种变化是考察： 日( 口) = x d i 厂( 石) = 口 其中厂( 工) 为目标函数，它的表面是两个目标值的变化，即从a 专b ，但隐含着两个 解集合的各种变化v x h ( a ) - - j ，h ( b ) 的可能。 以上三种状态变化的情形，第一种变化比较单一，而第二种和第三种变化则包含着 多个解变化的可能。因而在选择禁忌对象时，可以根据实际问题采用适当的变化。 ( 4 ) 禁忌对象的选取。禁忌对象就可以是上面状态变化三种形式中的任何一种。第 一种情况考虑解为简单变化。当解从x 一_ ，时，y 可能是局部最优解，为了避开局部最 优解，禁忌y 这个解再度出现。禁忌的规则是：当y 的邻域中有比它更优的点时，则选 择更优的解；当j ，为的局部最优时，不再选y ，而选择比y 较差的解。第二种情况 考虑向量分量的变化，禁忌的原则是：对一对元素x 和y 的禁忌也包含两个元素的对换， 即z 与y 的交换。上一步已经对换的两个元素不能再对换回去，以免还原到原有的解。 第三种情况考虑目标值变化，当一个目标值受禁之后，包含此目标值的所有状态都受禁。 实际应用中，应根据具体问题采用一种方法。解的简单变化比解的分量变化和目标 值变化的受禁范围要小，这可能造成计算时间的增加，但它也给予了较大的搜索范围。 解分量的变化和目标值变化的禁忌范围要大，这减少了计算时间，可能引发的问题是禁 忌范围太大以至于使搜索陷在局部最优点。 ( 5 ) 禁忌长度的确定。禁忌长度是被禁忌对象不允许被选取的迭代次数，一般是给 被禁对象x 一个数( 禁忌长度) ，要求对象x 在t 步迭代内被禁，在禁忌表中采用t a b u ( x ) = t 记忆，每迭代一步，该项指标做运算t a b u ( x ) = t - i ，直到t a b u ( x ) = o 时解禁。于是，我们可 将所有元素分成两类，被禁元素和自由元素。有关禁忌长度，的选取，可归纳为下面几 种情况： 1 ) t 为常数，如t = 2 0 ，- ，其中聆为邻居的个数，这种规则容易在算法中实现。 沈阳工业大学硕士学位论文 2 ) t i t - ，f 】，此时t 是可以变化的数，它的变化是依据被禁对象的目标值和邻 域的结构，此时f m i 。，r 雌是确定的。确定，m 如，矗。的常用方法是根据问题的规模l 限定变化区间k 亍，亍j o 口 p d 时，虽说从x 胁到x n o w 的变