（信号与信息处理专业论文）web模式下三维装箱问题求解方法研究.pdf

w e b 模式下三维装箱问题求解方法研究 捅要 集装箱装配货物方案是将具有一定体积、重量、价值、数量的不同种类不同 数量的货物合理地放置在一个具有一定体积和载重量限制要求的集装箱空间内 的过程，装箱问题广泛存在于工业领域，在实际应用中，装箱问题的解决效果影 响最直接和显著的领域是物流运输业。随着我国市场经济的发展，物流活动越来 越显示出它的重要性，装箱问题作为物流配送过程中的一个关键性技术，对提高 配送业务的自动化水平、提高货物装载的优化程度、提高配送业务的工作效率和 规范业务流程都有重要的意义。实际求解中，看似简单的装配问题也往往是n p 完全问题，即在有限时间内找不到问题最优解。 论文首先指出课题产生的时代背景，然后对装箱问题的研究现状进行了分 析，阐述了本文的研究内容及其意义。接着着重对三维装箱问题的实际需求进行 了分析，指出w e b 模式的装载是解决实际问题的必然发展趋势，接着对三维装 箱问题的常用算法进行分析，从问题的启发式方法和进化算法角度研究现有解法 的思路，并指出其针对w e b 模式下装载的优点与缺点。 在此基础上，针对实际装载中单种类型货物数量一般较多、使用现有启发式 算法空间利用率较低和在w e b 模式下使用以遗传算法为代表的进化算法存在装 载速度较慢的问题，从优化搜索策略方面入手，引入免疫克隆选择算法( i c s a ) ， 利用克隆扩增、克隆选择算子完成种群进化，并结合基于六空间分解的启发式策 略对i c s a 算法加以改进，使两者相辅相成，构造了混合克隆选择算法求解w e b 模式下的三维装载问题。 免疫克隆选择算法作为模仿自然免疫系统功能的一种智能方法，具有记忆和 自我调节的特性，在求解优化问题中显示了优越的性能。鉴于目前免疫克隆选择 算法在图像处理、组合优化、控制和故障诊断等领域的成功经验，将其与六空间 启发式算法相结合构造混合克隆选择算法，以保证快速获得全局最优解解。通过 对实际装箱数据的算例分析和与每种货物数量较多的现有结果比较，表明本文算 法处理复杂集装箱单箱装载问题是有效的，具有较高的空间利用率和计算效率。 根据本文提出的混合克隆选择算法，开发了电子配载系统。该软件具有能够 满足实际集装箱装载中的多约束条件、升级和使用灵活方便的优点，可真正用于 物流企业的配载实践。论文介绍了系统功能和数据流程，并简要说明了操作过程。 论文最后对研究成果进行总结，分析了混合克隆选择算法及电子配载系统的 成功与不足，并对今后系统的深入研究进行展望，指出未来的一些研究方向。 关键词：三维装箱；w e b 模式；启发式算法；遗传算法：混合克隆选择算法 n ih er e s e a r c h0 ta p p r o a c h e st 0s 0ivin gt h e r e - dim e r l sio n 一 r c o n t ain e rp a c kin gpr o bie mo fw e bm o d e a b s t r a c t t h es c h e m eo ft h ec o n t a i n e ra s s e m b l i n gg o o d si sap r o c e s st h a tp u td i f f e r e n tk i n d s a n dq u a n t i t yo fg o o d s ，w h i c hh a v ec e r t a i nv o l u m e ，w e i g h t ，v a l u ea n dn u m b e r i nt h e s p a c eo fc o n t a i n e rh a v i n gc e r t a i nv o l u m ea n dl o a d i n gc a p a c i t yr e s t r a i n t c o n t a i n e r p a c k i n gp r o b l e me x i s t si ni n d u s t r ya r e a sw i d e l y , e s p e c i a l l yi nl o g i s t i c sa r e a w i t ht h e d e v e l o p m e n to ft h em a r k e t 。e c o n o m i c si nc h i n a , t h el o g i s t i c sr e l a t e da c t i v i t i e sb e c o m e m o r ea n dm o r ei m p o r t a n t ，a sa k e yt e c h n o l o g y , c o n t a i n e rp a c k i n gp r o b l e mi sv e r y i m p o r t a n to ni m p r o v i n gt h ee f f i c i e n c yo fd i s t r i b u t i n gw o r k s ，o p t i m i z i n gt h ec a r g o s l o a d i n gp a t t e r na n ds t a n d a r d i z i n gt h eb u s i n e s sp r o c e s s m a n yp a c k i n gq u e s t i o n s s e e m i n g l ys i m p l ea r eo f t e nn p - c o m p l e t ep r o b l e m ，n a m e l y , w ec a n tf i n dt h e o p t i m i z e ds o l u t i o nw i t h i nl i m i t e dt i m e t h i sd i s s e r t a t i o nf i r s tp o i n t so u tt h ee ab a c k g r o u n dt h a tt h es u b j e c tp r o d u c e s ，t h e n a n a l y s e st h ec u r r e n ts t u d ys i t u a t i o no fc o n t a i n e rp a c k i n gp r o b l e m ，a n de x p o u n d s r e s e a r c hc o n t e n t sa n di t ss i g n i f i c a n c e f o l l o w i n ge m p h a s i z e so na n a l y z i n gt h ea c t u a l d e m a n d so ft h r e e d i m e n s i o n a lc o n t a i n e rp r o b l e m ，p o i n t so u tc o n t a i n e rp a c k i n gi nw e b m o d ei sd e v e l o p i n gt os o l v ea c t u a lp r o b l e m ，t h e na n a l y s e st h ec o m m o na l g o r i t h m sf o r t h r e ed i m e n s i o nb i np a c k i n gp r o b l e m ，t h ee x i s t i n gs o l u t i o n sa r es t u d i e di nt h et e r m so f h e u r i s t i cm e t h o da n de v o l u t i o n a l a l g o r i t h m , p i o n t s o u tt h e i ra d v a n t a g ea n d d i s a d v a n g t a g ef o rc o n t a i n e rp a c k i n gi nw e bm o d e o nt h i sb a s i s ，d i r e c t i n ga g a i n s tt h ef a c tt h a t ，t h en u m b e ro fas i n g l et y p eo fg o o d si s a l w a y sm o r et h a no n e o rs o m e t i m e sl a r g ea n dt h e r ei sl o ws p a c eu t i l i z a t i o nr a t i ou s i n g e x i s t i n gh e u r i s t i cm e t h o da n ds l o w f o o t e do fc o n t a i n e rp a c k i n gi nw e bm o d eu s i n g g e n e t i ca l g o r i t h m ，f r o mo ni m p r o v i n gs e a r c h i n ga l g o r i t h m ，w ei n t r o d u c ei m m u n e d o n a ls e l e c t i o na l g o r i t h m ( i c s a ) ，u s i n gc l o n a la m p l i f y 、d o n a ls e l e c t i o nt oc o m p l e t e s t o c k se v o l u t i o n ，a n dc o m b i n i n gs i xs p a c eh e u r i s t i ca l g o r i t h mt oi m p r o v ec s a , m a k i n gt h et w oc o m p l e m e n te a c ho t h e ra n db e n e f i te a c ho t h e r , a n dp u tf o r w a r d h y b r i dc l o n a ls e l e c t i o na l g o r i t h mt os o l v et h e r ed i m e n s i o nc o n t a i n e rl o a d i n go fw e b m o d e i m m u n ec l o n a ls e l e c t i o na l g o r i t h mi sa l li n t e l l i g e n ta l g o r i t h mt h a ts i m u l a t e sn a t u r a l i m l n u n es y s t e m ，i t sc h a r a c t e r i s t i ci n c l u d i n gm e m o r ya n dc h a r a c t e r i s t i ci t s e f fi s s h o w e ni nt h es o l u t i n gp r o c e s s i ti st h ef a c t t h a tt h ei m m u n ec l o n a ls e l e c t i o n a l g o r i t h mg e t s t h es u c c e s si n p i c t u r ed i s p o s e ，a s s e m b l eo p t i m i z e ，c o n t r o l a n d e x c e p t i o nd i a g n o s e sa n ds oo n ，w ec o m b i n e si ta n ds i xs p a c eh e u r i s t i cm e t h o di n t o h y b r i dc l o n a ls e l e c t i o na l g o r i t h m ，i no r d e rt og e tg l o b a lo p t i m a ls o l u t i o n t h r o u g h a n a l y z i n gt h ea c t u a lp a c k i n gd a t aa n dc o m p a r i n gw i t he x i s t i n gr e s u l t sf r o mh e u r i s t i c m e t h o da n dh y b r i dg e n e t i ca l g o r i t h m ，i ti si n d i c a t e dt h a ti t se f f e c t i v eu s i n gt h e a l g o r i t h mp u tf o r w a r di nt h ed i s s e r t a t i o nt od e a l w i t hc o m p l e xc o n t a i n e rl o a d i n g p r o b l e m ，a n dl o a d i n ge f f i c i e n c ya n ds p a c eu t i l i z a t i o nr a t i oi sh i 【g h o nt h eb a s i so ft h eh y b r i dc l o n es e l e c t i o na l g o r i t h mp u tf o r w a r di tt h i sd i s s e r t a t i o n ， ae l e c t r o n i cl o a d i n gs y s t e mi sd e v e l o p e d t h i ss o f t w a r ec a ns a t i s f ym u t i - c o n s t r a i n t q u a l i f i c a t i o n s ，a n di sf l e x i b l ei nu s a g ea n dc o n v e n i e n tt o i n s t a l l i tc a nb eu s e db y l o g i s t i c se n t e r p r i s e si np r a c t i c eo fl o a d i n g a tl a s t ，t h er e s e a r c hr e s u l t sa l es u m m a r i z e d ，t h es u c c e s s f u la n dd e f i c i e n tp l a c eo f t h eh y b r i dc l o n es e l e c t i o na l g o r i t h mb a s e do ns i xp a r t i t i o n i n gs p a c ea n de l e c t r o n i c l o a d i n gs y s t e mi sa n a l y z e d ，a n dp r o s p e c t st ot h ef u r t h e rr e s e a r c hi nt h i sf i e l da n d s o m er e s e a r c hd i r e c t i o ni nt h ef u t u r ei sp o i n t e do u t k e yw o r d s ：t h r e ed i m e n s i o nb i np a c k i n g ；w e bm o d e ；h e u r i s t i cm e t h o d ；g e n e t i c a l g o r i t h m ；h y b r i dc l o n a ls e l e c t i o na l g o r i t h m i v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含未获得 ( 洼! 翅遗直墓丝益蔓挂别虚盟的：奎拦亘窒2 或其他教育机构的学位或证书 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名： 五佛 签字日期：砧年月知日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络 向社会公众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：互乍新擀丁伽 签字日期：加矽年r 月b 日签字日期：砌扩年r 月害。日 w e b 模式下三维装箱问题求解方法研究 1 1 问题产生的时代背景 1 绪论 随着我国市场经济的发展，全国的物流业面临前所未有的发展机遇，物流在 经济发展中起着越来越重要的作用，2 0 0 1 年中国加入w t o 后，对物流的需求更 是日益旺盛起来，物流相关技术的应用和发展受到越来越多的重视，物流规模和 物流成本也随之不断上升，而物流是西方经济学家和企业界公认的继劳动力、自 然资源之后的“第三利润源泉 、“企业发展的战略手段 、“降低成本的宝库 ， 因此如何提高物流效率、降低物流成本就成为一个很重要而且迫切的实际问题。 在物流公司的各项运营成本中，集装箱管理成本已成为最重要的成本之一。因此， 如何最大限度的提高集装箱管理水平，降低集装箱管理成本，有效的统筹物流企 业的仓储、运输问题，及时控制和反馈各地的配载信息，优化集装箱装载问题， 提高经济效益，已成为当务之急。 集装箱装载问题是将不同尺寸的物品摆放入有一定容量的容器中，以获得某 种较好空间利用效率，该问题广泛存在于许多领域，如运输行业的集装箱货物装 载、飞机装舱、码头装货、列车装箱，机械行业中箱体和钟表等布局，航空、航 天工业中导弹仓的布局，以及建筑、电子、造船业、纺织业等。作者在某运输代 理部门了解到，集装箱装载分为两个部分：第一部分，积累货物，并计算到达某 地的货物体积，当体积达到一定数量时，根据各地的货物积累情况，整理出一份 待装货物清单( 包括尺寸、重量、体积、特殊说明等) 。第二部分，将清单上货物 装入集装箱，若有空隙，则填充某些隔离材料，或用金属丝固定。实际的装载中 货物和箱体会受到一些条件限制，常用的约束条件见文献n 1 ，现在还大量存在的 人工估计装填方法，往往在确保全部装下的前提下，需要保留足够空间，浪费了 宝贵的货运空间，增加了运输成本。还常因为货物清单上货物尺寸或数量不准以 及又需要装入额外的货物而需要经常反复重装，最后也可能会出现该装的没有装 入的情况，装载结果不尽人意。这就要求计算机辅助制定可行的装载计划，虚拟 出装箱过程，避免手工重装，为现场装卸提供决策支持。 集装箱运输是世界上广泛使用的手段之一。集装箱码头是国际运输链和物流 链的重要环节，通过它各种货物才能顺畅地流通。装箱问题作为物流配送过程中 1 w e b 模式下三维装箱问题求解方法研究 的一个关键性技术，对提高配送业务的自动化水平、提高货物装载的优化程度、 提高配送业务的工作效率和规范业务流程都有重要的意义。许多看似简单的装配 问题是多约束多目标的组合优化问题，属于n p 完全问题，即在有限时间内找不到 问题最优解。提高散集装箱配载的质量、效率和可靠性，节约运输时间，提高物 流效率，从而提高企业的盈利能力，获得可观的经济和社会效益，对物流行业的 发展意义重大。当前，有关集装箱配载系统的研究和设计主要集中在用计算机解 决配载计算问题，到目前为止，许多学者对装箱问题已经进行了大量的研究，发 表了各种解决该问题的方法。在装箱问题的算法研究中，一维装箱算法已相对成 熟，二维装箱问题研究的也较多，三维装箱问题由于其复杂性和难度大，因此研 究相应较少，并且三维装箱主要是对针对单个地点的集装箱装入问题研究偏多， 建立的系统也大多是单机版的，在统筹兼顾各个零散的仓储、运输地的配载信息 的情况下研究三维装箱问题的文献是少之又少，学者们仍在努力寻找更好的解决 方法。 针对上述原因，本文选择w e b 模式下三维装箱问题求解方法这一课题，以解 决当前复杂集装箱装载环节面临的问题。旨在寻求面向现代物流企业实用的装载 模式和优化算法，建立现代物流配载系统，以期达到对现代集装箱装载业务有一 个实用、有效的技术解决方案目的。 1 2 装箱问题的研究现状 1 2 1 装箱问题的分类 从2 0 世纪7 0 年代初开始，装箱问题就引起了广泛的探讨和研究 2 1 。装箱问题 可以追溯至u 1 8 3 1 年高斯( g u a s s ) 开始研究布局问题，因为装箱问题和布局问题本 质上是一样的，到现在已有百余年的历史，在文献上始见于1 9 3 0 年k n a t o r o v i c h 的俄文文章。集装箱装载可以从不同的角度进行分类研究： 按照装箱物体所属装箱空间可把装箱问题分为一维装箱问题、二维装箱问题 和三维装箱问题，其中三维装箱问题可以看作是一维、二维装箱问题的一个泛化。 按照装箱物体的形状可以把装箱问题分为规则物体的装箱和不规则物体的装箱 规则物体是指具有规则外形的物体，不规则物体是指具有任意几何形状的物体。 2 w e b 模式下三维装箱问题求解方法研究 按照装箱物体达到情况可把装箱问题分为在线装箱问题和离线装箱问题，在线最 流行的解决三维装箱方法之一是s h e l fm o t h e d 3 1 。该方法也是通过聚组相近尺寸 物品来提高装载利用率的，离线的装箱问题的常用算法有分支定界方法【4 】、遗传 算法【5 _ 】和模拟退火方法【7 】等。按照装载过程是否有惩罚值装箱问题可分为带拒 绝装箱问题和不带拒绝装箱问题，如果在装载过程中待装载物品没有被放在箱中 而产生惩罚，这种情况下的装箱问题是带拒绝装箱问题，反之为不带拒绝装箱问 题【8 1 。 1 2 2 装箱问题的国内外研究方法 装箱问题是一个组合优化问题，在理论上属n p h a r d 问题。由于目前n p 完全 问题不存在有效时间内求得精确解的算法，装箱问题的求解极为困难的，在2 6 世纪7 0 8 0 年代陆续提出的装箱算法都是各种近似算法，如下次适应、首次适应、 降序下次适应和调和算法【9 】等。近几年装箱问题的研究方法主要有线性规划法、 动态规划法、传统启发式方法及现代启发式方法( 如模拟退火算法、禁忌搜索算 法、遗传算法) 等等。 ( 1 ) 线性规划法和动态规划法的基本思想是把每装入一件物品作为一个阶 段，把装货问题化为动态规划问题，动态划分车厢空间，进行优化计算，在此基 础上提高车辆装载的空间利用率。它们存在的主要问题是计算时间和空间代价随 问题规模成指数增长，只适合于小规模的排料问题。 ( 2 ) 传统启发式方法( h e u r i s t i c m 9 0 r i t h m ) 的基本思想是依靠人的先验知识 确定每一步的排放策略，从而得到目标的优解。传统启发式方法的一般步骤是从 与待解问题有关的信息中得到评价函数来确定搜索方向，使过程中的每个状态向 目标状态方向前进，其中状态( 已装入、未装入和剩余空间) 的表示是个共性问题， 而装入策略和评价指标随着具体问题的变化而变化。求解装箱问题的传统启发式 方法多是按某种指标( 如面积、边长、体积) 对矩形货物排序，优先在剩余空间放 置大的货物。采用传统启发式算法的好处在于它相比遗传算法等现代启发式算法 减少了盲目性，但是它得出解的质量往往不是很高 1 ) 国内使用传统启发式方法求解装箱问题的研究主要有姜义东提出基于空 间分解的启发式算法【1 0 1 ，采用三叉树的数据结构来处理剩余空间，使用深度优 w e b 模式下三维装箱问题求解方法研究 先的处理方法处理三叉树得出布局结果。虽然这样划分剩余空间会降低问题的复 杂性，但是划分后剩余空间比较“零碎 。樊建华【1 1 】提出采取先放置边长大的物 体的策略，同时考虑了剩余空间的结合问题。刘嘉敏，马广现的算法【1 2 】针对以 上两种算法的不足进行了改善。上海交通大学的阎威武等人提出了一种基于层的 启发式算法【1 3 1 。该算法考虑了方向、重量、优先权、货物的配置位置等约束条 件，并且采用三空间分割、平均高度装载、货物合并、空间合并等策略，具有一 定的有效性。但是该算法的各种策略的参数过于依赖个人经验，存在“组合爆炸 的问题 2 ) 国外使用传统启发式方法求解装箱问题的研究 g e o r g ea n dr o b i n s o n 建立沿着集装箱宽度的层，尽量使某一层的外表面平 整，并且结合剩余空间以提高空间利用率【1 4 1 。然而当小物体的数量多，大物体 的数量少时空间利用率较低。b i s c h o f fa n dd o w s l a n d 也是基于通过沿着集装箱宽 度建立层来填充集装箱的【1 5 l 。它旨在最大化横截面( 集装箱的宽度和高度组成的 矩形) 的面积利用率，层的深度选择对空间利用率的影响很大。将三维问题降为 二维问题来解决，简化了剩余空间的描述。b i s e h o f f a n dm a r r i o t t 通过6 个等级规 则【1 6 1 ，提出了1 4 种集装箱装入的启发式方法，得出集装箱装入结果的优劣在一 定程度上依赖于待装物体种类多少的结论。在此基础上d a v i dp i s i n g e r 提出了基 于墙壁支撑的集装箱装载启发式方法f 1 刀，对于较大规模问题有更优的解。 m i c h a e le l e y 提出了建立相同方向物体的同质块算法【l 踟，首先提出了一个贪婪启 发式算法，然后提出搜索算法来改进贪婪启发式算法的解，这样使集装箱中的物 体比较稳定，装卸方便，放置容易。 ( 3 ) 模拟退火法( s i m u l a t e d a l g o r i t h m ，简称s a ) 是模拟热力学中经典粒子 系统的降温过程来求解规划问题的极值。当孤立粒子系统的温度以足够慢的速度 下降时，系统近似处于热力学平衡状态，最后系统将达到本身的能量最低状态， 即基态，这相当于能量函数的全局极小值点。由于模拟退火法能够有效地解决大 规模的组合优化问题，且对规划问题的要求很少，因此引起研究人员的极大兴趣。 当系统温度足够低时，就认为达到了全局最优状态。按照热力学分子运动理论， 粒子作无规则运动时具有的能量带有随机性，温度较高时，系统的内能较大，但 是对某个粒子而言，它所具有的能量可能较小。因此算法要记录整个退火过程中 4 w e b 模式下三维装箱问题求解方法研究 能量较小的点【1 9 1 。国内使用传统模拟退火法求解装箱问题的研究主要有天津大 学王金敏等对三维布局问题的求解【2 0 】。算法中给出了目标函数、约束条件、求 解的初始温度及退火策略。算法没有明确给出和其它算法的比较测试结果。中国 海洋大学的江娜【2 1 】等提出的将模拟退火方法和遗传算法结合解决三维装箱问 题，算法的收敛速度较慢。 ( 4 ) 遗传算法( 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 ) 在该算法中，由于群体中每个个体的搜索是独立进行的，因此算法具有 内在的并行性。这些优点使得g a 能处理许多传统优化算法无法解决的复杂问题， 但g a ：i ! e 许多问题的早熟( 即过早收敛于局部最优解而非全局最优解) 现象始终未 得到很好的解决。 中国科技大学曹光彬等先后给出了采用遗传算法和免疫遗传算法【捌求解装 箱问题的算法。免疫遗传算法是对标准遗传算法的改进。两种算法都采用二进制 编码方式，采用轮盘赌法选择抗体，难以保证解的优良性。另外，该算法没有涉 及如何保持由下而上的每层中小长方体高度一致的问题。从该算法的结果来看， 小长方体会出现悬空放置或倾斜放置的问题。中国海洋大学的丁香乾【矧、北京 交通大学的何大勇采用遗传算法求解复杂集装箱装载问题，在集装箱数目较少时 有不错的表现，但是当小箱子数目很大时，两篇文献中采用的编码方法会造成解 空间急速膨胀，搜索效率降低。 b o r t f e l d t 和g e h r m g 采用遗传算法【2 4 1 和禁忌搜索算、法【2 5 1 求解装箱问题得出基 于“层”思想的遗传算法更适于求解“强异质类”问题，而基于“同质块 的 5 w e b 模式下三维装箱问题求解方法研究 禁忌搜索算法更适于求解“弱异质类 问题的结论。但两篇文献中都没有提到 对多箱问题的求解 ( 5 ) 禁忌搜索( t a b us e a r c h ，简称t s ) 是一种现代启发式( m e t a - h e u r i s t i c ) 搜 索算法【2 6 刀】。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 的解， 或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。禁忌搜索在求解 一些困难复杂的问题时表现出极好的寻优能力，近年来被应用到优化问题的诸多 领域，有广泛的前景。 1 2 3 小结 从目前文献上看，针对这种典型的组合优化问题，遗传算法、启发式算法等 优化技术被广泛利用，并且获得了不错的装箱效果。然而，市场调查显示文献中 的各种方法难以在物流等相关企业中广泛使用，究其原因是这些算法忽略了一个 重要的实用性因素：三维装箱问题存在的企业仓储地点、运输地点一般比较零散， 装载往往需要全盘考虑问题，这就需要及时控制和反馈各地的配载信息，并且必 须考虑维护及升级简易性，因此，基于w e b 模式的装箱优化是未来这类问题能 走向实际企业营运的一个必然发展趋势。w e b 并发访问模式下，算法要考虑所 能达到的装箱效率，也得考虑算法运算的时间消耗。这就对装箱算法提出了更高 的要求。 1 3 本文研究的主要内容 本文根据当前物流行业对解决复杂集装箱装载问题的需求，在充分了解各类 装箱问题的基础上，从应用的角度对求解复杂集装箱装载问题的算法作了认真分 6 w e b 模式下三维装箱问题求解方法研究 析和研究，针对w e b 模式装箱实际需求，着重研究影响装箱进化算法速度的关 键因素，为避免遗传算法交叉算子的存在带来的无效模式干扰，引入免疫克隆选 ； 择算法，并结合基于六空间分解的启发式算法进一步构造了混合克隆选择算法， 提出利用混合克隆选择算法精简运算过程，以期在获得高装箱效率的同时提高装 箱运算速度。通过对算法的性能分析得出结论。 各章的内容安排如下： 第一章首先指出课题产生的时代背景，然后对装箱问题的国内外研究现状进 行分析，在此基础上，阐述了本文的研究内容及其意义。 第二章着重对w e b 模式下三维装箱问题的求解方法进行分析，详细分析了 混合遗传算法，并指出现有成果的优点与缺点。 第三章构造了混合克隆选择算法，给出了算法流程。 第四章通过对第三章的算例分析与比较，对其性能进行了合理评价。 第五章介绍基于混合克隆选择算法构造的电子配载系统。 第六章总结了本文的工作并展望了进一步的研究方向。 7 w e b 模式下三维装箱问题求解方法研究 2w e b 模式下三维装箱问题求解方法分析 2 1 w e b 模式下的装箱问题 在实际应用中集装箱装载还存在着一些问题，一是各物流企业仓储地点比较 零散，合理的安排货物装箱需要统筹兼顾各仓库的货物累积情况，这就要求实现 各地配载信息反馈的快速便捷，及时控制配载过程；二是装箱业务处理的数据类 型以业务表单为主，文件图片等大数据量类型的操作数据不多，且没有对这些数 据进行修改编辑的复杂要求；三是操作装箱业务的人员不是1 1 r 技术的专业人员， 客户的相关知识也不够专业，他们要求操作软件简单、快捷，系统易于维护。随 着计算机的迅速普及，网络也几乎覆盖了千家万户，集装箱装载信息完全可以通 过i n t e r n e t 在线来及时传输，通过w e b 并发访问模式实现信息的快速反馈和及时 控制，而且使用浏览器h t m l 为前端界面，基本可以满足页面操作和数据稳定 性的要求，操作也比较简单，采用以b s 架构为主的技术架构，在一些客户端系 统故障上比较好判断责任和原因，减轻维护的工作量。如客户端机器操作系统或 者网络的问题很容易判断与客户沟通，一般情况下不需要进行现场维护。基于以 上情况，w e b 模式下的装载优化系统是实际企业运营的一种有效解决方法，而由 于网络传输特有的时延特性，装载优化算法不仅要箱体的空间利用率要高，算法 的运算速度也要快，这就要求算法能够快速收敛于全局较优解。 2 1 1 问题的分类 目前对三维装箱问题的研究，多集中在多种物品问题上。一方面是因为多数 实际应用中，都涉及到种类繁多的物品；另一方面是因为在解决单一种类的单箱 三维问题时，二维问题的算法也对其提供了思路，如果待装物品完全相同，那么 在一个平面上求出面积利用率最大的布局模式后，只要在高度方向上扩展该布局 模式即可。目前更多地是按照使用集装箱数量来划分研究的问题，即单集装箱问 题和多集装箱问题。 ( 1 ) 单个集装箱装载情况 对于此类情况研究的文献比较多，多种物品单个集装箱三维装箱问题定义 8 w e b 模式下三维装箱问题求解方法研究 为：指给定1 个宽度为w ，长为l ，高为h 的矩形集装箱a 和1 1 种矩形物品， 第i 种物品的属性包括三维尺寸如m ，h ，重量d ；和其他属性，同种物品有m ；个 ( i = 1 ，2 ，n ) ，同种物品所包括的所有物品属性相同。求这些物品在a 箱内的布 局方案( 可以有部分物品剩余) ，使在满足一定约束的情况下，放入物品的总价 值最大。总价值可以是总体积、总重量或运费等指标。一般情况下，多以集装箱 的空间利用率最大为目标。单集装箱装载进一步又可分为相同体积货物和不同体 积货物的装载情形。对于相同体积货物的装载，s e u u i 和h u i ( 1 9 8 8 ) 等给出了启发 式装载方法；s c h e i t h u a e r ( 1 9 9 2 ) 给出了基于动态规划前向策略的近似算法；宫佩 珊( 1 9 9 7 ) 针对单一产品且产品无摆放限制的情况提出了一种递归方法。对于体积 不同货物的装配情形，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 ) 。大多数方法假定装载对象为 弱差异情形，从概念上讲，弱差异情形下装箱的方法也适合于强差异情形，但根 据i s c h o f f ( 1 9 9 0 ) 分析，方法的性能取决于货物的种类和数量，同样数量达几百件 的货物，如果把针对十几种体积规格的装载方法用来解决只有两三种体积规格的 货物情况，效果并不见得理想。用遗传算法可以很好地解决强差异和弱差异货物 的装载问题。 ( 2 ) 多集装箱装载情况 多种物品多个集装箱三维装箱问题是指给定若干个尺寸、限重等属性可能相 同，也可能不同的箱体和n 种矩形物品，第i 种物品三维尺寸分别为z ；，m ，h ；，以 及重量d ；和其他属性，同种物品有朋；个( i = 1 ，2 ，n ) ，某种物品所包括的所有 物品属性相同。求这些物品在各个箱体内的布局方案，使在装完所有物品的情况 下，使用的集装箱数量最少。当可使用的箱体完全一样时，则该问题的目标就是 最小化所用集装箱的数量。如果可使用的箱体不一样，即有多个种类的集装箱， 而且不同种类的箱体有不同的成本时，更加合适的目标应是最优化地选择集装 箱，使总成本最小。同时，尽量使物品在所有箱体中分布均匀。c h e n ( 1 9 9 5 ) 针对 集装箱一般装载问题( 用一定数量的集装箱装载给定的货物) 给出了0 1 整数线性 规划模型，考虑了货物和集装箱的不同规格、货物的方向、放置因素，并分析了 9 w e b 模式下三维装箱问题求解方法研究 一些特殊情况如单个集装箱装载、载重分布等。i v a n c c i 等人( 1 9 8 9 ) 给出了一种基 于整数规划的三维装箱启发式算法，对于每个集装箱依次装载直至所有货物装完 为止，但是这种方法仅适用于同种规格的集装箱装载，而且由于变量以及约束条 件随货物数量增加而迅速增多，从而使问题难于求解。b i s h c o f f 和r a t c l i f f ( 1 9 9 5 ) 将多托盘装载情况拓展到多集装箱装载问题。e l e y 根据b i s h c o f f 和r a t c l i f f 的实 验数据库中取3 5 0 个例子进行实验，最后表明串行方法可以得到比较好的解，但 运算时间很长。值得注意的是这种方法对强差异货物情形都能得到很好的解。对 于不同规格的多集装箱装载，需要考虑不同规格的集装箱的运输成本，其优化目 标为所用成本最小。 2 1 2 问题描述 集装箱装箱问题以集装箱数量的有限和无限来划分，可以分为两类： ( 1 ) 集装箱数量无限，货物必须全部装完，要使所有的集装箱数量最少； ( 2 ) 集装 箱数量有限，货物数量超过了集装箱的装载能力，要求被装载货物的总体积达到 最大，使空间利用率最高。实际应用中第二种情况较多，问题描述如下： 茹固|_ 田园| 技装容器 图2 1 装箱问题描述 给定n 个矩形体口，口：a a 。以及无限多大小都相等的箱子，箱子的最大装载空间 分别为c k ，c 人c 圪矩形体体积分别g k ，g g a g v 。，每个矩形体对应于一个价 值系数、数量和约束条件，价值系数分别用只，他，表示，可以代表价值，运 费等；约束条件分别用q ，q ：a q 。表示，可以代表摆放方向、堆码层数、到站次 序等；数量分别用x ，x ：似。表示。设x 。表示第k 种货物装入第i 辆车的数量， w e b 模式下三维装箱问题求解方法研究 则第i 辆车的实际装载空间设为： l ( x 肿x ，z 似衄) 2 善最x 脯c v , q l 那么装车问题可表述为： r a i ny 正伍i 1 ，x f 2 心如) 其中x 腑5 x t 4 - 4卅 ( 2 1 ) ( 2 2 ) 由此可见装箱问题即在满足约束的条件下，使获得最高的效益，即求得全局最优 解。 2 2 问题的启发式算法分析 启发式算法是和问题求解及搜索相关的，也就是说，启发式算法是为了提高 搜索效率才提出的。1 9 8 4 年p e a r l j 在其专著中对启发式算法进行了详细的讨论。 他认为：所谓启发式算法是指一组指导算法搜索方向的、建议性质的规则集，通 常按照这个规则集，计算机可在解空间中寻找到一个较好解，但并不能保证每次 都能找到较好的解，更不能保证找到最优解。换句话说，所谓启发式算法就是那 些从大量的实验数据来看，算法的实际计算性能较好，但理论上证明这些算法在 最坏情况下解题性能并不好，或者理论上并不能证明这些算法具有优良的解题性 育昌。 一种在启发式算法设计中应用较多的是垂直“层 或“墙 ( w a l l ) 的概念( 如 图2 2 所示) 。使用“层来生成摆放模式的基本思路是：通过生成垂直的互不 相关的包含多种物品的层，由这些层来组成完整的布局模式，层内单个物品的摆 放方式不同的算法有各自的规定。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 比较了1 4 种基于“层 的方法。因为 层与层之间互不关联，独立存在，所以一个完整的布局模式中，这些层的顺序可 以任意调整，能够更容易地满足一些约束，比如对重心的要求。 w e b 模式下三维装箱问题求解方法研究 图2 2 垂直层或墙 按层装填的思路可以使问题简化，然而，在g r 的层装填中，盒子是被一个 一个放入的，而且是按照先向上、再向右、再向前的递归方式进行的，每放入一 个盒子，都要重新分析集装箱空间的变化，这势必带来几方面的问题： ( 1 ) 算法的时间效率低。很多盒子逐一被分析和处理，会浪费大量宝贵的 计算时间，对w e b 模式下的装箱求解极为不利。 ( 2 ) 孤立地将每一个盒子按照先向上、在向右、再向前的模式装入，会降 低工人的装箱效率，实际应用性不强。相反，如果把一类盒子作为一个整