（系统工程专业论文）多形态不规则货物混合装载优化问题研究.pdf

山东大学硕士学位论文 摘要 货物装载是物流配送的重要环节，其方案的优劣对提高整个物流系统的效率 和降低运输成本都有着重大影响。装载优化问题已经日益受到物流实业界和学术 界的重视，然而目前的研究大都集中在规则矩形体货物的空间布局上，很少有人 对不规则非矩形体货物的布局问题进行深入的研究。对物流配送而言，货物的形 状千差万别，存在很多不规则非矩形体的情况，而已有的装载优化研究成果很难 应用于这些不规则货物的装载中。因此，研究不规则非矩形体货物的合理布局方 法，对提高装载容器的空间利用率有着极其重要的理论和现实意义。 本文着重对物流配送中不规则非矩形体货物的装载进行优化研究，采用两步 法，提出了一个合理的布局及装载方案，以提高装载容器的空间利用率。首先在 深入分析国内外现有对规则矩形体装载优化成果的基础上，构造启发式算法，提 出了将不规则的非矩形货物组合成近似矩形体的方法，包括单一型货物装载和混 合型货物装载时的各种组合方法，对比了各种组合方法的优缺点和适用背景；然 后用改进的遗传算法解决了规则矩形体及组合后的近似矩形体的布局优化问题。 在理论研究的基础上，本文对多形态货物混合装载优化系统进行了分析和设 计，并实现了该系统的优化计算和三维仿真。利用该软件，对烟草配送中用热缩 膜包装的条烟装载问题进行了大量的仿真实验，并对仿真结果进行了比较分析。 仿真结果表明利用该软件得出的装载优化结果高于人工装载率，即本文方法能有 效提高不规则货物的装载率。利用该系统，不仅可以得出高效的装载方案，还可 以给出直观形象的三维装载图。实验表明该仿真软件智能化较高、操作简便、实 用性强。 本文在不规则货物装载这一较新的研究领域进行了探索和尝试，研究结果对 实际装载作业提供了理论依据和技术实现手段，具有较强的指导意义，也为今后 该问题的迸一步研究提供了一种新思路。 关键词三维装载；启发式算法；物流配送；不规则非矩形货物；遗传算法 山东大学硕士学位论文 a b s t r a c t t h ec a r g ol o a d i n gi sa ni m p o r t a n tp a r to fl o 百s 虹d i s 砸b u t i o i l l h ep l 缸o f c a r g ol o a d i n gh 笛s i g n i f i c a m 砌u c e 血ee m c i c yo f1 1 1 e 虹l o 昏s t i d i s 仃i b u t i o ns y s t e m 锄dt h e 似i u c t i o f 呻o r t a t i c o s t t h el o a d i l l g 叩t i r n i 枷 p r o b l e ma l r e a d yr e c c i v e dt h ea t t 饥矗o no fl o 百s t i c sm d u s 仕y 姐da c a d e l n i cw o r l dd a yb y d a 弘h o w e v e r ，也ep r e s e mr e s e a r c h c o n c e 刀t f a t em o s n yo nt h es p a t i a ll a ) r 0 眦o f 坞g u l a r l yr e c t 锄g u l 缸c a 玛。髂，肌dv e r yf 鲁wp e 叩l ec d l l c t et h er e s e a r c ht 0m el a ) r o u t o f 如泔g u l a r l yn o n - r e c t a i l g u l 盯c a f g o 馏s p e a k i n go f t l l el o 百s t i c sd i s t r i b u d o i l ，t h es b 印铝 o f c a r g o 伪a 佗i n 丘n i t e l yv 暑l r i e d ，弛dt h e 盯em a n yi r ：g u l 础y n 假切n g u l a rc a r g o e s ， b u tt h e 既i s t i l 培l o a d i n go p t i m i z g d o n 瑚e 锄c h 他s u l t sa r ev e 搿d i 佑c u l tt 0b ea p p l i e di n t h c s e 如c g u l 盯c a r g o 髂l o a d i n 辱国地r c f o r c ，丘n d i n ga 船。舶：b l em e l l l o dt ol a y o u t 加g u l a r l yn o n r e c t a n g u l 盯c a r g o 鹤i sv 奶s i g n i f i c a n tf o rm i s i n gt h el o a d j n gf 撕 耽i sa r t i c l cm a i l l l yr e s e a r c h 韶t h e1 0 a d i n g 叩倒z a t i 咖b l e mo fi 玎e g i l l a r l y n _ r t 锄g u l 盯c a r g o 鼯i i lt h c1 0 舀s t i c sd i s 伍b u t i o i l ，a n dl l s e s 怕，o s t e ps t r a t e g i 髂t op r 叩o s e a a s o n a b l el a y o u ta i l dai o a d i n gp l 觚a i m i n gt o 舭em el o a d i i l gr a _ t eo f t h el o a d i n g v 韶s e l s f i r s t l y ，b 勰e do n 粗a l y z i n gd o m e s t i c 卸df 0 】商盟叩t i n l i z a t i o n l l i e 、，锄e n t so f 也er e 鲫a r l yr e c t 锄g u l 盯l o a d i n gp r o b l 锄，m i sa m c l cl 玛e sh e m i s t i ca 1 9 0 r i t h m st o p r o p o s es e v e r a im e m o d sb yw h i c ht h ei 玎e g u l 盯l y n d t a l l g u l a rc a r g o e sc 孤b e c o m b i n e di m oa p p r o x i m a t e l yr e c t a n g u l a rc 缸g o e s ，i i l c l u d i n gv a r i o 璐m e m o d so fs i l l 百e s h 印ec a r g o e s1 0 a d i l l ga i l di n u l t i s h 印ec a r g o e sl o a d i n g s e c o n d l y ，t l l i s 枷c l ed i s c l l s s e s t l ! 幢a d v a n t a g e s ，d i s a d v a n t a g e s ，a 1 1 d 印p l i c db a c k g r o u n do fe a c hk i n do fc o 硎b i 彻矗o n m e t h o d s f 卸a 1 1 y ，t l l i sa r t i c l ei m p m v e sg c l l e t i ca l g o r i t h n l t os o l v et h e l a y o u t 叩血血z a i i o np r o b l e mo f r e g l l l a rr e c t 蛆g i i l 盯c a r g o e s b e s e do nt 1 1 et l l e o r yr e s e a r c h ，t l l i sa n i c l ec a r i i e so n 也ea l l a l y s i s 孤dt h ed e s i g nt om e 皿l l 在一s h a p ec a r 9 0 e sl o a d i n go p t i 玎1 i 2 州o ns y 8 t 锄，a n dr e a l i z e sm ec o m p u t a t i o n 觚dn l e t h r e ed i m c l l s i 伽a ld 锄。璐臼a t i o n u s i n gt l l i ss o 脚a r e ，m 船s i v es i m u l a t i o ne x p e r i m e n t s t ot h eb o x 船o ft o b a c c ow h i c hi sp a c k c dw i 也p y r o c o n d e i l s a t i o nm e 玎1 b r a n ea r cc 枷e d o 越锄dt h es i m u l a t i r 髓u l 协a c o m p 盯c d 缸da n a l y z e d n es i l n l l l a t i o nr e s l l l t s i n d i c a t et 1 1 a tu s i l l gt l l e1 0 a d i n g0 p t i i 】越z a t i o np l a nc o n c l u d e d 丘d mm i sp r o 乒a mc a i lm a k e ah i 曲c r1 0 a d i n gm t e ，n 锄e l yt l l ea l g o r i t h m sp r o p o s e di i lm i sa n i c l ec a i le f r c c t i v e l y e i l h a l l c em el o a d i n gr a t eo f i r r c g i l l a r l y1 1 0 n j 僦t a i l g i l l a rc a r g o e s u s i n gt 1 1 i sp r o 酗m ，n o t i i i 山东大学硕士学位论文 o n l ym a yo b t a i nt l l eh i 曲l ye 腩c t i v el o a d i n gp l a n ，b u tm a yo b 翻nt h e 衄d i m e 哪i o n a l i m a g eo fl o a d i i l gp 1 弛t h es 证l u l a t i o nr e s u l t sp r o v et 1 1 a tm i ss i m u l a t i o np r o 孕a mh 私t l l e u s a b i l i t y 孤di n t e l l i g e n c e ，粗dc a nb eo p e r a t e de 弱i l y t h i sa r t i c l ec a r r i e so nt h ee x p l o r a t i o na n dt h er e s e a r c hi nt h en e w d o m a i n o ft h ei r r e g u l a r l yn o n r e c t a n g u l a rc a r g o e sl o a d i n go p t i m i z a t i o n ， a n dt h er e s e a r c hr e s u l t sp r o v i d et h et h e o r yb a s i sa n dt h et e c h n i c a l r e a l i z a t i o nm e t h o d st ot h ea c t u a ll o a d i n go p e r a t i o n ，s ot h i ss u b j e c t h a s s t r o n gg u i d i n gs e n s e ， a n dp r o v i d e san e ww a yf o r t h ef u r t h e r r e s e a r c hi nt h i sd o m a i n k e y w o r d s 3 dl o a d 址g ；h 即r i s t i ca l 剃1 m s ；l o 垂s t i c sd i s 缸i b u 石o n ；i r r c g i l l 盯l yn o n - r c c t a l l g u l 盯c a 培p ；g 锄e 石ca l g o r i t h m i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责 任由本人承担。 论文作者签名：陋 日 期：墨宣生乡 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文 和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) ：譬衅 山东大学硕士学位论文 1 1 课题背景 第l 章绪论 随着中国加入w t o ，对物流的需求日益旺盛，被经济学家和企业界称为 “第三利润源泉”的现代物流正在我国经济发展中起着越来越重要的作用。 然而，我国物流业发展与国外有较大差距。据悉，2 0 0 5 年，我国物流费用占 g d p 的比率为1 8 5 0 1 。有数据显示，1 9 8 2 年时，美国的物流费用占g d p 的 1 4 5 ，而现在降为8 ；欧洲的物流费用约占g d p 的l l 余。中国仓储协会 的一项调查显示，中国有4 5 3 的企业面临物流成本过高的压力。由此可 见，采取科学的措施，降低物流成本，已经成为企业发展的当务之急。 运输是物流的核心环节，在整个物流成本中占有很大的比例，是影响物流 成本的一项重要因素。因此降低运输成本能够有效地降低整个物流活动的成 本。运输成本与配送中心的选址，车辆调度、线路优化、运输工具的装载优化 等有密切关系，特别是运输工具的装载优化，是降低运输成本的关键。 在对多家物流公司进行实地调研之后发现：装载过程基本完全按照人工的 经验进行，搬运工人凭经验确定装载顺序，有时甚至随机的将货物装入车厢。 这种经验式的装载方式，往往使装载的货物杂乱无章、稳定性差，造成空间上 的浪费，增加了运输成本。经验式的装载效果如图l - 1 所示： ( a )( b ) 图1 1 调研的企业实际装载状况 在装载过程中，存在着大量的不规则形状的货物，即非矩形体货物，如家 山东大学硕士学位论文 具，汽车外壳、机器部件等。这些不规则体体积较大，无法将其用长方体的纸 箱进行包装，所以装载时若没有科学的方法进行布局优化，将很难保证空间的 合理运用，造成装载混乱。 因此，采用合理的装载方法，提高装载工具的空间利用率，是降低运输成 本、增加物流收益的重要途径。 1 2 装载问题简介 装载问题( 或称为剪裁与装填问题) ，是一种布局问题，通常是指在一种 材料上寻找各种形状的最佳布局以使材料的浪费率最小，或者描述为将若干小 的物体以最佳方式组合并装入一个大的空间从而使空间的利用率最大。1 。有时 还应满足一定约束条件，如冲载落料的不搭边要求，航空器的动平衡等等“1 。 由于布局的优化能够导致大量的材料节省、缩减产品的价值，而增加产品 工业的利润0 1 ，所以，布局优化问题是许多具有重要意义的实际优化问题的基 础删。比如，在建筑中经常需要从长度一定的棍子上切割不同长度的棒和管； 电气布线中的电线来自长度一定的线卷；贴墙纸需要从给定长度的纸卷中得 到；具有相同宽度、不同长度的石料需要用平板架运送到建筑工地；在金属制 造业中，钢片需要从大片钢片中切除。物品的尺寸不一定是几何尺寸。例如， 电子工业中不同长度( 字节) 的微代码程序需要存储至微处理器中具有固定容 量的存储器中；运输工业中卡车具有给定的最大承重，通常将不同负荷的重量 作为考虑对象；在娱乐工业中，歌曲集被发布在给定容量的媒质( 光盘、磁 带) 上；在作业管理中，不同执行时间的任务需要在满足完成所有任务时间限 制的前提之下被分配到不同的工人。以上皆是布局优化理论的实际运用。 由于应用领域不同，所求问题的目标和约束也是多种多样的。根据待布物 的形状、容器形状及装填方式，布局问题可以分为以下几种基本类型： 1 托盘问题口a l i e t1 0 a d i n g ) ：将许多较小的矩形物品排放到一个较大矩形 板材上，使其某一方面的性能达到最优，比如排放的个数最多。这是 立体货架、载货托盘上的货物摆放所面l 临的常见问题； 2 一刀切问题( g u i l l o t i n e ) ：将某些种不同大小的小矩形按照一刀切的原则 排放在一个大矩形板材上，使面积浪费最少，这是剪床落料、玻璃切 2 山东大学硕士学位论文 割、纸张切割中遇到的主要问题。所谓一刀切，是指切割总是从矩形 板材的一边开始一直切到其对边，即每切一刀都将一个矩形分割成两 个小矩形。这类问题往往根据每种小矩形的个数是否限定分为无约束 一刀切问题( 每种小矩形的个数无限) 和约束一刀切问题( 每种小矩形的 个数是给定的) ；， 3 二维矩形件布局问题( r e c t 孤g l ep a c 鲑n g ) ：将许多不同大小的矩形件排 放在一张或几张大的矩形板材上，使板材的利用率最高； 4 冲载件布局问题( m e t a ls t 锄p i n g ) ：将一种形状( 一般为复杂的不规则形 状) 的工件，按某种摆放方式等距连续的排放在一较长的带状板材上， 使材料利用率最高。这类问题是冲压落料中遇到的主要问题。根据冲 头数目，该问题可分为单排、双排及多排排样； 5 二维不规则图形布局问题i ：将许多任意形状、大小的图形排放在一 张或几张大的矩形板材上，使某种性能最优，一般为板材的利用率最 高，这是许多行业中经常遇到的问题，如服装剪裁的放样、机械行业 中的板材切割下料等； 6 二维不规则图形布局问题n ：将许多任意形状、大小的图形排放在一 张任意形状的不规则板材上，使板材的利用率最高，有时板材上还带 有不可利用的疵点，如皮革制品行业中的皮革落料问题； 7 三维布局i ：三维箱体布局，即将许多不同大小的待布箱体装入一长 方体容器中以使某一性能最优。如集装箱内具有长方体包装的货物的 装载； 8 三维布局：不规则三维实体的最优布局，即将许多任意形状、大小 和性能的三维实体摆放在一个任意形状、大小的三维容器中以满足某 些约束或使某一目标最优。如火箭仪器舱内的仪器布置等。 1 3 装载问题的相关问题 在装载问题研究中，有三个相关的布局问题，可以借鉴其他与之相类似的 装填问题所使用的研究方法。分别介绍如下： ( 1 ) 背包装入问题( k 【p s a c kp r o b l e m ) 山东大学硕士学位论文 背包问题是一个非常有名的问题。可以这样叙述如下。假设有一个容积为 b 的背包，n 个体积分别为q ( i = 1 ，2 ，n ) ，价值分别为c j ( i = 1 ，2 ，n ) 的物品。现在要求用这n 种物品的子集填满背包，使得背包的价值尽可能 高。模型表示为： 一善 1 ) i = 1 ( 1 1 ) “善郦6 ( 1 - 2 ) ，= i 【1 2 ) 一 o ，1 ) ( 江1 ，2 ，以) ( 1 3 ) 其中公式( 卜1 ) 欲使背包中所装物品的总价值最大；公式( 卜2 ) 为背包的约 束条件，使背包中所装入物体总长度不大于背包的长度；公式( 卜3 ) 表示五为 二进制变量，而= 1 表示第i 个物品装入背包，而= o 表示第i 个物品不装入背包 如果假设物体的利润等于他们的体积，该问题即变为一个求解装箱空间利用率 问题。 ( 2 ) 装箱问题( b i n p a c k i n g p r o b l 锄) 有一些( 可以看成是无穷多个) 尺寸或长度相同的箱子，设其长度为c ( c o ) 。现有n 个物体q ( i = 1 ，2 ，n ) ，每一种物品q 的长度为s ( q ) ， 且都小于等于箱子长度c 。寻找一种算法，使得可用最少数目的箱子将这些物 品全部装入箱中，且每个箱子中的物品长度之和不超过箱子长度c 。装箱问题 常见于一维与二维情形，就三维装箱而言与集装箱装箱区别不大。3 。 ( 3 ) 平板车装填问题( p a l l e t p a c k i n g p r o b l e m ) 平板车装载是将货物装在侧面没有遮挡或支撑的货盘上，装载货物的边平 行于货盘的边，物体之间互不重叠，而且物体装入的高度不能超过货盘限定的 高度，使得装载的空间利用率最大啪。托盘装载的最大特点是侧面没有遮挡或 支撑，货物码放时要考虑其稳定性从而保证货物不会从货盘上掉下来，而集装 箱装载不考虑这种约束。 4 山东大学硕士学位论文 1 4 国内外研究现状 目前的装载方法研究大部分是基于二维布局技术的，许多三维布局问题也 是通过分层应用二维技术来处理。由于三维布局问题的复杂性，在布局问题的 研究中，关于三维布局的研究是有限的，只有少许与复杂集装箱装载问题有关 的论述在目前三维布局的研究中，对规则矩形货物三维摆放方法的研究占 大多数，对不规则货物三维摆放方法的研究还很少。 1 4 1 规则装载问题的研究现状 规则装载问题的前提是货物和装载容器都是规则的矩形体，这种问题通常 称作c l p ( c o n t a i n e rl o a d i n gp m b l e m ) 问题。c l p 问题是一类组合优化 ( c o m b i n a t o 血1o p t i m 配a t i o n ) 问题，也是n p 一难问题“1 。c l p 问题的传统研究方 法有线性规划、整数规划、动态规划等传统优化方法，构造型启发式算法及智 能优化算法( 包括模拟退火算法、禁忌算法、基因算法) 等等。对于传统的优化 方法，由于解空间随着问题规模的增大呈指数倍数增长，会导致“组合爆 炸”，使问题难以求解。目前，国内外c l p 问题的研究成果主要集中在启发式 算法与智能优化算法方面，下面就这两方面成果分别论述。 1 4 1 1 启发式算法 所谓启发式算法即凭借实践经验建立直接的搜索策略和搜索规则，并以此 规则在搜索空间中求解。一方面由于启发式规则是根据实际问题建立的，具有 较强的针对性和一定的合理性，虽然无法保证得到最优解，但是通常可以得出 令人满意的可行解，另一方面由于构造型启发算法描述直观，易于实现，对于 具体装载问题的优化有很高的实用价值，因此目前大量的研究集中在这类算法 中，下面就几种有影响的算法分别进行介绍。 1 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 ( 以下简称g r ) 算法是影响最广的一种启发式算法。1 ， 主要解决可以按任意方向放置的多种物体装填问题。g r 算法有两个关键点： 一是层的划分，二是确定物体的装入优先级。其中层的概念对后来的研究产生 了很大影响。 该算法的基本思想如下：( 1 ) 将物体在深度方向分层填充，尽量使每一层 山东大学硕士学位论文 的外表面平整。装填的每一类物体都被赋予一个状态：打开状态( o p e n ) 或非打 开状态( u n o p e n ) 。如果某类物体中已经有物体装入箱体内，则标识该类物体为 o p e n 状态，反之标识为硼o p c i l 状态。处于打开状态的物体优先装入，通常选 取处于打开状态且没有装入箱体的物体数量最多的那类物体首先装填新层。 ( 2 ) 对处于非打开状态的物体设置优先级。首先对物体的长、宽、高三尺寸 中的最小尺寸进行排序，最小尺寸越大，物体级别越高。对于处于同一级别的 物体，按物体的数量进行分级，数量多者级别高。如果按前面两种规则进行排 序后，仍然有物体优先级相同，则按每一类物体的长、宽、高三尺寸中的最大 尺寸进行排序，尺寸越大，级别越高。( 3 ) 优先级确定后，按照构建层的方式 装填。优先级确定后选取优先级最大的物体作为装入的第一个物体。以后各 层，装入的第一个物体在处于o p e n 状态且数量最多的一类物体中选取，如果 没有处于o p 雠状态的物体，则按照物体优先级确定。 可以说以后涉及到分层的算法研究都是在g r 基础上进行研究探讨的。该 方法适用于弱差异情形。缺点就是每个物体都要逐一分析处理，会牺牲大量的 时间，算法效率较低；孤立的按照每个物体考虑，降低了装箱的效率。 2 b i s c h o f f m a r r i o t t 算法哺1 b 洲算法仍然是建立在层的基础上进行讨论的。该算法的构想是，先按照 某种标准确定物体的优先级，然后取出级别高的物体，分别尝试用它的长、 宽、高充当层的宽度，一旦层的厚度确定，由于同层的物体尺寸相同，问题就 转化为二维装填问题。该算法的特点是要求每一层尽可能由同一类物体组成。 如果没有足够的尺寸相同的物体能够把一层装满，就暂时放弃对这种物体 的处理，转而处理下一个优先级类型的物体。到最后可能所有的物体刚好装入 集装箱内，但是更多的情况是剩下的每类物体都不能装满一个完全层。对于后 一种情况采用g r 算法可将剩下的装箱工作完成。该算法实际上是对g r 算法 的改进。b m 算法运用二维装填技术来解决三维布局问题，给我们对c l p 问题 研究给了很大的启示 3 g e o r g e 算法 g e o r g e 算法是建立在同一尺寸的物体基础上的装箱问题，属于装箱问题 的一个特例n ”。算法中唯一改进的地方是提出了一种“集装箱旋转”的方 法，即允许集装箱在坐标系中绕y 轴或z 轴旋转，从而使得原来沿集装箱深度 6 山东大学硕士学位论文 方向码放的工作转变为沿集装箱宽度方向进行码放，从而在不改变装箱策略的 情况下改变了布局结果，在更大的空间范围内找到满意解。该方法简化了对物 体布局情况的搜索，使得物体的装填更容易用计算机来实现。 4 l o h n e e 算法 l o h n e e 研究的是弱差异情形，他们采用了水平方向进行构建层，为使 层表面趋于平坦按照物体高度设置优先级，并定义移动边界分隔集装箱为已装 填和未装填空间。值得强调的是，该算法给出1 5 组数据被很多算法当作标准 测试数据使用l 。 5 n g o i 算法 n g o i 等人提出一种新算法，该算法舍弃了层的构建方式，用一种特殊矩阵 空间描述方法表示空闲空间和已装填空间“钉“”，使得算法的描述直白而简单。 例如，一个长、宽、高为( 1 0 0 ，8 0 ，6 0 ) 的箱中左下角放入了一个尺寸为 ( 4 0 ，3 0 ，1 2 ) 的物体，则箱的边x 、y 、z 分别被分割为两段，空间表示法将 这一布局描述成如图卜2 两个矩阵： 稠琴司 图1 2n 9 0 i 的空间表示法及对应的空闲状态 两个矩阵分别表示箱体以物体高1 2 为分割点的上下两个空间状态。矩阵 中的第一个元素表示竖直方向的两个分割点。第一行的第二、三个元素表示x 方向的两个分割点，第一列的第二、三个元素表示z 方向的两个分割点。2 表 示装入物体的标识号，o 表示剩余空间。这种表示法简单、直观，且非常准确 的反映了物理空间的占用状态。 该算法流程简单，利于计算机编程实现，但是该算法缺点就是耗费内存较 多，增加了时间复杂度，而且使用该方法产生的盒柱之间有空隙“”，剩余空 间不能得到充分利用。 7 山东大学硕士学位论文 b i s c h o f f r a t c l i f f 采用了n g o i 等人的空间描述方法，算法独到之处在 于尽量使相同的物体组成盒柱，并且对于物体的优先级制定了四个标准即空间 利用率、深度方向尺寸、物体体积、剩余空间y 坐标最小“1 。他们的算法 中，物体可以任意放置。算法既适用于弱差异类问题，又适用于强差异类问 题。 目前国内对三维装载问题及其相关问题的研究比较少。就传统算法而言， 其中青岛大学的宫佩珊( 1 9 9 7 ) 针对单一产品且产品无摆放限制的情况提出了一 种递归方法“”，对单一产品摆放取得了不错的效果；天津商学院的杨传民教授 对于立体包装件的混装使用离散优化的方法进行研究“”，该方法只适用于小规 模问题。 国内装载问题启发式算法的代表有： 何大勇，查建中“ 提出一种利用三叉树结构表达三维矩形物体布局状态空 间的方法。该算法通过布局空间依次分割为三个方向的待布局空间，将分割后 的空间作为根节点的三个子节点。采取优先放置体积大的物体策略，每次都先 把最大物体放入剩余空间，这样每次放入相对于当前布局空间来说是满足特定 条件得最优解。每放一个物体，就把当前空间划分成了三个小空间，然后重复 上面的过程逐个对分割空间进行填充，直到没有剩余物体为止。 上海交通大学的阎威武“”在此基础上加入了重量的限制，通过平均高度装 载、货物合并、空间合并等策略，考虑了方向、重量、优先顺序、货物的配置 位置等约束条件，通过逐步淘汰差的装载方案，得出最终优化方案。 山东交通学院的陈建岭“”咖1 在g & r 算法的基础上对背包型集装箱问题提 出采用对每个货物“层”划分为一系列的垂直或水平的货物“条”。从而将每 个货物“条”的装填转化为求解容量等于货物“条”长度的背包问题，另外为 了保证货物层表面的平整性采取了货物合并策略以减少空间碎片的产生。 沈阳工业大学的马广煜”改进了启发式方法对物体从大到小的排放过于简 单的策略而带来的空间利用率的下降，提出了按层划分集装箱、在每层内对不 同物体进行回溯组合放置的新的方法。 1 4 1 2 智能优化算法 智能优化算法，是近年来解决复杂优化问题备受关注的一类方法，用于装 箱问题的这类方法主要有模拟退火算法( s i m u l a t e da n n e a l i n g ，简称s a ) 、基因 山东大学硕士学位论文 算法( g e n e t i ca 1 9 0 r i t h m s ，简称g a ) 、禁忌算法( 1 a b us e a r c h ，简称t s ) 。 模拟退火算法( s a ) 又称为模拟冷却法、随机松弛法和概率爬山法等。其思 想是由n m e t r o 口o l i s 噙1 等提出的。该算法是根据目标函数进行评价的，判定是 否接受某一状态为当前状态。s a 算法将解决布局问题的约束转化到目标函数 中去，从而将有约束问题转化为无约束问题，即将目标函数用于衡量约束违反 状况并作为模拟退火算法的评价函数。 模拟退火算法的特点： 1 ) 能够以一定的概率接受劣解，使得算法过程具有跳跃性，可能跳出局 部最优的“陷阱”，化解了算法对初值得依赖性； 2 ) 新状态产生函数、新状态接受函数、退温函数、抽样稳定准则和结束 准则及初始温度是直接影响算法优化性能的主要因素； 3 ) 算法具有解质量高、初值鲁棒性强、通用易实现的优点； 4 ) 较高的初温、较慢的降温速度、较低的终止温度以及各温度下足够多 次的抽样，使得优化过程较长。 遗传算法是建立在自然选择和群体遗传机理基础上的自适应概率性搜索算 法。遗传算法把优化问题的解的搜索空间转化为遗传空间，从代表问题可能潜 在的解集的一个种群开始，其中种群中的每一个个体对应问题的一个解。然后 进行编码，通过模拟自然选择和遗传过程中发生的交配和基因突变等现象，在 候选解中搜索最优解并充分利用原有优良解的已知信息加快收敛过程，最后输 出搜索结果。近年来出现了许多应用遗传算法解决装载问题的研究1 ”。 禁忌搜索的思想最早由g 1 0 v e r ( 1 9 8 6 ) 提出，它是对局部领域搜索的一种扩 展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。t s 算法通过 引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则 来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优 化。相对于模拟退火和遗传算法，t s 是又一种搜索特点不同的m e t a - h e u r i s t i c 算法。迄今为止，t s 算法在组合优化、生产调度、机器学习、电路设计和神 经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研 究，并大有发展的趋势。 近几年出现了采用启发式算法与智能优化算法相结合的办法进行集装箱装 载优化的研究。如北方交通大学的何大勇“1 提出了基于空间分解的布局启发式 9 山东大学硕士学位论文 遗传算法处理集装箱的装载问题；青岛大学的郭宏伟提出了“空间布局点” 的概念，对布入空间的物体所造成的新的可以放置物体的位置进行描述，并根 据集装箱的大小和彩电的分类建立系统模型，用启发式算法、遗传算法和模拟 退火算法对该问题进行了求解；福建师范大学的黄川汹1 提出了一种基于构造型 启发式规则和自适应技术的混合遗传算法来求解实际操作中最常见的弱异类集 装箱装载问题；中国海洋大学的韩运实口0 1 分析了遗传算法在整个遗传算法的运 算过程中的作用。 1 4 2 不规则货物装载问题的研究现状 不规则货物三维空间装载问题是指待装载的货物是任意形状、任意大小的 三维实体，或者待装容器是任意形状、任意大小的三维容器。由于不规则三维 空间装载问题的复杂性和琐碎性，这方面的研究还较少，但是在一些尖端科学 及航天技术中，这一优化问题却不容忽视，例如，火箭仪器仓内的仪器布置 等。 目前，人们把三维矩形空间的装载问题列为这类问题的基础或特殊情形， 关于如何把这类问题转化成三维矩形空间的装载问题来解决，许多研究者作过 一些探讨，例如将不规则实体组合成近似的长方体或将不规则的三维容器分割 成若干块的矩形空间，然后采用三维矩形空间的装载方法，再通过压缩算法来 求解3 瑚1 ”。 因此解决不规则货物三维空间最优装载问题的关键，在于能否解决不规则 货物组合成近似矩形体的问题，以及将不规则容器分割成矩形空间的问题。 目前，对如何将不规则货物有效地组合成矩形体问题的研究还十分少见， 而这种研究对不规则货物的三维空间装载优化起着至关重要的作用。 1 5 课题研究内容 本文主要研究物流配送中的不规则非矩形货物的装载问题，采用两步法的 研究策略： 第一步通过分析不规则货物的形状特点，按照不同的策略对不同规格、不 同尺寸的非矩形货物进行近似组合，目的是将非矩形的货物组合成近似的矩形 l o 山东大学硕士学位论文 体块。不规则货物的具体形状将对组合策略产生重要影响，因此本文将对多种 常见的不规则货物的组合方式及布局方法进行深入的探讨。 第二步则是将第一步组合好的近似矩形块按照启发式规则及遗传算法进行 装载优化。 最后以烟草配送中的装载为例进行研究，并给出仿真优化结果。 1 6 论文章节安排 在理论深入与实践应用相结合的原则下，第一章绪论对课题背景及相关研 究领域的发展状况进行了论述，对装载问题做了简要的介绍，作为本文的铺 垫，确定了论文的研究环境及意义所在；接着第二章对论文所涉及的货物装载 问题基本原理和相关知识做了详细介绍，奠定了论文的理论基础；第三章是本 文的核心部分，讨论了不规则货物的装载方法，运用启发式方法实现单一型不 规则货物的优化和多种不规则货物混合装载的优化。第四章是本文的另一个核 心部分，在第三章对不规则货物进行组合优化的基础上，对矩形体和组合后的 近似矩形体，运用改进的遗传算法进行装载优化。第五章着重介绍了基于前面 理论而实现的不规则货物混合装载优化仿真软件。介绍了软件的开发环境和各 项功能。并通过烟草配送装载实例的分析，得出优化仿真结果。最后，对全文 进行了总结，并指出了下一步的研究方向。 整篇文章的框架如图卜3 所示： - - - - - - - - - + 图卜3 论文框架结构 山东大学硕士学位论文 第2 章货物装载问题概述 2 1 装载问题的一般描述 为了便于研究，简化问题的描述而又不失一般性，货物的装载问题通常作 如下假设： 1 容器的长，宽、高分别代表笛卡尔坐标系的x 、y 、z 轴方向，坐标 原点位于前端右下角，后开门，如图2 1 所示 2 货物的放置方向必须与坐标轴平行或正交，货物不能与其它货物交叠 放置，货物不得超出装载容器的尺寸范围，货物的挤压变形可以忽 略。 3 假设货物可以任意旋转。 圈2 1 车厢坐标系 2 2 三维装载问题的分类 按照不同的标准三维装载问题有多种分类方法，以下是几种常见的分类方 法： 1 以装载容器的有限和无限来划分：容器数量无限，货物必须全部装 完，要求使所用的容器数量最少；容器数量有限，待装货物数量超过 了容器的装载能力，要求被装载货物的总体积达到最大，使容器空间 利用率最高。 2 根据所装货物的类型可分为：所有货物的类型( 体积、三维大小等) 山东大学硕士学位论文 相同；货物的类型不同，且类型多，每种类型的货物数量少；货物的 类型不同，但是类型少，每种类型的货物数量多。而第3 类可以通过结 合第1 类和第2 类的解决方法，寻求最优装载方案，因此，三维装载问 题也可大体按货物类型的相同和不同划分成2 类。第一，弱差异情形 ( w e a l 【l yh e t e r o g e n e o u s ) “小”，即只有少数几种体积不同的货物但每种 货物的数量较多；第二，强差异情形( s t m n gh e t e r o g e o u s ) 。”汹，即有 多种体积不同的货物但每种货物数量较少。 2 3 装载问题的相关概念 2 3 1 分层的概念 在求解c l p 的诸多启发式算法中，为了便于装填，大都引入了层( 1 a y e r ) 的 概念。即把装载过程看成是一层一层地装入。所谓层，有水平和竖直之 分。水平方向的一层是指，铺满x y 平面，但是沿容器的高度方向只装填了一个 基本单位的所有货物( 本文简记为) ( y 专z 层) ；竖直方向的一层则是指，铺 满y z 或x z 平面，但是沿容器的宽度或深度方向只装填了一个基本单位的所有货 物( 本文简记为y z x 层和x z 寸y 层) 。在引入了层的算法中，装载的顺序 是：从原点出发，开始装填一层，一层装好以后，再开始新层的装填，直至将 容器装满或将货物全部放入。每一层的深度由这一层中第一个货物的长度决 定。这种按层装入的方法通常也叫做砌墙法( w a n b u i l d i n g ) 。 在装载时，常常使每一层尽可能由单一类型的货物组成，那么这种完全由 单一尺寸的货物填充的层被称作一个完全层( c o m p l e t cl a y 神。 2 3 2 空间合并思想 在启发式算法当中，每层的布局中都会不可避免的出现些相对较小的空 间，而很难有合适尺寸的盒子能够放入这些相对较小的空间中，这样势必造成 大量的难以利用的空间碎片的产生。为了减少由于空间碎片所产生的空间浪 费，需要对满足一定条件的相邻空间加以合并。 1 4 山东大学硕士学位论文 2 4 装载的相关规则 2 4 1 定序规则 定序规则是指通过比较待装货物的某一项或者某几项属性( 如货物的目的 地，货物的体积，货物的面积，货物的最长边等等) ，来决定装载货物的顺 序。定序规则可以通过调整货物放入车厢中的先后顺序，影响最终布局质量。 装载时，物体对装载人员而言，重要程度不同。重要的优先放入，次重要 的后放入。效果较好的定序规则有： 1 按照体积递减原则。体积大的先放入，体积小的后放入 2 按照重量递减原则。较重的货物先放入，较轻的货物后放入。 3 按照底面积递减原则。底面积大的先放入，底面积小的后放入。 4 按照最长边递减原则。最长边大的先放入，最长边小的后放入。 5 按照卸货时间原则。卸货较晚的先放入，卸货较早的后放入。 2 4 2 定位规则 当按照一定的先后顺序将布局货物逐个放入容器当中时，确定当前布局块 在容器剩余空间中的位置的规则就叫做定位规则。货物装载问题的定位规则主 要有： 1 占角策略，即物体首先摆放在布局空间的某一角； 2 顺放策略，从一个角开始，沿布局空间的某一边顺序摆放； 3 先沿布局空间的四边摆放，然后填中心； 4 从某面的容器壁开始，一层一层布局，在某一面容器壁上，再确定 一条边，最后归结为一个角。 应用领域不同，布局的定位规则也不同，但是归纳起来可以用围棋中的一 句行话来体现“金角银边草肚皮”，即布局物体应先定位在角上，再定位在边 上，最后填满中心。”。 与传统的定序规则一样，“金角银边草肚皮”的定位思想是人们试凑布局 所获得的经验，是长期生产实践的结果。考虑图2 2 ： 山东大学硕士学位论文 ( a )( b )( c ) 图2 - 2 三种不同定位规则的布局比较 该图是二维矩形布局，a 、b 、c 三种定位方案，显然，根据“金角银边草 肚皮”的思想可知，a 优于b 优于c 。 2 5 装载问题的实际制约因素 在货物装载中待装物体的类型千差万别，由于受到货物体积、重量，容器 尺寸、载重等方面的限制，货物的装载需要满足以下基本条件。 1 方向约束：在装载中，货物的摆放方向受约束。例如有的货物的包装 要求只能向上放置，不能倒置。 2 承载能力的约束：在装载过程中，货物所能承受的最大压力受限制， 否则下面的货物会被上面的货物压坏，所以装载的层数、装载顺序要 受到限制。 j 3 稳定性的约束：装载完毕，货物的重心应在装载容器的几何中心附 近，以利于运输安全。 4 货物的配置位置：货物的种类千差万别，货物不能任意摆放。有的货 物不能摆放在其它货物之上。 5 货物的装载顺序：不同货物在装载中应按不同的优化顺序装载。例如 送货的目的地不同，装载顺序也应相应的不同，此时采取先到的货物 后装箱的策略。 6 货物的均匀性：在多集装箱装载中，有时要考