（计算机应用技术专业论文）集装箱装入新算法的研究与软件实现.pdf

沈阳工业大学硕士学位论文 摘要 “切割和装入”问题的目标是寻求一种有效的切割和装入方法，最大化原料或空间 的利用率。由于布局的优化能导致大量的材料节省，空间的充分利用，所以高的利用率 能增加企业的利润。该问题的应用非常广，最具体的应用是对原材料面积和空间的利 用，例如钢板、玻璃和木材的切割，货盘、集装箱的装入等。 集装箱装入问题是“切割和装入”问题领域中的三维空间问题，是具有复杂约束条 件的组合优化问题。在理论上属于n p 完全问题，在实际问题上很难解决。该类问题的 解决方法在国内外仅有少量的研究报道，多是基于启发式的近似求解方法。 在本课题装入算法的研究中，提高集装箱空间的利用率是主要的目标。作者首先对 樊建华设计的算法进行消化和整理，继承了其对剩余空间的描述和划分方法。然后在她 原有的启发式方法的基础上进行了重新的设计，改进了启发式方法对物体从大到小的排 放过于简单的策略而带来的空间利用率的下降，提出了按层划分集装箱、在每层内对不 同物体进行回溯组合放置的新的方法。为了避免对所有的物体进行组合，本课题提出了 组合方法与启发式相结合的方法。在保证时间的前提条件下，使用限制组合方式来提高 空间利用率。这是本课题研究的重点。最后，由于在集装箱中对剩余空间的划分、层的 划分采用的是切割的原理，剩余空问在实际上是相互连通的，本课题为了进一步提高剩 余空间的利用率，在集装箱的装入算法中，实现了剩余空间的结合算法。 基于本文算法的软件已调试成功，可解决于具体的集装箱装入问题。 关键词：集装箱，布局，装入，启发式，组合，计算机辅助设计 沈阳工业大学硕士学位论文 r e s e a r c ha n ds o f t w a r e i m p l e m e n t a t i o n o fan e w a l g o r i t h m f o r c o n t a i n e r l o a d i n g a b s t r a c t t h e t a r g e to f “c u t t i n ga n dp a c k i n g i ss e e k i n g a l le f f e c t i v ec u t t i n ga n d p a c k i n gm e t h o d ， m a x i m i z i n gr a w m a t e r i a lo rs p 面a lu t i l i z a t i o n b e c a u s et h eo p t i m i z a t i o no f t h el a y o u tc a ns a v e r a w m a t e r i a l ，u s es p a c ea b u n d a n t l y , t h ep r o m so f e n t e r p r i s ec a n b ei n c r e a s e db yt h e h i g h u t i l i z a t i o n t h ef i e l dt h a tt h ep r o b l e ma p p l i e di sv e r yw i d e ，t h em o s tc o n c r e t ea p p l i c a t i o ni st h e u s i n go f r a w m a t e r i a la r e aa n d s p a c e ，s u c h a st h e c u t t i n g o f s t e e lp l a t e ，g l a s sa n dt i m b e r , t h e l o a d i n go f t h ep a l l e ta n d c o n t a i n e r c o n t a i n e r l o a d i n g i st h et h r e e - d i m e n s i o n a lp r o b l e m i n c u t t i n ga n dp a c k i n g p r o b l e m s i t i sc o m b i n e d o p t i m i z a t i o nw i t hc o m p l e x c o n s t r a i n tc o n d i t i o nn b d o n g s t on p c o m p l e t e p r o b l e m i nt h e o r y , s oi t sh a r dt os o l v ei n p m a i c a lp r o b l e m s ，t h i sk i n do f p r o b l e m h a saf e w 咖d yr e p o r t s i nd o m e s t i ca n d o v e r s e a s , m o s to f t h e m b a s eo nh e u r i s t i c sa p p r o x i m a t i o n a l g o r i t h m s o nt h er e s e a r c ho f t h e l o a d i n ga l g o r i t h m i nt h i sp a p e r , t h em a i ni d e ai sh e i g h t e n e dt h e u t i l i z a t i o no f t h ec o n t a i n e r s p a c e f i r s t l yt h em e t h o d o f f a n sw a s d i g e s t e da n d r e v i s e d a d e s c r i p t i v ea n di n t e r s e c t e dm e t h o d o f r e m a i n d e r s p a c e w a si n h e r i t e df r o m f a n s s e c o n d l y , a n e wm e t h o dw a s r e d e s i g n e d t h a tb a s e do nf a n so r i g h ：1 a lh e u r i s t i cm e t h o d t h eh e u r i s t i c m e t h o d , t h a t t h es p a t i a lu t i l i z a t i o nw a sd e c r e a s e d b y t h es i m p l e rs t r a t e g yw h i c ht h ei t e m sw e r e c h o s ef r o mt h eb i g g e rt ot h es m a l l e r , i si m p r o v e d an e wh e u r i s t i cw a yi sp r o p o s e d , w h i c h d e c o m p o s e s t h ec o n t a i n e ri n t oan u m b e r o f l a y e r s a n dc o m b i n e sa n db a c k t r a c k sd i f f e r e n ti t e m s i nt h el a y e r i no r d e rt oa v o i dt h ec o m b i n a t i o no fa l li t e m s t h em e t h o dt h a tc o m b i n e dm e t h o d i n t e g r a t i n g w i t ht h eh e u r i s t i cm e t h o di su s e d u n d e rt h ec o n t r o lo f t i m e , ac o n s t r a i n e d c o m b i n a t i o nm e t h o di su s e dt oe n b a n c ot h es p a t i a lu t i l i z a t i o nt h i si st h e k e yo f t h er e s e a r c h t h i r d l y , b e c a u s e t h et h e o r yo f t h ed i c t i o no f r e m a i n d e r s p a c ea n dl a y e ri nt h ec o n t a i n e r i s c u t t i n g t h er e m a i n d e r s p a c e i si n t e r r e l a t e di nf a c t s o ，ac o m b i n a t i o n a l g o d t h m o f r e m a i n d e r s p a c e i si m p l e m e n t e dt oe 枷h a n c ct h e s p a t i a lu t i l i z a t i o no f c o n t a i n e rl o a d i n g i np r o c e d u r eo f t h e c o n t a i n e r l o a d i n g 2 一鲨堕三些奎兰壁兰垡笙茎 t h es o f t w a r eb a s e0 1 1t h e a l g o r i t h m o f t h i sp a p e ri ss u c c e s s f u ln m n i n gi tc a ns o l v e k e y w o r d s ：c o n t a i n e r ，l a y o u t ，l o a d i n g ，h e u r i s t i c ，c o m b i n a t i o n ，c a d 3 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：马于蝎日期：2 肋乒。弓，口 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：弓主：炖导师签名：日期：细耻孑i 沈阳工业大学硕士学位论文 注释说嘎清单 同质物体( h o m o g 锄u s ) ：装入算法中要处理的货物是由相同的物体组成的，则称 这些物体为同质的物体。 弱异质物体( w e a l d yh e t e r o g e n e o u s ) ：装入算法中要处理的货物中物体的种类比较 少，则称这些物体为弱异质的物体。 强异质物体( s t r o n g l yh e t e r o g e n e o u s ) ：装入算法中要处理的货物中物体的种类比较 多，则称这些物体为强异质的物体。 沈阳工业大学硕士学位论文 1 绪论 1 1 课题研究的价值 1 1 1 应用价值 “切割和装入”( c u t t i n g & p a c k i n g ，简称c & p ) 问题可以看作是一类特殊的资源 利用优化问题。目标是寻求一种有效的切割和装入方法，最大化原料利用率。由于布 局的优化能导致大量的材料节省、缩减产品价值，所以高的材料利用率能增加产品 工业的利润【“1 。该问题应用的领域非常广，最具体是对原材料面积( 二维) 和空间 ( 三维) 的利用。二维应用如：钢铁制造行业，纸品加工行业，服装制造业，以及玻璃 加工制造行业中。在这些行业中，一种行之有效的切割原材料的方法可以提高原料的利 用率，减少废料的产生，对提高企业的经济效益有直接的好处。三维应用如：集装箱 货物运输行业，货物存放行业，货物的仓库存放等。有效的三维装入方式提高空间的 利用率，从而提高经济效益。 采用集装箱运输是世界上广泛使用的手段之一。集装箱码头是国际运输链和物流链 的重要环节，通过它，各种货物才能顺畅遣流动。现代彩口流被西方经济学家和企业界称 为继劳动力、自然资源之后的“第三利润源泉”、“降低成本的宝库”、“企业发展的 战略手段”，将在我国经济发展中起着越来越重要的作用。随着中国加入w t o ，中国 对物流的需求日益旺盛起来，突出表现在：外贸出口逐年上升，1 9 9 5 年至1 9 9 9 年中 国外贸年均增长7 9 ；1 2 亿人口的巨大消费市场使1 9 9 9 年零售消费品总值已达 3 7 5 1 2 亿美元；加入w r o 后，关税及配额的逐步取消将使外贸出口由1 9 9 9 年的3 ，4 8 0 亿美元增长至2 0 0 5 年的6 ，0 0 0 亿美元【2 翻。集装箱装入的优化的问题是物流链中可以降 低运输的成本，提高运输的效率的一个问题。它广泛的出现在铁路货车车厢装载，轮船 配载，集装箱装载等情况中，在集装箱的运输中，降低运输成本，关键是提高集装箱的 装箱量，以降低单件包装产品的运费。对可塑包装产品，要做到这点是容易的，只要按 集装箱容积的尺寸设计产品的包装即可。但对于非可塑包装产品，由于产品包装固定。 难以做到满负荷运输，所以提高集装箱的装箱率可以带来很大的经济效益【4 1 】。 2 沈阳工业大学硕士学位论文 1 1 2 学术价值 “切割和装入”问题已有四十多年的研究历史【5 1 ，涉及的领域非常广，在不同的行 业中对现实问题的求解有不同的要求，没有一种通用的数据结构和解决方案可以适合一 切问题的求解。根据每一行业生产的产品特点，在对原材料的处理过程中存在一些特殊 的约束条件，而且不同行业可能对问题的侧重点各异，如在板材上切割零件时要考虑切 割时零件的边缝，在对土地资源的描述中要对不规则的形状进行准确的描述，集装箱装 载物体时考虑物体对重量的承受力，在飞机的货舱装载中不仅要对非矩形的货舱进行描 述，而且还要严格的考虑物体的重心。在问题求解中，每增加一个约束条件，就会增加 数据结构的复杂性，同时加大了问题的求解难度。随着现实问题的不断复杂化，对该问 题不断增加新的约束条件，就需要重新考虑求解策略，以适应实际的需要。 集装箱装入问题是“切割和装入”问题领域中的三维问题，是具有复杂约束条件 的组合优化问题，在理论上属于n p 完全问题【9 】，在实际问题上很难解决，直接利用数 学中的优化方法比较困难，因为数学优化方法一般是对量的优化，通过对方程进行求解 得到目标解。但是集装箱装入问题不仅是量的问题，而且还需要对物体以及剩余空间进 行形状的描述，从而增加了问题的复杂度，使得该问题无法用纯数学方法进行描述，无 法通过数学的公式进行求解，因此该问题只能通过一些近似方法来解决。大多数近似的 方法都使用了大量的列举法来寻求较优的效果，计算量大，过程不容易控制，不适合实 际的应用。由于集装箱装入问题的复杂性和特殊性，对于剩余空间的形状较难把握，处 理该问题有一定难度，在此领域研究的人数相对较少，所以行之有效的集装箱装入算法 具有较大的研究意义。 1 2 “切割和装入”问题的分类 由于“切割和装入”问题涉及范围的多样性，在许多文献中它们有不同的名字，虽 然这些问题出现在不同的领域中，但是对它们的研究表明它们有相同的逻辑结构【1 8 】，其 中包含了两组基本数据，一组是大物体( o b j e e t ) ，另一组是较小物体( i t e m ) 。大物体 表示需要被切割和装入的物体，如原料、集装箱，而小物体表示要切割成或要装入的物 体，如二维条、立方体盒子。 为了实现信息在不同学科的交流，d y c k h o f f 0 9 9 0 ) 确定了“切割和装入”问题 。3 沈阳工业大学硕士学位论文 的分类。第一类空间问题由一维切割问题，二维平面切割问题，三维装入问题组成，它 们都被定义成欧几里德空间( 例如切割杆材问题，集装箱装入和货盘装入问题) 。另一 类非空间问题涉及抽象的“切割和装入”问题，包括如重量，时间或者金融的维度等非 空间领域( 例如内存分配，资金预算，铸币及人工投入线性平衡法) 。 非空间问题应用在比较抽象的经济领域，针对它的研究相对较少，而空间问题则在 学术界引起了一些学者的关注【5 1 。其中空间问题的具体内容如下： 一维切割主要指线形的管材或杆材的下料，即指在一定长度的管材或杆材上如何合 理截取，使所剩废料最小。一维切割涉及的数据结构简单，只需用长度来描述即可，因 此一些数学优化方法很容易用来解决这一问题，并且基本上能达到最优的切割方式。 二维平面切割指在平面板料上如何合理有效的放置各种零件，使得所剩余料最少， 原料的利用率最高。二维排料中的数据结构比较复杂，物体越多，问题就变得更困难， 需要借助一定的中间手段，一些优化算法在二维排料领域中的应用也变得困难多了。集 装箱装入问题比二维排料问题更加复杂，要想得到好的解就更加不容易。本课题主要研 究的是“切割和装入”问题中空间问题的三维装入问题。 三维装入问题是指寻找多个较小物体合理地放入较大物体( 如集装箱) 中的布局问 题。目前研究的主要对象是长方体形状的盒式物体。根据装载工具的不同，可分为货盘 装载和集装箱装入 9 1 问题。 1 2 1 货盘装载 货盘( p a l l e t ) 是一种只有底面没有四周墙壁和项面的托盘。货盘装载是将货物装 在侧面没有遮挡或支撑的货盘上，装载货物的边平行于货盘的边，物体之间互不重 叠，而且物体装入的高度不能超过货盘限定的高度，使得装载的利用率最大。其典型 应用于自动仓库中基于货盘的物品传输。根据待装物体尺寸的不同，可以分为生产商 货盘装载和批发商货盘装载。 生产商货盘装载( m p lm a n u f a c t u r e r sp a l l e tl o a d i n g ) 涉及的待装物体都是同样的 尺寸，即它们的长、宽、高都是相等的，这种方式多用于生产同一产品的厂家。在 m p l 方式中，为了便于控制，大多数文献都是将所有待装物体沿着同一朝向放置，这 样可实现按层放置，每一层相当于二维排料中的放置算法，事实上将m p l 问题转化为 - d 一 沈阳工业大学硕士学位论文 二维平面矩形排放的问题。而且都是同一尺寸的物体，约束条件比较简单，所达到的优 化程度比较高。 另一种批发商货盘装载方法( d p ld i s t r i b u t o r sp a l l e tl o a d i n g ) 所装入物体的尺寸 不相等，主要针对一些大型批发厂家货物种类比较多的情况。批发商货盘装载算法由于 物体的种类多，实现起来比生产商货盘装载算法困难。最初的解决方法是将其转化为较 容易处理的二维装入问题，这种处理方法只有当装入物体的高度尺寸相同时才可行。后 来从三维装载的角度来考虑问题，使用了启发式方法等算法。 1 2 2 集装箱装入 集装箱( c o n t a i n e r ) 是一种不仅有底面而且还有四周箱壁以及箱顶的封闭型的矩形 盒式容器，是一种重要的储存以及装载运输物体的工具，广泛的应用与生产批发商和运 输部门货物的装载运输。集装箱装入问题与货盘装载问题不同。首先，集装箱是封闭式 容器，所能利用的空间资源限制比货盘装载要严格的多；其次，由于集装箱装入的货物 只能通过侧门进入，因此不仅要得到对空间利用率的优化，对装入的过程的描述也必须 是明确和可行的。目前集装箱装入问题的研究多数针对多种不同种类的物体的装入问 题，所以对集装箱装入问题处理比货盘装载复杂度和难度要大的多。 1 3 集装箱装入问题的国内外研究动态 131 常用的算法及使用方法 有关布局的问题综述性工作详见文献1 9 8 1 ，目前大部分文献是研究二维或三维矩形 物体在矩形容器中的布局。目前常用的布局优化方法有启发式方法、数学规划、图论 法、遗传算法、模拟退火法等方法。 ( 1 )启发式方法( h e u r i s t i c a l g o r i t h m ) 的基本思想是依靠人的先验知识确定每一步的 排放策略，从而得到目标的解。启发式方法的一般步骤是从与待解问题有关的信 息中得到估价函数来确定搜索的方向，使过程中的每个状态向目标状态的方向前 进，其中状态( 己装入、未装入和剩余空间) 的表示是个共性问题，而装入策略 和估价指标是要随具体问题变化的问题。 集装箱装入问题目前多是按某种指标( 如面积、边长、体积) 对矩形货物排 序，优先在剩余空间放置大的货物。采用肩发式算法的好处在于它比遗传算法和 5 沈阳工业大学硕士学位论文 模拟退火法减少盲目性和计算时间、便于控制排放过程，较适于实用软件，这在 集装箱装入问题中尤为重要。但是往往启发式方法得出的解不是很高。 ( 2 )模拟退火法( s i i r n d a t e da n n e a l i n g ，s a ) 是模拟热力学中经典粒子系统的降温过 程，来求解规划问题的极值。当孤立粒子系统的温度以足够慢的速度下降时，系 统近似处于热力学平衡状态，最后系统将达到本身的最低能量状态，即基态，这 相当于能量函数的全局极小点。由于模拟退火法能够有效地解决大规模的组合优 化问题，且对规划问题的要求极小，因此引起研究人员的极大兴趣。当系统温度 足够低时，就认为达到了全局最优状态。按照热力学分子运动理论，粒子作无规 则运动时，它具有的能量带有随机性，温度较高时，系统的内能较大，但是对某 个粒子而言，它所具有的能量可能较小。因此算法要记录整个退火过程中出现的 能量较小的点阳 。国内外有一些对此问题的研究1 1 9 4 1 。 ( 3 ) 遗传算法( g 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 年提出来的。它的突出特点在于包含了与生 物遗传及进化很相似的步骤，如遗传，变异，选择等。遗传算法与传统的优化算 法相比，具有以下特点： 该算法是利用目标函数本身的信息建立寻优方向，而不是利用其导数信 息建立寻优方向，因此它对优化设计问题的限制较少，仅要求问题是可计算的。 遗传算法利用概率转移规则，可以在一个具有不确定性的空间上寻优。 与一般的随机型优化方法相比，遗传算法不是从一点出发沿一条线寻优，而是在 整个解空间同时开始寻优搜索，因此可以有效地避免陷入局部极小点，具备全局 最优搜索性。 在该算法中，由于群体中每个个体的搜索是独立进行的，因此算法具有 内在的并行计算特性【2 9 】。 这些优点使得g a 能处理许多传统优化算法无法解决的复杂问题，被广泛 应用于许多领域。但g a 在许多问题上的早熟( 即过早收敛于局部最优解而非全 局最优解) 始终未得到很好的解决，在将g a 应用于优化排样时有时得不到最优 解，即存在遗传欺骗问题9 ”。其中国内外对此进行了一定的研究孤”3 9 1 。 6 沈阳工业大学硕士学位论文 ( 4 )线性规划法和动态规划法，它们存在的主要问题是计算时间和空间成指数增长， 只适合于小规模的排料问题口。5 1 。 13 2 国内外研究动态 在二维装入问题中，物体的类型包括规则的形状和不规则的任意形状。目前国内 外进行了大量的研究1 棚2 2 。3 3 2 1 3 弘“。9 】。二维排料中的数据结构比较复杂，物 体越多，问题就变得更困难，需要借助一定的中间手段，一些优化算法在二维排料领域 中的应用也变得困难多了。集装箱装入问题的复杂性远大于二维装入问题，要想得到好 的解，就更加不容易。三维集装箱问题主要是解决物体组合问题，它的解空间是非常大 的，而且随着问题规模的扩大，复杂性成指数增加，尤其是对于物体种类不同的三维集 装箱问题，没有确切的算法可以有效的解决这问题。 全局优化的方法求解的质量比启发式方法要好，但是在实际应用问题中，在约束 条件较多，物体的种类较多的情况时，它们的计算复杂度较高、时间长，中间过程难以 控制，不适用于实用软件，所以多数的实用软件采用的是启发式方法。启发式方法是根 据经验启发直接得出物体每次装入过程的最优状态，并对各种的约束和物体类型的选定 直接控制。启发式的优点是可减少因全局搜索带来的盲目性，计算效率比其他方法好， 而且还能兼顾装入过程，而且通过一定的优化策略使其接近优解，更适于实用软件的应 用，因此可见的几个集装箱装入软件使用的是启发式方法。 目前的研究大多针对相对简单、但实际应用中常用的物体形状是盒子形的，从己 发表的有关文献来看，大多数研究者的工作是在寻求近似优解的方法，通常是基于启发 式的算法。 国内对三维集装箱启发式方法有一定的研究，姜义东【3 ”提出基于空间分解的启发 式算法，采用三叉树的数据结构来处理空间，使用深度优先的处理方法处理三叉树得出 布局结果。该算法采用优先放置体积大的物体策略，每次都先把最大物体放入剩余空 间。每放一个物体，就把当前空间划分成了三个小空间，然后在逐个对小空间进行填 充。虽然这样划分的剩余空间会减小问题的复杂性，但是划分后剩余空间比较“零 碎”。樊建华明的算法与姜义东0 5 1 的算法类似，她提出了采取先放置边长大的物体策 略，在剩余空间内先放置边长大的物体，不同的是她优先考虑多个同类物体并排放置刚 7 沈阳工业大学硕士学位论文 好能在空间底面的宽度或长度方向放满的情况，这样可以减少产生的空间碎块，降低空 间的复杂性。同时她也考虑到了剩余空间的结合问题。 上述两种算法0 7 1 ”1 都提出优先放置大物体，逐个对物体进行排放的策略。这两种 算法虽然在一定的范围内可以达到局部较优，但是可以通过针对剩余空间寻求几个小物 体的适当组合代替简单的选用大物体来提高集装箱的空间利用率。同时也存在通过一定 的策略把对剩余空间的描述更加简化，以减少计算的复杂度。在国外的文献中也提到了 物体的组合方法。如按层( 1 a y e r ) 、列( c o l u m n ) 、块( b l o c k ) 、堆( s t a c k ) 来组合 放置物体的方法。 g e o r g e 和r o b i n s o n 1 棚建立沿着集装箱宽度的层，尽量使某一层的外表面平整，并 且结合剩余空间以提高空间利用率。在建立一个新层的之前，要评估哪些物体可以作为 “新开( o p e n ) ”层的物体来放置，这有赖于评定的优先权函数。第一标准是先选择数 量最大的物体，因为这样很容易填充一层，第二个标准是物体最大维度的尺寸，如果它 很大，物体也许很难放入，装入时应该先放入这样的物体。但是当小物体的数量多，大 物体的数量少，则会使小物体优先放入，导致大物体被剩余，从而降低了空间利用率。 b i s c h o f f 和d o w s l a n d 3 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 方法的过程有两个主要的不 同：首先，每一层由单一类型物体组建；第二，层内物体的布局通过二维布局过程来决 定。它旨在最大化横截面( 集装箱的宽度和高度组成的矩形) 的面积利用率。层的深度 选择很大的影响了空间的利用率。按层来放置物体，层的深度一旦决定了，横截面就可 以通过二维布局来解决了。通过层的划分。三维问题可降为二维问题来解决，大大的降 低了闯题的复杂性，简化了剩余空间的描述。这两种方法只有在同种物体的数量很大时 才会有较大的作用。 1 9 9 0 年b i s c h o f f 和m a r r i o t t 0 研究了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 个等级( r a n k i n g ) 规则，即待装入物体的最小边降序排列，物体最小边升序 排列，物体数量的降序排列，物体数量的升序排列，物体体积的降序排列，物体体积的 升序排列，提出了1 4 种集装箱装入的启发式方法，通过大量的实例进行分析，对这1 4 种算法性能进行比较，得出集装箱装入结果的优劣在一定程度上依赖于待装物体的种类 8 沈阳工业大学硕士学位论文 多少的结论，并建议针对物体种类和数目，采用不同的启发式方法。并提议依此设计复 合启发式算法，针对箱子类型的数目，采用不同算法。 该方法表明启发式的性能非常依赖领域，受物体数量变化的影响也是很大。由于 b i s c h o f f 等人的验证和分类，后来的研究者对物体进行不同方式的组合，如层、列、 块、堆等方式，基于这种组织方式开发相应问题启发式求解方法，如墙壁支撑( w a l l b u i l d i n g ) 方法【4 m + m 、堆( s t a c kb u i l d i n g ) 方法“】、立方体布局( c u b o i d a r r a n g e m e n t ) 方法p 8 l 、剪切机方法 2 0 l 等。 d a v i dp i s i i l g 一8 媳出了基于墙壁支撑的集装箱装入启发式方法，把整个集装箱分解 成若干层，每一层又分解成若干条( s t r i p ) 。层由一系列垂直或水平的条所组成，层的 深度也就是每条的厚度由分枝定界法解决，而条的布局可转化为等宽或等高的一维背包 问题来处理。在此启发式方法中使用搜索算法来寻找层深度和条宽度的集合，为了减少 复杂性，并有效地控制层深度和条宽度的搜索，设计一些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 ) l h 日题进行测试，其结果表明对于较大问题 规模有更优的解。 m i c h a e l e l 一婚j 提出了一个建立相同方向物体的同质块算法，把相同的物体按照同 样的方向组合成块，然后由这些同质块填充集装箱。首先提出了一个贪婪启发式算法， 它产生预期的块布局，通过评估标准来决定物体的方向和剩余空间的最好组合。然后提 出搜索算法来改进贪婪的启发式算法的解。为了简化问题的复杂性，树的分枝不是对每 个不同物体进行分配的，而是对不同类型物体进行分配的。因为不可能对所有子问题完 全分枝，因此又提出了一个评价函数，鉴别最有希望( p r o m i s i n g ) 的结点，修剪没有希 望的结点。这个函数不仅要考虑迄今得到的空间利用率，也要评估剩余物体填充剩余空 间的潜力。但是这只是一个理想的函数，没有确切的界限，只在树搜索中使用下界并且 限制宽度搜索。这样做的好处是相同的物体放置在一起，使集装箱中的物体比较稳定， 装卸方便，放置容易。 d a v i d p i s k n _ g e r t s 弄1 m i c h a e le l e y 【1 9 1 的方法都通过评估的规则对层的深度、块的组合 进行判断，这两种方法计算的代价十分庞大，而且不论是组成层、块，都要求同种或尺 9 沈阳工业大学硬士学位论文 寸相似的物体有足够的数量，若是对于同种物体个数少，物体的种类较多，尺寸差异较 大的散装货物的情况并不适用。 1 4 本课题研究内容 本课题研究的是集装箱装入算法与软件实现。软件实现是把集装箱装入算法实用 化，把理论上的算法与具体的应用结合起来，所以装入算法是本课题研究的重点。由于 问题本身的复杂性和目前国内外的研究的现状，本课题研究的待装物体都是盒式的长方 体，没有方向的限制，各种物体的尺寸和数量没有限制。 在本课题装入算法的研究中，作者首先消化了樊建华渊基于启发式的集装箱问题求 解思想，继承了其剩余空间的描述和划分方法。本课题主要的目标是在樊建华集装箱的 算法基础上进一步提高集装箱的空间利用率。 由于樊建华阳，姜义东1 3 5 1 采用的是对物体从大到小，逐个放入的启发式方法。启发 式方法的缺点是以入工经验为主导，对物体从大到小的排放策略过于简单，考虑其它优 化的因素太少，可以通过一定的策略对其进行改进，其中可以通过对待装物体进行组合 评估来代替逐个对大物体进行放置的策略。而d a v i dp i s i n g e r t 鞠im i c h a e le l 1 羽方法对 物体的组合应用于物体种类少、同类物体的数量很大的情况，并不适用于同种物体数量 少，物体尺寸差异大的散装货物。因此本课题提出一种新的按层划分集装箱、在每层内 对不同物体进行回溯组合放置的排放方法。这样做既提高了集装箱的空间利用率，又简 化了三维问题的复杂度。物体放入剩余空间中，往往几个小物体组合后放入比单纯放入 几个大物体要好的，因此本课题通过对物体的回溯把不同的物体在层内进行组合放置， 以提高集装箱的空间利用率。但是如果对所有物体进行组合又会带来存储空间急剧增大 的问题，所以本课题采用组合方法与启发式相结合的方法，在保证时间的前提条件下， 使用限制组合方式来提高空间利用率，即把集装箱按层划分，缩小物体回溯组合的范 围。 最后，由于在集装箱的装入过程中，对集装箱空间的划分采用的是切割原理，而在 集装箱中，此种切割是虚拟的，剩余空间实际上还是相互连通的，所以剩余空间是可以 结合的。因此本课题在樊建华剩余空间的结合基础上，又实现了符合本算法特点的对剩 余空间的结合算法，对集装箱的利用率进行进一步的提高。 1 0 沈阳工业大学硕士学位论文 本系统的主界面如图2 1 ： 图2 1 系统的主界面 2 1 系统的基本功能 本系统的功能如图2 2 所示。 2 系统简介 图2 2 系统的功能 ( 1 ) 订单管理 用户对订单进行管理，可以添加新订单，对已有订单进行修改、查询，并通过 查询界面显示已有订单的信息。对订单数据进行输入、修改时，要求以正确的类型 输入数据，并且对已有的数据可进行增、删、改。 ( 2 ) 数据的提取与处理 系统从用户输入的数据进彳亍物体、集装箱数据的提取。 吉西暑西占 沈阳工业大学硕士学位论文 把输入的物体信息数据按照长 = 宽 = 高的顺序整理。 把输入的全部物体按照底面积降序排列，当面积相等的时候按照长度，宽度，高 度降序排列。 ( 3 )对用户输入的定订单数据进行计算 调用软件的核心算法对订单数据进行计算，并得出计算后物体的放置位置。 ( 4 ) 对计算后的结果进行数据输出 显示计算后己放置物体的个数，剩余物体的个数，集装箱的利用率，物体放置 的位置坐标。 ( 5 ) 图形显示 根据物体在集装箱中的位置坐标，进行图形显示，给提供用户一个直观的排放 结果。 2 2 系统工作流程 本系统的工作流程如图2 3 。 订单管理 0 l 对数据进行提取、处理 士 计算 士 计算结果输出 士 绘制图形 图2 3 系统的工作流程 - 1 2 沈阳工业大学硕士学位论文 2 _ 3 集装箱装入系统的数据文件结构 系统的数据结构涉及到数据在内存中的存放方式，而且数据结构与系统的运行效率 有着直接的关系。所以选择合适的数据描述及存放方式也是本课题设计中需要考虑的一 个方面。 在本课题的实现过程中，作者将所有来自外部的数据( 订单中待装物体的数据以及 集装箱的数据) 和系统执行完毕后产生的结果数据都放在数据库中，取放数据直接通过 数据库来操作。由于待装物体的数量通常都很大，借助于数据库这种方式就不必再在内 存中申请存储单元，可以节省许多内存空间，从而使系统的运行效率提高。 在本文中，主要用到如下的数据结构：待装物体的数据结构、集装箱的剩余空间数 据结构和物体在集装箱内放置位置的数据结构。 待装物体数据包括以下字段： b o x n o待装物体韵标识号 b o x n u m该类待装物体的数量 b o x l e n g t h待装物体的长度 b o x w i d t h 待装物体的宽度 b o x h e i g h t待装物体的高度 剩余空间的数据包括以下字段 r _ x ( r e s t x )剩余空间左下后角坐标的x 轴值 r _ y ( r e s t y )剩余空间左下后角坐标的y 轴值 r _ z ( r e s t z )剩余空间左下后角坐标的z 轴值 r _ l e n g t h ( r e s t l e n g t h )剩余空间沿着集装箱长度方向的长度 r _ w i d t h ( r e s t w i d t h )剩余空间沿着集装箱宽度方向的长度 r _ h e i g h t ( r e s t h e i g h t )剩余空间沿着集装箱高度方向的长度 ( 括号前的表示方法表示剩余空间的表字段，括号内的表示方法表示具体值，它们 的具体含义相同) 物体在集装箱内放置位置的数据包括以下字段 b o x n o 放置物体的标识符代号 1 3 沈阳工业大学硕士学位论文 p _ x物体在集装箱内放嚣的左下后角坐标的x 轴值 p _ y物体在集装箱内放置的左下后角坐标的y 轴值 p _ z物体在集装箱内放置的左下后角坐标的z 轴值 p _ l e n g t h物体在集装箱内沿着x 轴放置的长度 p _ w i d t h物体在集装箱内沿着y 轴放置的长度 p _ h e i g h t物体在集装箱内沿着z 轴放置的长度 其中，待装物体的数据和剩余空间的数据都是输入数据，物体在集装箱内放置的位 置数据是输出数据。三者的关系如图2 4 ： 图2 4 数据关系图 2 4 系统的开发环境 2 4 ，1 软、硬件平台 硬件平台：p u 配置，1 2 8 m b 以上内存 软件平台：w m d o w s 9 x x p 2 0 0 0 操作系统，c - h - b u i l d e r5 0 ，o p e n g l 2 4 2 开发工具 c + + b u i l d e r 是一个3 2 位c - h 语言的w i n d o w s 应用程序快速开发环境工具的总称。 它提供集成的可视开发环境，包括代码编辑、可视化用户界面设计、工程管理、编译和 调试等多项应用程序的开发功能。 1 4 沈阳工业大学硕士学位论文 c + + b u i l d e r 是i n p r i s e 公司继i ) e l p b a 之后推出的又一款高性能可视化集成开发工 具。c + + b u i l d e r5 0 是该公司2 0 0 0 年推出的版本，它继承了以前版本简单高效的特点， 并溶进了当今软件领域的最新技术：设计过程可视、设计思想面向对象、利用a e t i v e x 和d l l 等功能使程序与其它w i n d o w s 程序交换数据和调用其它语言程序、利用第三方 控件可使用户编程更加迅速可靠等。同时c + + b u i l d e r 具有理想的数据库开发功能，提 供的数据库开发工具将有助于程序员开发出功能强大、晃面美观的数据库，c - h - b u i l d e r 5 提供了3 2 位数据库引擎b d e ( b o r l a n d d a t a b a s e e n g i n e 5 ，所有数据库连接的指令， 均会通过b d e 进行处理。b d e 支持桌面型数据库p a r a d o x 和d b a s e ，b d e 与o d b c 具 有良好的接口，可以直接存取a c c e s s 和f o x - p r o 等数据库。c + + b u i l d e r 5 还为用户编程 提供了功能繁多的数据报表控件。 与其他开发工具一样，c + + b u i l d e r 也提供了多媒体空间、图形控件和图像控件，而 且可以利用d i r e c t d r a w 和o p e n g l 进行深层次的开发“。 o p e n g l 是用于开发简捷的交互式2 d 和3 d 图形应用程序的最佳环境。o p e n g l 自 1 9 9 2 年出现以来，逐渐成为工业上应用最广泛的支持2 d 和3 d 图形的应用程序编程接 口，并出现了成千上万的基于各种计算机平台的应用程序。o p e n g l 通过集成大量的渲 染、纹理映射、特殊效果和其他强大的可视化函数，使得其应用程序更加新颖，并大幅 度加速了图形应用程序的开发。 o p e n g l 是一个与硬件无关的编程接口，可以在不同的硬件平台上得到实现，而且 目前许多通用软件都支持o p e n g l 。用o p e n g l 制作的三维模型更容易对其进行各种变 换，呈现在用户面前的三维真实感图形更方便、更真实船“删。 1 5 沈阳工业大学硕士学位论文 3 系统总体设计 本课题的中心问题是解决物体在集装箱内的放置问题，最终的目标是使集装箱的空 间利用率达到最高。剩余空间的划分与描述是物体放置的基础，要保证在物体的放置过 程中满足集装箱装入中的约束条件以及对剩余空间的准确描述。要想提高集装箱空间的 利用率，必须通过有效的放置算法来实现。同时，剩余空间的合并也可以提高集装箱空 间的利用率。 本文为了降低计算的复杂度，把集装箱分按层分解，以最大填充层空间为目的，在 层内对物体进行组合填充，同时在层内及不同的层间进行剩余空间的结合，所以物体的 放置又不单单局限于层的划分。本课题通过层布局来简化三维问题的复杂度，在层内优 先对大物体进行组合，因为不仅大物体占用较多的资源，而且优先考虑对大物体进行组 合可以增加集装箱的稳定性，但是对所有的物体进行组合，消耗的时间过长，空间的复 杂度也较大。针对这个问题，本课题提出了组合方法与启发式相结合的方法，在保证时 间的前提条件下，使用限制组合方式来提高空间利用率。 由于集装箱是侧面开门的封闭型结构，因此，本课题中物体的装入是沿着集装箱的 长度方向由里n 9 l - 的放置，在沿着集装箱宽度方向放置物体时候，采用由下往上的方 向。这种装入顺序符合集装箱的结构特点以及装入中实际操作的要求。 3 1 物体放置的策略 本文研究的物体都是盒式长方体。对于物体的放置，总是采用由下到上，由里n ； l - 的顺序。物