（计算机应用技术专业论文）航空货运装载问题算法设计与研究.pdf

中罔民航大学硕i ：学位论文 摘要 随着世界经济与国际贸易的稳步发展，航空运输业将会以较快的速度增长。 提高飞机货舱利用率，是提高经济效益的重要途径。航空货运装载问题研究，对 推进航空物流业的发展起着积极的作用，具有一定的理论与现实价值。 对于飞机货舱成拱形的特点，提出了航空货物装载问题，组装的宽度随着货 舱或者i a t a 指定集装器的轮廓动态变动。 提出了属于一维装载问题的散舱装载方法，主要应用于比较简单的装载决策 问题，为散舱装载提供了粗略的优化方案。 提出了宽体客机集装器装载方法，它属于三维装载问题。采用逐层填充的方 式，首先通过基于统计函数的启发式规则确定层高，根据机舱的要求或者集装器 类型动态确定层宽，然后对层进行二维填充。二维平面布局采用了两种启发式方 法：一为寻找等高线法，布局空间由一系列等高线组成，根据启发式规则确定矩 形的放置方式和等高线的分解、合并等方式；二为条状布局法，把布局空间分成 若干水平或竖直条，由启发式规则确定条的宽度，然后用背包算法对条进行装填。 后者对大多数弱异类问题有较好优化方案，而前者适用于强弱异类问题，并且算 法在时间、空间上消耗较小。启发式规则以减少浪费空间为原则，不但考虑了空 自j 利用率，而且考虑了载重利用率。箱体组装后的形状很好地迎合了飞机货舱轮 廓上的特点，并取得了较优的空间、载重利用率，为弱异类装载问题提出了一种 新的方法。 实例计算的结果，说明本文方法对实际装载作业具有较强的指导作用，同时 与其它几种算法比较的结果表明该方法切实可行，并且方案较优。 关键词：启发式，装载，布局，组装，散舱集装器 中固民航人学顾i 。学位论文 a b s t r a c t w i t hs t e a d yd e v e l o p m e n to fg l o b a le c o n o m ya n di n t e r n a t i o n a lt r a d e ，a i r t r a n s p o r t a t i o nw i l lg r o wr a p i d l y i m p r o v i n ga i r c r a f tc a r g oh o l du t i l i z a t i o n ，i sa s i g n i f i c a n ta p p r o a c ht ob o o s te c o n o m i cb e n e f i t a i rc a r g ol o a d i n gp r o b l e mr e s e a r c h ， p l a y sa ni m p o r t a n tr o l ei np r o p e l l i n ga i rl o g i s t i cd e v e l o p m e n t ，a n dh a sa c a d e m i ca n d p r a c t i c a lv a l u e c o n s i d e r i n gt h ec h a r a c t e rt h a ta i r c r a f tc a r g oh o l d sp r e s e n ta r c , a i rc a r g ol o a d i n g p r o b l e mi sp r a i s e d t h eb u l kl o a d i n gm e t h o dw h i c hb e l o n g st o1 - d i m e n s i o nl o a d i n gp r o b l e mi s i n t r o d u c e d ，i ti sm a i n l yu s e du n d e rs i m p l ep a c k i n gc i r c u m s t a n c e ，a n dp r o v i d e s c u r s o r yp r o j e c tf o rt h eb u 墩l o a d i n gp r o b l e m w i d eb o d ya i r c r a f tu l d ( u n i tl o a d i n gd e v i c e ) l o a d i n gm e t h o d sw h i c hb e l o n gt o 3 - d i m e n s i o nl o a d i n gp r o b l e ma r ep r o v i d e d t h el o a d i n ga r r a n g e m e n ti sb u i l tu pi n l a y e r sf r o mt h eb o t t o mu p w a r d s ，b o x e so r g a n i z e di nl a y e r s f i l li n t ou l d s ：f i r s t ， l a y e r sh e i g h t i sg e n e r a t e db yh e u r i s t i cr u l e s ，t h e nl a y e r sw i d t hi sd e t e r m i n e d a c c o r d i n gt o t h es i t u a t i o no fa i r c r a f t c a r g oh o l d o ru l d sd y n a m i c a l l y , l a s t 2 - d i m e n t i o nl o a d i n gm e t h o d sa r eu s e dt of i l lt h el a y e r 2 dp a c k i n ge m p l o y st w ok i n d s o fh e u r i s t i c s ：o n ei sf i n d c o n t o u ra l g o r i t h m ，p a c k i n gs p a c ei sc o m p o s e do fas e r i e so f c o n t o u rl i n e s ，i tg e n e r a t ep o s i t i o n so fc a r t o n s ，c o m b i n ea n dd e c o m p o s ec o n t o u rl i n e s i nt e r m so fh e u r i s t i cr u l e s ；a n o t h e ri ss t r i p - b u i l da l g o r i t h m ，p a c k i n gs p a c ec o n s i s t so f h o r i z o n t a lo rv e r t i c a is t r i p sw h i c hw i d t hi sd e t e r m i n e db yh e u r i s t i cr u l e s ，t h e np a c k s i t e m si n t os t r i p sw i t hk n a p s a c ka l g o r i t h m t h ef o r m e ra l g o r i t h mc a t e r s f o r w e a k l y - s t r o n g l yh e t e r o g e n e o u si n s t a n c e s ，a n dp r e s e n t sl o wc o m p u t a t i o n a lt i m ea n d s p a c e ，w h i l et h e l a t t e rc a np e r f o r mm o r eo p t i m a ls o l u t i o n sf o rg e n e r a lw e a k l y h e t e r o g e n e o u si n s t a n c e s ，b u ts p e n d sm u c ht i m ea n ds p a c ec o s t w a s t es p a c ei s d e c r e a s e db yh e u r i s t i cr u l e s ，b o t hs p a c ea n dw e i g h tu t i l i z a t i o na r et a k e ni n t oa c c o u n t t h ep a c k i n gs h a p ec a t e r sf o rc a r g oh o l d s c o n t o u rp r e f e r a b l y , a n da c h i e v e sm o r e o p t i m a ls p a c e a n dw e i i g h tu t i l i z a t i o n ，i tp r o v i d ean e wa p p r o a c hf o rw e e k l y h e t e r o g e n e o u sp r o b l e m s c o m p r e h e n s i v et e s t sp r o v i d eam o r ed e t a i l e da n dp o w e r f u lp i c t u r eo fg u i d i n g p r a c t i c a ll o a d i n gw o r k t h es o l u t i o n o fn u m e r i c a le x a m p l e sc o m p a d n gb y o t h e r c l a s s i ca l g o r i t h m ss h o w st h a t t h i sa p p r o a c hi sm o r ee f f e c t i v et h a no t h e r s k e yw o r d s ：h e u r i s t i c ，l o a d i n g ，p a c k i n g ，b u i l d u p b u l k ，u l d 中同民航大学硕l 学位论文 中国民航大学学位论文独创性声明 本人声明所旱交的学位论文是我个人在导师指导下进行的研究：i ：作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中国民航大学或其它教育机构的学位或证持而使埘过的材料。与我一同：i ：作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：丕嚏互查 日期： 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件 和电子文档，可以采j j 影印、缩印或其它复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被壳阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权中国比航大学研究生部办理。 研究生签名：三鉴勉 导师签名 中国民航人学硕 ：学位论文 1 1 课题背景 第一章绪论 航空运输有其局限性，主要表现在：飞机货舱容量有限，对大件货物或大批量货物 的运输有一定的限制。目前，国内航空公司的飞机以中小型为主，以波音7 5 7 机型为例， 即使其4 个货舱全部装满，也只能载l o 多吨，运力跟中型卡车差不多。所以，如何在 飞机有限的空间里，尽可能多的装入不超过飞机限重的货物，以降低货物运输的单位成 本，提高运输经济效益，是一个很关键的问题。 出港货物组装与装机流程如图1 - 1 所示，货物装载操作主要发生在出港流程中，包 括内场( 库房) 货物组装，外场( 机坪) 装机组装。在组装宽体客机货物时，首先由搬 运人员把货物按照一定要求仔细码放在集装器内，然后牵引车司机把集装器拉到飞机货 舱下，再由外场平台车把集装器抬升到飞机货舱门口，最后由货舱内的机械动力装置辅 以人力把集装器放到指定舱位，此情况下组装工作量主要在内场：在组装窄体客机时， 窄体客机货舱既容不下集装器也无机械动力装置，故组装工作量主要在外场，内场搬运 人员按照配载人员的要求把不同舱位的货物放入不同的拖斗中，再由牵引车司机把拖斗 拉到机下，最后由外场的装卸人员钻进窄小的货舱内手工码放。 中圆民航人学硕十学位论文 图1 - 1 出港货物组装装机流程图 组装与装卸中的装机操作属于装载问题。表1 - 1 和表1 2 是某航空公司内场航班组 装和外场装卸的资源统计表，可以看出，工人把大部分时间、人力都用在了装载工作中。 因此我们需要研究货物智能装载系统，辅助制定可行的装载方案，虚拟出装箱过程，提 高运输工具装载率，降低运输成本，避免手工重装，为货运装卸提供决策支持。这就是 本课题的出发点和着眼点。 表1 1 内场航班组装资源统计表 序呼t 作名称t 作所用时问( 分钟) t 作所用人数前序t 作 1 拿颅舱单lt 人l 2容器准备 3 1 0t 人11 散斗：3 0 - 4 0 吨工人1 3组装集装：3 0 - 4 0 p 6 p下人31 ，2 2 0 a k e t 人2 教斗：1下人1 4封闭容器集装：5 i 6 pt 人2 3 3 i a k e t 人1 2 5汁蓖l o 1 5拖乍州帆13 ，4 6艴币记求1丁人1 3 7送交接甲lr 人15 中同民航人学硕l 学位论文 表1 - 2 外场装卸资源消耗表 序口t 作名称t f f 所用时问( 分钟)t 作所用人数前序t 作 调度r 解班组人员、航班动态， i接收电脑信息派1 =5工人1 机位 2接收出港派t 小单 5工人1 网i ： 班k 接到派t 4 , 单工人1 r 解进出港货量大小安捧人 32 0 组织人员找货拖车司机1员，提j d f 小单找货 工人1 通过电脑矗询：贵重物品、鲜活 4 串货并预备设备 2 5 拖车r j l 机1危品，并作记录，通知班组 2 0 ( 窄体)工人1 5拖货到机下 填开拉货单并登记 3 0 n ) t h e n 输出结果r e t u r n e n d i f f o ri = 1 n 记录节点i ； i f ( c o n s t r a i n t ( t ) & & b o u n t ( t ) ) t h e nb a c k t r a c k ( t + 1 ) e n d i f e n d f o r e n d 在解空b j 树时，用两种策略来避免无效的搜索，提高搜索效率。其一是用约束函数 ( c o n s t r a i n t o ) 在扩展节点处剪去不满足约束的子树；其二是用限界函数( b o u n t o ) 剪去不能 得到最优解的子树。 0 i 0 00 i 0 i o i 鳘i2 - 1 解空间树 如图2 1 所示，解空间树是一个满= 叉树，满足条件记录l ，反之记录0 。 2 3 算法应用 中固民航人学硕十学位论文 r w ： 剩余货物重量之和 九，： 剩余货物体积之和 c w ：已装货物重量之和 c v ： 已装货物体积之和 b w ：当前最优总重量 咖：当前优总体积 因为货舱有弧度，在这个弧面上磊放货物，实际占用的体积会比理论的大，所以给 出的货舱体积v 比实际的体积要小1 0 。为了使所装货物的体积重量达到最优，一方面， 我们应该找出使货物的平均密度最接近标准密度( 货舱限重货舱体积) 的组合；另一方 面，我们要避免最接近标准密度的货物组合的体积或重量远低于货舱装载能力的情况， 也就是说避免这种情况：货物还没有装满，他们的平均密度已经是最优的了。因此，我 们在更新最优解的时候，首先判断当前体积和重量是否大于最优解的体积和重量，如果 是，就更新当| j 情况为最优解，而不用考虑当前货物的平均密度是多少，如果不是，再 去考虑平均密度。 2 3 1 一个舱，不允许分批 这种情况处理比较简单，可以用o 背包算法解决。因为货物不允许分批，所以解 空间树每一个节点代表一票货物，只要其左儿子节点是一个可行节点，就进入其左子树。 当右子树可能包含最优解时才进入右子树搜索，否则，将右子树剪去，这个任务是由上 界函数完成的，当： c w + r w b w a c l p + r v s b v ( 2 7 ) 时，可减去右子树。 由于计算上界函数需要o 伽) 时间，在最坏情况下有0 ( 2 4 ) 个右儿子节点需要计算上 界函数，故此种情况该算法时阃复杂度为o ( n 2 ”1 。 2 3 2 二个舱，允许分批 这罩需要考虑：为了达到优化配置可以将一票m 个货物分丌装在2 个舱罩。因为 允许分批，所以解空间树每个节点代表以一个货物，而不是一票货物。按照下面的策略， 可以得到一个较优解：首先选出载蘑量最大的一个舱，使之利用率最大化，然后再优化 第二个舱。 首先找出载藿最大的舱，记为1 ，约乘函数的约束条件为： c v + v ，s uac w + ms 彬( 2 8 ) 中国民航人学硕 ：学位论文 限界函数的限界条件为： 洲+ r w 五b w a c v + w b v ( 2 9 ) 判断是否为最优解： ( c h ，乏b w a c v 却) v ( ( c h ，b w v c v a b v ) a i c w c v 一嘶v , l a l b w b v 一暇kd ( 2 1 0 ) 当舱1 优化完毕之后，可以按照类似的算法优化舱2 。对于剩下的货物可以由下一 个航班运送。 如果每一票货物的件数很多，其二叉树的节点数目是可怕的，这就需要做出改进。 如果货物的尺寸很小，如手机盒，为避免时间复杂度指数爆炸，可以把第i 票货物分成 m f 组，每组货物体积m ；v i ，重量是m w i ，则解空间树的结点数目可以减少到22 ：“个。 如果货物尺寸比较大，不利于组合，可已先把此票货物刨除在外，最后再处理它。 2 3 3 二个舱，最多一票货物分批 这种情况是最常见的，如果允许大量多票货物分批，那么对于发货收货和交付是很 麻烦的，所以最多允许一票货物分批是很现实的。按照下面的策略，可以得到一个近似 最优解：首先选出载重量最大的一个舱，使之利用率最大化，然后把没有完全装入第一 个舱的那票货的剩余部分全部装入第二个舱，再把剩余的货物按2 3 1 节的方法放入第 二个舱。 首先找出最大舱1 ，设： 朋： 一部分已经装入1 舱的货物要装入2 舱的那部分体积和 ，h ，：一部分已经装入1 舱的货物要装入2 舱的那部分重量和 则约束函数的约束条件为： 洲+ m 嵋a c v + v is ka 驯s 矸，2a s v s 哆 限界函数的限界条件为： c w + m b w a c v + n ，b y 判断是否为最优解： ( 2 1 1 ) ( 2 1 2 ) ( c w 2 b w a 卯z b v ) v ( ( c ，b w v 删芑b v ) a i c w c v 一暇v l l 剖b w b v 一嵋k i ) ( 2 1 3 ) 当舱1 优化完毕之后，因为已经先行判断了刚= w 2 = v 2 ，所以把那些没有完全装 入第一个舱的货物的剩余部分全装入第二个舱更新第二个舱的当i i i f 货物的重鼍之和c w 和当前货物体积之和c v ，再把剩余的货放按照2 3 1 的方法选入第二个舱，如果还有载 量和空日j ，找出剩余货物中密度最接近于平均密度的那一票货，能装多少装多少，这样 就选出了需要分批地郧一票货物。 中国民航人学硕 。学位论文 2 3 4m 个舱，最多一票货物分批 反复用2 3 1 和2 3 - 3 的方法，即可得到近优解。 2 4 算例 设有如表2 - 1 的货物，要装入波音7 5 7 2 0 0 型飞机的三四舱中，舱位情况见表2 2 。 表2 - 1 货物情况表2 2 货舱情况 票 体积( m 重晕( k g )件数 lo 0 6 42 01 0 0 2o 8 85 02 0 3 0 1 22 55 0 4 0 0 4 61 02 0 50 0 25 82 0 6o 0 7 51 52 0 7o 11 52 0 80 5 51 42 0 90 6 8 1 4 2 0 1 00 0 8 21 5 6 0 总6 4 3 46 6 2 63 5 0 l 舱位 体积( m 限重( k 9 1 h 31 83 8 0 0 ih 4 1 23 0 0 0 i 总计 3 06 8 0 0 因为货物件数很多，把每一票1 0 件货物合成一大件，如：第一票货物合成后有1 0 大件，第二票有2 大件。 2 4 1 允许多票货物分批 表2 - 33 4 1 货物分舱情况 l 舱位 票1票2票3票4票5票6票7票8票9票l o h 4 4 0 o5 01 02 0 2 0 2 0 0o6 0 h 35 01 00000ooo0 l 剩 1 01 001 0 00 o 2 02 00 表2 _ 42 4 1 舱f i ) = 利j l j 情况 舱位 体积( n f )体积利_ | f 率( )重鼙( k g )载重利_ 【 j 率( ) j h 41 7 8 49 93 7 6 69 9 h 31 21 0 01 5 0 05 0 2 4 2 最多允许一票货物分批 先装4 舱，把没有完全装入4 舱的那部分货物，企装入3 舱。 表2 52 4 2 货物分呛情况 l 舱协票1祟2禁3 禁4 祭5祭6禁7 票8 禁9巢l o h 44 0o5 01 02 02 02 0o06 0 h 36 0o01 0000 1 00 0 中田民航人学硕卜学位论文 表2 - 62 4 2 舱位利用情况 l 舱位 体积( m 体积利用率( )重培( k 9 1载重利_ l 率( ) h 41 7 8 49 93 7 6 69 9 h 3 9 88 21 4 4 04 8 5 中国民航人学硕l ：学位论立 分。 第三章二维装载 二维装载在航空货运领域应用范围不大，但本章所讲内容是三维装载的重要组成部 3 1 模型建立 模型建立的假设同2 1 节，设容器( 矩形) 的高、宽、限重分别为h ，w , l w ，把高、 宽、重量分别为h i , w i , w e i i 的n 个矩形放入容器中，放置时矩形各边均要与容器各边平行 且互不重叠，使容器的面积利用率或载重率最大，数学表达如下： ， 目标： m a ) ( 啊m h w 0 1 m a x m f j ( 3 1 ) ， m a x w e i i i e l ( 3 2 ) 约束：0 s 墨s w m f ， ( 3 3 ) o y f h - h i i e l ( 3 4 ) y 慨s l w i e l ( 3 5 ) o 以下四个不等式至少成立一个： x i + s 并， f ， ( 3 6 ) x i + w i x i i ，j lq y j + h i 墨y ff ，j j ( 3 8 ) y j + j l s 乃f ，j e i ( 3 9 ) 其中，为放入容器内的矩形集合，( x , y ，) 为第i 个箱子左下角在容器内的坐标，不等 式3 3 和3 4 约束了布入的矩形都在容器内，不等式3 5 约束了布入矩形的总重量不超过 容器限重，不等式3 6 至3 9 分别说明了“两个矩形在容器中可能的左、右、上、下的 空间关系，约束着两个矩形不相重叠。 3 2 等高线填充法 壤_ r 等高线的二维布局方法，如图3 1 所永，秆l 线部分为等高线，该- 维如局平面 白入t a ( 2 5 ，6 ( ) ) ，b ( 4 0 ，1 0 ) ，c ( 1 0 ，4 0 ) , d ( 5 ，2 0 ) ，e ( 2 0 ，1 5 ) f ( 1 0 ，1 5 ) , 9 0 0 ，1 5 ) 7 个雄! 形之后，产生了 中国民航人学硕 。学位论文 标识为纠月，c , d , e 的5 条等高线，其中彳月，c p 这4 条等高线分别f l = i a 2 , ，c , d 这4 个矩形单独产 生，等高线e 哇豫这2 个矩形共同产生，而后按照某种规则在等高线上放置矩形，就产生 了布局方案。这里的示意图横轴代表宽，纵轴代表高。 ：三乏乏五一 图3 1 等高线法 等高线类结构如下表示： s t r u c tc o n t o u r l i n e t y p e ls t a r t x ：。 等高线左端点x 坐标 r 1 广丁f 一 图3 2 确定矩形位置 t y p e ls t a r r y ；等高线左端点y 坐标 t y p e lw i d t h ： 等高线的宽度 ； 如图3 1 所示，等高线爿声，c p 捌的s t a r t x ，s t a r t y ，w i d t h 值分别为( 0 ，6 0 ，2 5 ) ，( 2 5 ，1 0 ，4 0 ) ， ( 6 5 ，4 0 ，l o ) ，( 7 5 ，2 0 ，5 ) ，( 8 0 , 3 0 ，2 0 ) 。 矩形( 盒子) 类结构为： s t r u c tb o x t y p e ld e m 2 】； ，矩形边长 t y p e 2w e i g h t ： 矩形重量 t y p e lp o s x ： 矩形左下点x 坐标 t y p e lp o s y ； 矩形左下点y 坐标 t y p e 3v a l u e ： 矩形的价值 因为矩形类各个成员鬣纲不同，故各个成员变量应该用不同的类型，通常情况下 t y p e l ，t y p e 2 ，t y p e 3 类犁如下： t y p e l ：b i g i n t e g e r 毫米 i n t e g e r厘米 f l o a t米 柏 抑 m 0 卯 棚 加0 中国民航人学碘_ i 学位论文 t y p e 2 ：i n t e g e r 公斤 f l o a t吨 t y p e 3 ：d o u l b e 矩形类中没有单独表示旋转的成员变量，本文约定d e m 0 所代表的边水平放置( 与 x 轴平行) ，d e m 【1 】所代表的边竖直放置( 与y 轴平行) 。开始时d e m 【0 】，d e m 【1 1 按照初始 情况赋值，产生布局方案时，如果矩形需要旋转，则交换d e m 0 与d e m 1 的值即可。 矩形的价值由空间价值和重量价值两部分组成： v a l u e 一口s p a v a l + ( 1 - a ) w e i v a l( 0 s a s l ) ( 3 i o ) 矩形的空间价值评价方式可以有多种，最常见的3 种是： ( 1 ) 价值为矩形的最长边； s p a v a l l - m a x b o x , d e m o ，b o x 3 e m 1 ( 3 1 1 ) ( 2 ) 价值为矩形的面积； s p a v a l 2 - b o x d e m o 。b o x , d e m 1 ( 3 1 2 ) ( 3 ) 价值为矩形的周长。 s p a v a l 3 - 2 ( b o x d e m o + b o x d e m 1 ) o 1 3 ) 矩形的重量价值评价方式只有1 种： w e i v a l b o x w e i g h t ( 3 1 4 ) 两种价值的量纲不一样，数值差异很大，需要把两种价值都标准化为0 - 1 之问的数， 设矩凭i 的空间价值、重量价值、整体评价值分别为印口阳0 ，w e i v a l j ，v a l u e l ，矩形价值计算 方式如式3 1 7 ： s s p a v a l ， ( 3 - 1 5 ) 毗一as p a r v a l j + ( 1 - 砂警陋叫 3 2 1 基于选择最佳适配矩形的方法 ( 3 1 6 ) ( 3 1 7 ) 基f 选择最佳适配矩形的疗法：首先选出将要被布局的等高线空间，然后选择最适 合此等商线窄f 、口j 的矩形进行地危，再对无效等岛线进行俞j f ：、删除等操作，这样j 互复操 作，“纠庀“r 用等i f j 线或无j 川甜! 彤为i ：。 fwdm 。y 角 l 2 s 中国民航人学硕十学位论文 3 2 1 1 选择等高线 设c ，为等高线，m 为等高线个数，有两种选择等高线的方式： ( 1 ) 选择最左等高线，选择布局空间中最左边的等高线： s e l e c tc lic 1 s t a r t x = m i n c l i s t a r t x i = 1 ”肼 ( 3 1 8 ) 如图3 - 1 ，等高线从左往右依次是a 口，c p 正，该策略选择等高线a 。 ( 2 ) 寻找最低等高线。选择布局面空自j 中高度最小等高线， s e l e c tc lic 1 s t a r t y = m i n c l i s t a r t y i = 1 ”伽 ( 3 1 9 ) 如图3 - 1 ，等高线按高度升序排列为b p 厶c 1 ，该策略选择等高线b 。 3 2 1 2 计算矩形适宜值 选择什么样的矩形放入当前等高线所构成的空间效果会最好呢? 可以遍历各个待 布矩形，并进行旋转，选择一个适宜值最大的矩形放入当前等高线空间中。因为现阶段 是二维布局，所以只有一种旋转情况，即矩形在该二维平面作9 0 度转置。设h i 盼 别为当前二维布局空间的宽、高、限重。 矩形对等高线所产生空间的适宜值由空间适宜值和重量适宜值两部分组成： f i m e s s - a s p a f i t + ( 1 一口) w e i p t ( 0s 口s1 )( 3 2 0 ) 其 o s ；a p t 为空白j 适宜值，w e i f i t 为载重适宜值。矩形的空间适宜值，可以由以下几种方 式计算： 印a p f i 。1 一b o x d e m o o ri 一b o x d e m 1 ( 3 2 1 ) c 1 w i d t hc 1 w i d t h 聊疗t21一(c1width-boxzlemo)(h-c1starty-box。lem1) 一 。f 础 饵一。，肋r t y ) ( 3 2 2 ) o rl一(c1width-boxzlem1)-(h-c15tarty-boxzlemo) 、 c 1 w i d t h ( 月一c 1 s t a r t y ) s p a p t 3 - c 1 w i d t h b o x z l e m o 】o rc 1 w i d t h - b o x z l e m 1 】( 3 2 3 ) 职肛4i ( c ，w 蝴一6 似矗绷【o 】) ( 日一。f 砌哪一胁砌l 【1 】) o 2 4 ) o r ( c 1 w i d t h - b o x z l e m 1 ) 。f 日- c 1 s m r t y - b o x d e m 0 1 ) 、 s p a t5 ；b o x d e m 0 1o rb o x d e m 1 】( 3 2 5 ) 其中妒妒，即可z ，即妒，考察矩形对锋商线所在空问的宽度适宜性，妒妒，即妒，考察矩 形对等高线所在空i 日j 的二维适宜性。s p a f i t 。即妒f 2 即妒r 5 值越大则甜，形的适宜性越优 妒妒f j 即哆7 i f 4 的值越小则矩形的适i = ：怍越优，冈为窄刚适宜值要与载霞适宜值相加，而 载重适幽：值越小表爪甜一形的通i i ：住越簟，赫l s p a f i ? , s p a f i t 4 适用f ：单独评价。s p a f i t 7 j s p a f i t 5 中固民航人学顾e 学位论文 本质是一样的，标准化后的结果也是一样的， 上的开销。矩形的重量适宜值如下计算： w e i p t b o x w e i g h t 用计算，节省了算法在时问、空间 ( 3 2 6 ) 设射个矩形的空间、载重适宜值分别为印确，p 锄，重写式3 2 0 ，, 1 , f i t n e s s j ： 墨善蝴， ( 3 2 7 ) 跏善聊弘， 廊倒，孚+ ( 1 - 砂警1 ) 如果存在两个以上矩形的适宜值相等，则可以如下考虑： ( 1 ) 选择面积最大的矩形； ( 2 ) 选择最长边最大的矩形； ( 3 ) 选择周长最大的矩形。 3 2 1 3 选择最佳适配矩形 ( 3 2 8 ) 0 2 9 ) 选择最佳适配矩形的流程如图3 3 所示：首先判断矩形重量是否在当前容器可承载 重量范围之内，如果不能则抛弃该矩形，否则旋转矩形各边，判断能否放入当前等高线 空自j 内，如果不能则抛弃该矩形，否则确定该矩形最佳旋转方式( 矩形旋转后的空间适 宜值用s p a f i t ( b o x ，1 ) 表示，反之用s p a f i t ( b o x ，o ) 表示) ，并把它插入到当前可行矩形表术尾， 所有可行矩形都确定后，标准化各个矩形的s p a f i t , w e i j l t 值，并按照3 2 9 式计算一加 s 值， 最后选, q 4 , f i t n e s s 值最大的矩形作为放入当前等高线空间内的最佳适配矩形。 中国民航人学硕i 学位论文 输入待布奸形表：o p e n b o x l i a t 输入布局守问高，限重：h 工 输入、前等高线：f ， 3 2 1 4 处理无效等高线 图3 3 筛选最佳适配矩形流程幽 如果某一等高线的宽度不足以放下任何一个 布矩形，则此等高线为无效等高线。 判断的流程见本节算法整体流种图3 2 0 。埘无效誓高线的处理方式有合并，等待、删除 j i 种。 中国民航大学硕l 学位论史 3 2 1 4 1 合并 可供选择的方式无外乎有两种：跟左面的等高线合并或者跟右面的等高线合并。设 c ，l 为c f 的左邻等高线，c f 2 为c ，的右相邻等高线，如果： c 1 f t a r t ysc 1 1 f t a r t y c 1 s t a r t y5c 1 2 f t a r t yac 1 1 1 t a r t y c 1 2 z m r t y ( 3 3 0 ) 那么c 疆艮c b 合并。如果： c 1 s t a r t y c 1 1 s t a r t y c l j t a r t y c 1 2 s t a r t yac l l j t a r o , c 1 2 s t a r t y( 3 3 1 ) 那么c f 跟c 1 2 合并。也就是说如果c ，的高度小于d l 与c j 2 的高度，那么c 腥艮c ，, c l z 中高度小者 合并。如图3 1 ，假如每一待布矩形的边长( 宽或者高) 都大于等高线d 的宽w i d t h ) ， 则按照上述规则应该把d 跟e 合并，显然d 跟c 合并极不合理，合并后效果如图3 4 所示， 阴影部分为合并的空间，此时更新等高线： e s t n r x t = d 5 “i r 臼c e w i d t h = d w i d t h 把w i d t h ( 3 3 2 ) 并从等高线表中删除d 。 3 2 1 4 2 等待 在实际布局中容易产生这样一种情况：无效等高线的高度至少比一个相邻等高线的 高度大即满足： c 1 s t a r t y c f l z t a r t yvc 1 s t a r t y c 1 2 s t a r t y( 3 3 3 ) 如图3 4 所示，假如c 是无效等高线，且高度比占和e 都要大，那么应该一直等待，直到两 侧的等高线的高度都超过了c 的高度，再进行判断、合并，显然如果现在就和等高线君五 中的个合并是不合理的。 abd f d b 吲3 - 4 合并无效筲南线蚓3 5 无效苫高线 中固民航大学硕卜学位论文 3 2 1 4 3 删除 此时，无效等高线情况有两种：一种为无邻无效等高线，另一种为已经到达布局空 间顶端的等高线。如图3 5 所示，c 属于静一种前情况，a 声p 属于后一种情况，此时它 们已经没有任何用处了，应该删除。 ( 1 ) 无邻等高线，当前等高线c 眼口没有左邻等高线也没有右邻等高线，假设d 3 , d 4 是 离c f 最近的两条等高线，即满足： ( c 1 t a r t x c 1 3 胁，肛+ c 1 3 w i d t h ) i t ( c l s t a r t x + c 1 w i d t h 0 则会产生新等高线c f ，c ，成员变量如下赋值： c l s t a r t x c 1 ，t a r t x + b o x z t e m o 】 c l s t a r t y - c 1 s t a r t y c 1 w i d t h - c 1 w i d t h - b o x 3 e m 0 】 并把c ，插入到等高线表等高线c 垢面。 3 2 1 5 2 动态放置 动态决定矩形是放置在左边还是右边。如果矩形放在右边， 成员变量赋值为： b o x p o s x c 1 s t a r t x + c 1 w i d t h - b o x , d e m o 】 b o x p o s y c l a t a r t y 当前等高线c 服! 新为： c 1 s t a r t x c 1 1 t a r t r + c 1 w i d t h - b o x d e m o 】 c 1 s t a r t y - c 1 s m r t y + b o x d e r a i l 】 c 1 w i d t h - b o x 3 e m o 】 如果： c 1 w i d t h b o x z t e m 0 1 0 则会产生新等高线c f ，c f 成员变量如下赋值： c l s t a r t x c 1 s t a r t x c l s t a r r ytc l j m r t y c l 。w i d t h = c 1 w i d t h - b o x x l e m 0 】 并把c f l 插入到等岛线表中等高线c ，的f j i 面。 矩形的动态放胃方法由以下三种情况确定： ( 1 ) c l l c 1 2 都存在； 如粜： ( 3 3 7 ) 则此袒形6 甜位置坐标 ( 3 4 1 ) r 3 4 2 ) ( 3 4 3 ) 中固民航大学颂i + 学位论文 i c l s t a r t y + b o x d e m 1 - c 1 1 s t a r t y i 司c 1 s t a r t y + b o x z l e m 1 - c 1 2 s t a r t y i( 3 4 4 ) 那么矩形b o x 应该放置在c f 的最左边，否则，应该放胃! 在c f 的最右边。如图3 2 ，假如 需要把矩形f ( 2 5 ，2 5 ) 放在等高线b 所构成的空间中，经过计算1 1 0 + 2 5 6 0 1 1 1 0 + 2 5 - 4 0 1 ， 因此把f 放在目的右半部分。 图3 - 9 b 无右邻等高线图3 1 0 a w i d t h 1 1 w i d t h ( 2 ) c h 存在，c f 2 不存在； 如图3 9 ，等高线口的左邻等高线是一，它的右邻等高线不存在，假设此时要命入矩 形口，若a w i d t h b w i d t h ，无论a 靠右还是靠左放置，都会在原等高线曰的高度上产生新的 等高线口l ，c ( 如图3 1 0 所示) ，则有如下情况： 图3 1 1 盒子口靠右放置图3 1 2 盒子a 靠左放置 1 ) 新等高线c 是无效等高线，新等高线口l 高于等高线4 ； 那么矩形应该靠右放最，如图3 1 1 所示，这样等高线c 可以和等高线一合并， 扩展了等高线，萱，以使下次操作时爿可能恰好放入最佳适配矩形b 。如果矩形a 靠左 放置，由于c 是无效等高线，c 需要和口l 再次合并，合并后曰。的宽度与装入矩形a 之前等高线口宽度相同，若此时再要填入矩形c ，由启发式规则确定将要填入该等 高线的矩形的宽度可能不会优于前次填入的矩形a ，把c 靠左放置，会产生新的等 高线口2 和c 1 ，如图3 1 2 所示，如果c l 还是无效等高线，仍旧要被合并，这样往复 循环，那么等高线引均右侧空间可能永远无法利用上。 2 ) 新等高线c 是无效等高线，新等高线且l 不高于等高线，4 ； 如图3 1 3 ，因为无论矩形a 怎样放置，c 都需要与b ，合并，所以矩形口既可以 靠庄放胃也可以靠右放置。 中圉民航人学硕卜学位论文 图3 1 3 曰1 不高t - a ，c 为无效等高线图3 1 4 口1 高于爿，c i 最低 图3 - 1 5 丑i 高于，c l 适中 图3 - 1 6b i 高于以，c t 最高 3 1 新等高线c 非无效等高线，新等高线口。高于等高线爿； 假设此时恰好布入矩形c ，产生新等高线c ，分三种情况： 等高线c 。的高度低于等高线一和历的高度，如图3 1 4 所