（通信与信息系统专业论文）复杂集装箱装载问题求解方法研究.pdf

中国海洋大学学位论文 复杂集装箱装载问题求解方法研究 摘要 集装箱装配货物是将具有一定体积、重量、价值、数量的不同种类货物合 理地放置在一个具有一定体积和载重量限制要求的集装箱空间内的过程。装配 方案必须满足定性和定量两方面的要求。在定性方面，主要考虑空间的合理利 用，提高货运途中的安全系数等因素；在定量方面，主要考虑有限空间内的不 同种类不同数量的货物价值最大化。这一类问题是多约束多目标的组合优化问 题，称为复杂集装箱装载问题。许多看似简单的装配问题也往往是n p 完全问题， 即在有限时闻内找不到问题最优解。 论文首先指出课题产生的时代背景，然后对装箱问题进行分类，阐述了本 文的研究内容及其意义接着重对装箱问题中的复杂三维集装箱装载问题进行 分析，概述国内外研究现状，并指出现有成果的优点与缺点从集装箱装载问 题的变化形式、问题分类角度来考察各予问题在约束条件和目标函数方面的区 别，从问题的启发式方法和进化算法角度研究现有解法的思路。 在此基础上，针对实际装载中每种类型货物数量一般较多、使用现有针对 单个物品的基于三空间的启发式算法存在装载效率和空间利用率低的问题，采 用同种类型货物一次性装载的思想，提出了一种新的基于六空间分解的启发式 算法，将同类型货物一次性装载到待布空间，根据是否能够摆满分别采用“标 准装载方式”和。非标准装载方式”来定位货物，给出了其定序规则、空间分 割方法、约束条件处理方法和算法流程。 遗传算法作为一种模拟自然进化过程的随机性全局优化概率搜索算法，在 求解优化问题中显示了优越的性能。鉴于目前遗传算法在装箱领域的成功经验， 将其与本文提出的启发式算法相结合构造混合遗传算法，以保证获得全局最优 解或次优解。 通过对实际装箱数据的算例分析和与单种货物数量较多的现有结果比较， 表明本文算法处理复杂集装箱单箱装载问题是有效的，具有较高的空间利用率 和计算效率。同时，通过与每种货物数量唯一的现有结果比较分析可见，算法 虽是针对每种货物一次装载较多的情况设计的，但对于每种货物数量唯一且没 有约束条件的情况，也具有较好的适用性 复杂集装箱装载问题求解方法研究 根据本文提出的启发式算法和混合遗传算法，开发了电子配载系统。该软 件具有能够满足实际集装箱装载中的多约束条件、安装使用灵活方便的优点， 可真正用于物流企业的配载实践。论文介绍了系统功能和数据流程，并简要说 明了操作过程。 论文最后对研究成果进行总结，分析了基于六空间分解的混合遗传算法及 电子配载系统的成功与不足，并对今后系统的深入研究进行展望，指出未来的 一些研究方向。 关键词：复杂集装箱装载；多约束；空间分解；启发式算法；混合遗传算法 2 中国海洋大学学位论文 t h er e s e a r c ho fa p p r o a c h e st os oivin gc o m ple x c o n t a i n e r i c a d i n gp r o b i e m a b s t r a c t a s s e m b l i n gg o o d si nac o n t a i n e ri sap r o c e s st h a tp u tg o o d so fd i f f e r e n tk i n d s ， w h i c hh a v ec 豇 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 es p a c eo fc o n h a i n e r h 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 i tm u s ts a t i s f yq u a l i t a t i v ea n d q u a n t i t a t i v er e q u i r e m e n t s i nq u a l i t a t i v ea s p e c t , t h em a i nc o n s i d e r a t i o ni sr a t i o n a l u t i l i z a t i o no f t h es p a c ea n di m p r o v i n gt h es a f e t yc o e f f i c i e n ti nt h et r a n s p o r t a t i o nw a y , e t c ：i nq u a n t i t a t i v ea s p e c t , t h em a i nc o n s i d e r a t i o ni sv a l u em a x i m i z a t i o no f c a r g oo f d i f f e r e n tt y p ea n dq u a n t i t yi nf i n i t es p a c e t h i sk i n do fp r o b l e mi sac o m b i n a t o r i a l o p t i m i m i o np r o b l e m o fm u f f - c o n s t r a i n ta n d m u t i - o b j - t , c a l l e dc 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 m a n yp a c k i n gq s t i o 珊s e e m i n g l ys i m p l ea 糟o f i e n n 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 eo 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 d t i m e 1 1 1 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 r 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 s u m m a r i z e st h eb i np a c k i n gp r o b l e mi ns o r t s , a n de x p o u n d sr e s e a r c hc o n t e n t sa n d i t s s i g n i f i c a n c e f o l l o w i n g , i te m p h a s i z e s o n a n a l y z m g t h e c o m p l e x t 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 mo fb i np a c k i n gp r o b l e m , s u m su pl h ec u r r e n t s t u d ys i t u a t i o nb o t ha th o m ea n da b r o a d , a n dp o i n t so u tt h ea d v a n t a g e sa n d d i s a d v a n t a g e so fe x i s t i n ga c h i e v e m e n t s n 呛d i f f e r e n c e so fs e v e r a ls u bp r o b l e m si n c o n s t r a i n tc o n d i t i o n sa n do b j e c t i v ef u n c t i o n sa r er e v i e w e df r o mt h ep o i n to ft h e c h a n g ef o r ma n ds o r t so fc o n t a i n e rl o a d i n gp r o b l e m , a n dt h ee x i s t i n gs o l u t i o n sa m s 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 la l g o r i t h m 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 f as i n g l et y p eo f g o o d s i sa l w a y sm o r et h a no n eo rs o m e t i m e sl a r g ea n dt h e r ei sl o wl o a d i n ge f f i c i c ya n d s l m c eu t i l i z a t i o nr a t i ou s i n gh e u r i s t i cm e t h o db a s e do nt h r e ep m i t i o m ss p a c e p o i n t i n gt oo n eg o o d s , an e wh e u r i s t i cm e t h o db a s e d0 1 1s i xp a r t i t i o n i n gs p a c ei sp u t f o r w a r da c c o r d i n gt ot h ei d e at h a tg o o d so ft h es a m et y p es l l o l l l db el o a d e da tt h e 3 复杂集装箱装载问题求解方法研究 s a m et i m e t h i sm e t h o dp u t sg o o d so fc e r t a i nt y p ei nc u r r e n tc u h o i d a ls p a c ea to n e t i m ea n dc h o o s e so n ef r o mt w op a t t e r n sc a l l e d n o r m a ll o a d i n g ”a n d u n n o r m a l l o a d i n g a c c o r d i n gt ow b e t h c ra l lt h eg o o d so fo n et y p ec a nb ep u ti nc u r r e n ts p a c e 砒o n et i m eo rn o tn 圮r u l eo fs e t t i n go r d e r , t h es p a t i a lp a r t i t i o nm e t h o d , t h e p r o c e s s i n gm e t h o do f c o n s t r a i n tc o n d i t i o n sa n dt h ea l g o r i t h mf l o wi sg i v e n a sar a n d o mg l o b a lo p t i m i z a t i o np r o b a b i l i t ys e a r c ha l g o r i t h mw h i c hs i m u l a t e s n a t u r a le v o l u t i o n a l p r o c e s s , g e n e t i ca l g o r i t h m h a sd e m o n s t r a t e di t s s u p e r i o r p e r f o m m c ei ns o l v i n go p t i m i z a t i o np r o b l e m i nv i e wo ft h ef a c tt h a tg e n e t i c a l g o r i t h m sh a v eg o ts u c c e s s f u le x p e r i e n c ei nb i np a c k i n gp r o b l e ma tp r e s e n t , a h y b r i dg e n e t i ca l g o r i t h mi sm a d eb yc o m b i n i n gg e n e t i ca l g o r i t h ma n dt h en e w h e u r i s t i cm e t h o dg i v e ni nt h i sd i s s e r t a t i o ni 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 no r s u p e r i o rs o l u t i o n t h r o u g ha 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 s f r o md a t ai nw h i c ht h en u m b e ro fo n el 【i n do fg o o d si sl a r g e i ti si n d i c a t e dt h a ti t s e f f e c t i v eu s i n gt h ea 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 lw i t hc o m p l e x c o n t a i n e rl o a d i n gp 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 m e a n w h i l e ，t h r o u g ha n a l y z i n ga n dc o m p a r i n gw i t ht h ee x i s t i n gr e s u l t sf r o md a t ai n w h i c ht h en u m b e ro fak i n do fg o o d si so n l yo n e , i ti ss h o w nt h a ta l t h o u g ht h i s a l g o r i t h mi sd e s i g n e df o rt h es i t u a t i o nt h a tt h en u m b e ro fas i n g l et y p eo fg o o d si s m o r et h a no n e ，i ti sb e t t e rf i tf o rt h es i t u a t i o n o n en u m b e r , o n et y p e e i t h e r o nt h eb a s i so ft h eh e u r i s t i cm 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 mp u tf o r w a r di n t 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 e 啪s a t i s f y m u t i - c o n s t r a i n tq 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 oi n s t a l l i t c a nb eu s e db yl 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 f l 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 r 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 dg e n e t i ca 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 cl o a d i n g s 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 ds o m e r 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 y w o r d s ：c 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 ；m u f f - c o n s t r a i n t ；s p a c e p a r t i t i o n i n g ；h e u r i s t i cm e t h o d ；h y b r i dg e n e t ca l g o r i t h m 4 学 2 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 ( 逵! 如塑直墓丝盂要挂型直明鲍：奎拦互窒2或其他教育机构 的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：娟编签字日期：渺5 年f 月刁日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文( 保密的学位论文在解密后 适用本授权书) 学位论文作者签名：字目铞 签字日期：加0 6 年箩月1 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导燧字：丁要锄 签字日期：硝年，月。7 日 电话： 邮编： 中国海洋大学学位论文 1 1 问题产生的时代背景 第一章绪论 二十世纪九十年代以来，随着新一轮的运力扩张，世界各大运输公司竞相 开辟新航线，扩大经营规模，造成航运市场供大于求，竞争日趋激烈。为了保 证揽取足够的资源，各公司纷纷采取降低运价的策略，导致运费水平一降再将， 各航运公司纷纷出现效益下降，尤其是东南亚金融危机的爆发，对航运公司经 营更是雪上加霜，大多数公司的经营处于微利甚至亏损的境地。各公司在主营 业务收入大幅下降的情况下，纷纷将目标集中到成本管理上由于在航运公司 的各项运营成本中，集装箱管理成本已成为最重要的成本之一因此，如何能 最大限度的提高集装箱管理水平，降低集装箱管理成本，已成为当务之急。 在许多大中型海运港1 ：3 和航运机场，集装箱装配货物方案是将具有一定体 积、重量、价值、数量的不同种类不同数量的货物合理地放置在一个具有一定体 积和载重量限制要求的集装箱空间内的过程，装配方案必须满足定性和定量两方 面要求在定量方面，主要考虑有限空间内的不同种类不同数量的货物价值最大 化；在定性方面，主要考虑空间的合理利用，提高货运途中的安全系数等因素， 这一类问题是多约束多目标的组合优化问题，这里称为复杂集装箱装载问题。许 多看似简单的装配问题也往往是n p 完全问题，即在有限时间内找不到问题最优 解 作者在某海洋运输代理部门了解到，集装箱装箱分为两阶段：第一阶段， 积累货物，并计算到达某地的货物体积，当体积达到一定数量时，整理出一份 待装货物清单( 包括尺寸、重量、体积、特殊说明等) 第二阶段，将清单上货 物装入集装箱，若有空隙，则填充某些隔离材料，或用金属丝固定常因为以 下原因遇到困难： 货物清单上货物尺寸不准： 货物清单上某种货物数量不准或又有额外的货物需要装入 因此，需要经常装上卸下，再装上，几次下来，也会有该装的没有装入， 复杂集装箱装载问题求解方法研究 装载结果不尽人意。再如，与集装箱装载类似的棚车装载，其装载利用率一般 在6 0 - 7 0 ，若能提高到9 0 ，年利润可观。这就要求计算机辅助制定可行 的装载计划，虚拟出装箱过程，避免手工重装，为现场装卸提供决策支持。 集装箱在实际的装载中常用约束条件如下： 1 ) 方向限制：在装载中，货物的摆放方向受约束，例如有些货物的包装标有 向上的箭头等。一般货物装载时的方向约束可归纳为三种约束，既任意旋转、水 平旋转、不能旋转。 2 ) 承载能力限制：货物的承载能力由包装盒的结构和货物本身的性质决定。 有些货物不能摆放在其它货物之上，所以装载层数要受限制。 3 ) 稳定性限制：货物在集装箱内不能窜动，以免相互间磕碰引起损坏。需要 用泡沫塑料填充空余空问或用包装带捆束以固定货物。另外应尽可能使集装箱重 心和其几何中心一致，以有利于运输和机械装卸作业。 4 ) 货物编组：属于同一接受人的货物或货物类型相近的编成一组，便于装卸 作业。 5 ) 装配隔离限制：某些货物不宜与其他货物混装，如食品和化工产品等。 6 ) 某类货物整体运输对于机床等设备，有时需分解成各个部件运输，因此应 尽量组织一起装载发运。 7 ) 装配优先级；按照货物的运到地点、期限或者保质期等情况确定装箱货物 的优先次序。 当然，并不是每种因素在任何情况下都很重要，但相当一部分情况下某些因 素直接影响到了配送的质量，需要引起足够的重视。 集装箱运输具有运输效率高、运输质量好、符合环保的要求等特性，是一种 快速发展的运输方式。随着国内物流业的发展，物流相关技术的应用和发展受到 越来越多的重视。装箱问题作为物流配送过程中的一个关键性的技术，对提高配 送业务的自动化水平、提高货物装载的优化程度、提高配送业务的工作效率和规 范业务流程等方面都有重要的意义。在上述有利因素作用下，未来我国集装箱运 输发展可望百尺竿头更进一步 提高散集装箱配载的质量、效率和可靠性，对集装箱安全、高效运输意义重 大当前，有关集装箱配载系统的研究和设计主要集中在用计算机解决配载计算 2 中国海洋大学学位论文 问题 针对上述原因，本文选择复杂集装箱装载问题求解方法这一课题，以解决当 前复杂集装箱装载环节面临的问题。旨在寻求面向现代物流企业实用的优化算 法，建立现代物流配载系统，以期达到对现代集装箱装载业务有一个实用、有效 的技术解决方案目的。 1 2 装箱问题分类 装箱问题涉及多学科、多领域的知识，在生产实践中广泛出现并亟待解决。 本文从不同角度把装箱问题分为以下几类： 1 2 1 按照装箱物体所属装箱空间对装箱问题的分类 1 一维装箱问题 一维经典装箱问题可描述如下，s ；( s j ，岛，只) ，其中0 & l ，称之 为第i - e 物体的体积，1 s i s 打，有若干只容积是i 的箱子，问题是如何设法将 墨，8 2 ，瓯放入尽可能少的箱中一维装箱问题看似简单，但从计算复杂性理 论来讲，装箱问题是一个n p 难题，很难精确求解，目前的求解方法主要是一 些近似算法，如n ft n e x t f i t ) 近似算法f ff f i r s t f i t ) 近似算法，f f d ( f i r s t f i t d e c r e a s i n g ) 近似算法，b ft b e s t f i t ) ，b f dt b e s t f i t d e c r e a s i n g ) 等，评 价这些算法最重要的标准是：算法的在线特性、时间复杂度、最坏情况渐进性 能比表1 1 列出了部分著名装箱问题近似算法的研究现状【1 1 ： 近似算法在线特性时间复杂度量坏情况渐进性能比 下次适应算法( n f ) 在线 0 ( n ) 2 首次适应算法( f f )在线o ( n l e s n ) 1 7 量佳适应算法( b f )在线 0 ( n i o 印 1 7 量坏适应算法刑n 在线 0 i n i o g n ) 2 降序首次适应算法( f f d ) 脱线 0 ( n i 哪) 1 1 ，9 降序最佳适应算法f d 脱线 o n l o g n ) l l ，9 表i 1 经典意味装箱问题的几种著名近似算法 3 复杂集装箱装载问题求解方法研究 从表1 - 1 我们可以看出b f 是较优的在线算法，b f d 是较优的脱线算法，在 现实生活中这两种算法是较常采用的算法 b f 算法的大致思想是：把箱子分为空箱和已用箱，对于每一个物品，按最 优适配算法先在已用箱中找合适的箱子，如果没有合适箱子，则再在空箱中找， 找到后，修改该箱数据，并把该箱插入到已用箱中。直到装完所有的物品，如 果物品在装箱前按体积降序排列，即为b f d 算法，b f d 算法在很多情况下可 取得很优的结果，甚至最优解，但在极端情况下的结果却不理想，如对于单位 体积的箱子，如果物品装箱顺序为( 0 8 ，0 7 5 ，o 1 5 ，o 1 ，0 0 8 ，0 0 8 ) 采用b f d 算法所需的箱子数目为3 个，比最优解要多用一个箱子。 一维经典装箱问题有着广泛的实际背景，如： 1 ) 用户送来一张订货单，上= h ，a ：口。 ，a j 表示第f 个货件的长度，货件 可能是钢条、铅管、电缆、原装纸卷等一维线材假如厂家所供应原材料的标 准长度为c ，同时满足a l c 。v i ，试想如何能以最少量的原材料截出用户所需 的货件。 2 ) 有n 个零件需要加工，假定每个零件只需在一台机器上加工一次即可。 设第i 个零件所需的加工时间为矾，要求所有零件在规定时问c 内全部加工完 毕，试问如何能以最少数的机器和入力在规定时间内完成所需加工任务。规定 所有机器的性能皆相同。 2 二维装箱问题 二维装箱问题有下述两类： 1 ) 给定n 个矩形工；h ，口2 q ( 其中q = g 。，y 。) ；，乃( o ，1 】，f = 1 ，2 疗) 装入一宽度为1 ，高无限大的矩形a ( 箱子) ，要求将n 个矩形q ，a 2 a - 6 不叠 迭地装填入a 中，使布局的总高度最小。对每个小矩形a 装填入a 后的姿态也 有直角装填，定向等限制； 2 ) 给定n 个矩形= 缸，口： 及无限多大小都相等的大矩形( 箱子) ，要 求将q ，a 2 a n 直角定向装填入箱子中，使所占用的箱子个数最少 对第一类二维装箱问题，若设小矩形的高度都相等，限制装填方式为直角 中国海洋大学学位论文 定向，则问题蜕化为一维装箱问题；对第二类问题若设小矩形之宽与箱子宽相 等，也退化为一维情形。 这类问题在实际中有着广泛应用。如应用于板类( 金属板，木板，玻璃、大 理石板等) 切割行业，服装剪裁行业等中的下料问题；建筑业中的房间布局，工 业中的模板布局( t e m p l a t el a y o u t ) 、新闻报纸、广告等版面布置，集成电路布图 设计及其它一些工程设计等 3 三维装箱问题 与二维装箱问题相似，三维装箱问题也有下述两种形式 1 ) 给定n d 矩形体l ； 口i ，a 2 a n ( ；g v e a , = “，y l ，刁) ；而，y j ，毛e ( o , 1 1 ， f = 1 , 2 一) 装入一底为l x l ，高为正无穷的柱形箱子a ，要求将n 个矩形体 q ，d 2 互不叠迭地装填入a 中，使布局的总高度z 最小对每个矩形体a l 装 填入a 后的姿态也有直角装填，定向等限制。 2 ) 给定l i t 个矩形体a t ，吒q 及无限多大小都相等的箱子，要求q ，吃q 直 角定向装填入箱子中，使所占用的箱子个数最少 对第一类三维装箱问题，若设矩形体的高度都相等，限制装填方式为直角 定向，则问题蜕化为二维装箱问题；对第二类问题若设矩形体之宽与箱子宽相 等，也退化为二维情形 因此三维装箱问题可以看作是一维、二维装箱问题的一个泛化 2 , 3 1 三维装 箱问题有着广泛的应用背景，如运输行业的集装箱货物装载、飞机装舱、码头 装货、列车装箱，机械行业中箱体和钟表等布局，航空、航天工业中导弹仓的 布局，以及建筑、电子，造船业、纺织业等诸多领域 1 2 2 按照装箱物体的形状对装箱问题的分类 1 规则物体的装箱 包括二维规则物体的装载和三维规则物体的装载。规则物体是指具有规则 外形的物体，例如圆柱体、矩形体等在以前及现在的装载研究中，研究较多 的仍然是规则体的装载问题，如：工业应用中的底盘装载问题；三维布局中的 集装箱的货物摆放问题 ， 5 复杂集装箱装载问题求解方法研究 货物底盘装载问题广泛存在于工业生产和交通运输中。由于箱子的大小和 形状完全相同，且箱子的边平行于底盘的边，因此该问题也可简化为二维问题。 对于该问题，有的学者使用精确的方法求解 4 1 。 2 不规则物体的装箱 包括二维不规则物体的装载和三维不规则物体的装载。不规则物体是指具 有任意几何形状的物体。不规则物体的装箱问题在工业生产中大量存在，但同 时也是难度最大的装箱问题。二维不规则物体的装箱如服装样本的下料、皮革 下料等。三维不规则物体的装箱如向具有任意几何形状的容器中放置任意几何 外形的装箱物体，并满足特定的约束条件，达到装箱目标最优。从文献资料中 可以看出，许多研究者利用人工智能原理求解该复杂问题1 5 l 。该问题的求解算 法基本上是启发式的。 1 2 3 按照装箱物体达到情况对装箱问题的分类 i 在线装箱问题 如果一个装箱算法在装入物品时，只利用嘶前面物品a j , 1 ，i 的信息， 而不知道后继元素的任何信息，即按照元素到达顺序随到随装，则称该算法为 在线( o nl i n e ) 算法。这种情况下的装箱问题称为在线装箱问题脚。在实际应用 中，往往要求装载具有在线特性。例如对从传送带上下来的物体进行装载。 很多一维、二维在线装箱问题都采用层的思想：物品的尺寸不能提前知道。 层由沿箱子宽度排列的一列物品组成。也就是说箱子是由层中最大高度的物品 来分割的。典型方法包括n e x t f i td e c r e a s i n gh e i g h t ( n f d h ) l 拍一，f i r s t f i t d e c r e a s i n gh e i g h t ( f f d h ) 1 2 7 1 ，b e s t f i td e c r e a s i n gh e i g h t ( b f d h ) 嘲，i m p r o v e d f i r s t f i td e c r e a s i n gh e i g h t ( i f f d ) a n dh a r m o n i ca l g o r i t h m s 2 7 1 尽管这 些方法都很相似，但是每个算法都是用不同的方法决定将物品放在哪里。 和二维装箱算法相似的一些算法被应用到三维装箱问题中在线最流行的 解决三维装箱方法之一是s h e l fm o t h e d ! 引该方法也是通过聚组相近尺寸物品 来提高装载利用率的。 2 离线装箱问题 物品装载以前就已得到所有物品信息，之后统一处理所有物品的近似算法 中国海洋大学学位论文 称为离线( o f f l i n e ) 装箱算法这种情况下的装箱问题称为离线装箱问题。在现 代化的物流配送中，很多都要求按订单送货，因此物品的信息提前都是知道的。 该问题广泛地出现在铁路货车车厢装载、汽车车厢装载、轮船配载、集装箱装 载等情况中。 分支定界方法嗍、遗传算法【l o u 1 和模拟退火方法u 2 1 都是用来解决离线的装 箱问题的常用算法分支定界方法利用递归方法寻找问题的可行解，采取了必 要的限制条件，设法排除可行域中大量非最优解区域，从而能够有效求解一些 规模较大的问题。在遗传算法中，问题模型是数字串，称为染色体。一个染色 体的存活概率被称为适应度函数这个函数是衡量染色体所代表的解接近于最 优解的程度在执行遗传算法之前，给出一群“染色体”，也即是“假设解” 然后，把这些“假设解”置于问题的“环境”中，并按“适者生存”的原则， 从中选择出较适应环境的。染色体”进行复制，再通过交叉，变异过程产生更 适应环境的新一代。染色体”群这样，一代一代地进化，最后就会收敛到最 适应环境的一个。染色体”上，它就是问题的最优解模拟退火方法源于对固 体退火过程的模拟，它与局部搜索算法的最大不同是接受新解的准则不同，允 许目标函数在有限范围内变坏，由一控制参数t ( 温度) 决定。开始时t 值大， 可能接受较差的恶化解，随着t 值的减小，只能接受较好的恶化解，最后在t 值趋于零时，就不再接受任何恶化解了使算法既可以从局部极小的“陷阱” 中跳出，更有可能求得组和优化问题的整体最优解，又不失简单性和通用性。 i 2 4 按照装载过程是否有惩罚值对装箱问题的分类 1 带拒绝装箱问题 带拒绝一维装箱问题可描述为：设有许多长为c 的一维箱子，给定物品集u 每个物品有两个参数# 长度和罚值。u = “，材2 ， ，虬长为q ( 0 q 绘出t 0 - 1 整数 线性规划模型，考虑了货物和集裟箱的不同规格、货物的方向，放置因素，并分 析了一然特殊情况如单个集装箱装配、载重分布等。i v a n c i c 等人给出了一种基于 整数鬏魁鹣三维装簇囊发式算法，对予每令集装篇蔹次装黧塞至黪寒货耱装宠为 止鳓但是这种方法仅适用于嗣种规格的集装箱装配，而且幽于变量以及约束条 件随货物数量增加而迅速增多，从而使问题难乎求解。e l e y 分别应用串行和并行 篆貉浚诗7 装配方法渊，壤据融黼i c 等久浚诗瓣| 毒7 令馕景逻孬实验。实骏戆象显 示，用遮两种方法可以对其中1 4 种情形得到优化解，但不足以说明孰优孰劣。值 得注意的是两种方法对强差异货物情形都能得别很好的解 2 3 阍题的启发式算法 一 、 癌发式算法是相对于最优算法提出鲍，一个闯题的最优算法是求褥该瓣题 每个赛绷的最往辩，启发式算法掰以这样定义：一个壹鼹或经验的构造算法， 在可以接受的花费( 时间，空间铎) 下给出待解决组合优化问题的每个实例的 一个霹抒解，该可行鼹与最优鳃鹣攘离程度并誉一定可以预诗。 另一种定义是：扁发式算法怒一种能在可接受的费用肉溽找最好静解的技 术，但不一定能保证所得解的可杼性和最优性，甚至在多数情况下，无法阐述 所褥鳞阋最饯解的避似程度。 由予实际应爵约束条件狠爱杂，所殴具有多约束条件豹装箱拇遂豹求解也 复杂集装箱装载问题求解方法研究 是困难的。对于二维的装箱问题研究较多珥2 卯，三维的装箱问题由于其复杂性 和难度大，因此研究相应较少，且很多算法都是基于一定的假设之下阅。目前， 实际应用中，往往采用一些启发式算法来求解。 2 3 1 空间分割方法 1 三空间分割法 目前许多启发式算法均基于三空间分割的方法当一个货物在摆放入一个 集装箱后，该集装箱被分割成三个子空间( 除自己占用的空间) ，分别为左空间 l ，右空间r ，和上空间m 。分割如图l 所示。同理每个子空间在充填过程中， 被摆放入货物后，同样被继续分割为三个空间，而原空间消失，直至没有待布 局物体满足要求或集装箱无可利用空间为止。 图2 1 空间分解策略示意图 何大勇和姜义东1 2 7 , 2 s 最早将三空间分割法引入三维装箱领域，将三空间与 三叉树的数据结构相对应，采用深度优先的方法处理三叉树，通过将布局空 间依次分割，每次放入相对于当前布局空间来说是满足特定条件的最优布局块， 来完成不同大小的三维矩形物体的布局方案的确定。定序规则和定位规则分别 是按布局块体积递减定序和占角优先策略，即每次将布局块定于当前布局空间 的后部左下角。 该算法思路简单，有效避免了空间干涉现象，能在合理的时间内得到问题 的满意解，尤其适合于大规模布局求解；但它无法处理更复杂的约束，如后到 先放、尽量平铺、重心约束等，这些约束往往是至关重要的。 2 按层分割法 另一种思路是将空间分层。g e o r g e 侧提出一种分层策略进行装载，之后很多 中圈海洋大学学位论文 学者都遵循这一原则。该方法按阶段填充，在深度方向按层布局，尽量使某一层 的外表面平整。o ) b i s c h o f fa n dd o w s l a n d m l 方法是一层层的开始布局，但与文 献 3 0 有两点不同：每一层仅由单一类型箱体开始布局：每一层的布局通过二 维平面布局( 该算法即底盘装载布局p a l l e tl o a d i n g ) 方法求解。eb i s c h o f f 忱1 比较文献 3 1 与文献 3 2 ，将文献 3 1 方法中的选择标准与文献 3 2 中的判断标 准交叉组合，组成1 4 种启发式算法，并对这1 4 种算法性能进行比较，经过大量试 验，得出结论，对于盒子种类小于5 种的采用文献 3 2 的方法，而对于大于1 0 种 类型的，采用文献 3 1 的算法，并提议依此设计复合启发式算法，针对箱子类型 的数目，采用不同算法。 p i s i n g e r 【l s ! 把集装箱分解成若干层，层又分解为若干条，条由相似的物体组 成e k 尹1 把相同的物体组成同质块，用同质块填充集装箱。这几种方法研究的 物体尺寸比较接近，当物体的种类很多、尺寸差异大的时候，这些方法并不适用 因此，刘嘉敏嘲提出了一种新的按层划分集装箱，在每层内通过回溯对不同物体 进行组合放置的算法为避免对所有物体进行组合带来的存储空间急剧增大的问 题，采用限制组合与启发式相结合的方式 刘霞聊】采用分层的启发式算法，每层有一个以一定规则的货物( 称为层定义 盒子l d b ) 确定，每层再进行空间分解，并逐步装载各形成的子空间，由于每一 个盒子可能有几种放置形式，且变化合资的放置形式可以获得更多的装载方法， 从而可在更大范围内取最佳方案，但每个盒子都考虑其所有放置形式，计算量大， 不好实现而通过变化每一层的l d b 的放置形式，从而改变该层的有关数据，更 新装载方法，从中选出空间利用率最高的层作为该层的最优装载方案，则是可行 的。 2 3 2 约束条件的处理 同时考虑多种约束条件的启发式算法较少，可查阅到的文献【3 5 , - 琊z l 基本是 将多种约束条件分别用来确定不同种类货物的摆放次序和定位策略。 1 ) 方向约束 文献 3 5 根据货物与待布空间的长宽高大小来确定方向，使得货物的最长边 与待布空间的最长边平行设方向约束属性胄= l ，2 3 ，若置= l 则货物可任意旋 复杂集装箱装载问题求解方法研究 转，r = 2 则货物可水平旋转，r = 3 则货物不能旋转。即r = l ， m a x 1 , ，嵋，h m a x 1 ，w 】；货物r = 2 ，m x g , ，w , m a x 1 ，w 】；r = 3 ，1 , w l w , i h ) 文献 3 6 根据货物的具体属性，如能否侧放、能否倒置等，将一件货物复制 为多个货物。例如某货物既可以侧放也可以倒置，就分别以它的3 个不同面作为 底面，得到6 种不同的摆放姿势，把它们当作6 个不同的货物进行处理。文献 3 7 优先考虑长边与集装箱宽方向平行放置 2 ) 承载能力约束 文献 3 5 将货物的配置位置属性设为l ，2 ，3 ，规定属性值小的不能摆放在 属性值大的货物上面，同种属性的货物之间不受限制。例如货物的属性为2 ，则 货物只能摆放在1 ，2 上面，不能摆放在l 下面，也不能摆放在3 上面。 3 ) 稳定性约束 文献 3 6 同时考虑了重心和左右平衡。为了降低重心高度并使货物质量尽 量均匀分布，采取优先平铺策略。优先对l 和r 空间进行分解，处理方法为平 面二叉树分解，对产生的m 空间只记录不分解。当摆放完一层后，依次将记录下 来的m 空间作为当前解空间，进行l 和r 空间分解，如此循环直至货物装载完 毕或者没有足够的空间为止。对于大型集装箱或者大型车辆，运输过程中的左 右平衡无疑是等级最高的约束条件。为了使集装箱左右尽量平衡，并且使未填 充空间尽量出现在中间以利于稳定性，将未布局空间按照其中轴线的位置分为 两类，相对于集装箱的中轴线来说，偏左的待布局空间，每次将物体定位于它 的后部左下角；偏右的待布局空间，每次将物体定位于它的后部右下角。与此 相对应，两种方法的空间分解策略也略有不同。应用这种策略，货物会优先摆 两边，然后填充中间，符合算法的定位规则。 文献 3 5 同样采用优先平铺策略使货物重心在限定的范围内。同时，为满足 多集装箱装载的平均高度要求，令k 个集装箱的平均高度h ：h i k ， n 【为第k 个集装箱的高度与平均高度的差h k = h k - h ，当h k 超出一定范围时，将此集装