（计算数学专业论文）集装箱铁架装载的优化模型研究.pdf

摘要 集装箱运输已成为国际贸易的最优运输方式。集装箱装载是集装箱运输过程 的一个重要环节，是指将各种尺寸的物品按照一定的约束条件放入一定容量的容 器，以获得某种意义上的最佳效益。集装箱装载问题是一个具有复杂约束条件的 多目标的优化组合问题，在理论上属于n p 完全问题，其求解是极为困难的。 集装箱铁架装载问题是一种特殊的集装箱装载问题，目的是寻求一种满足既 定约束条件下将货物装入集装箱铁架上，又使得集装箱的利用率最大的装载方 案。目前关于该问题的求解普遍存在着低利用率和低效率的问题。 针对以上两个关键问题，本文重点研究了集装箱装载的优化模型和相关求解 算法，针对集装箱装载的相关问题，本文开展了以下工作： 1 ) 通过研究集装箱装载的相关模型，建立了一个新的优化模型； 2 ) 根据所建立的新模型，提出了一种新的启发式自适应算法来求解模型； 3 ) 通过模拟实验，得到了较好的结果，表明了新优化模型和求解算法的可行 性和有效性； 4 ) 针对集装箱铁架装载问题，通过调查分析厦门某公司的需求，并且结合实 际的装载约束条件，有目的地改进了模型，优化了算法，并且研究设计出 一套“装柜王一铁架版 软件。该软件在预定集装箱数量时提供了准确的 依据；提高了集装箱的利用率；以3 d 图形方式给出每件货物在集装箱铁 架上的准确位置，并给出了打印的装载方案，以指导工人装载，提高工作 效率，从而达到提高企业经济效益的目的。 关键词：集装箱装载；优化模型；启发式 r e s e a r c ho no p t i m i z a t i o nm o d e l so fc o n t a i n e r i r o ns h e l fl o a d i n g a b s t r a c t c o n t a i n e rs h i p p i n gh a sb e c o m et h eb e s tm e a i l so f t r a n s p o r t a t i o ni nt h ei n t e r n a t i o n a l e c o n o m ya n d t r a d e a sa k e ys t e pi nt h ec o n t a i n e rt r a n s p o r t a t i o n ，t h ec o n t a i n e rl o a d i n g p r o b l e m ( c l p ) c a nb ef o r m u l a t e da sf o l l o w s ：g i v e nas e to fb o x e sa n dac o n t a i n e r , f i n d i n gt h es u b s e to ft h eb o x e sw i t hm a x i m u mt o t a lv o l u m e ，w h i c hc a nb ep l a c e di n t h ec o n t a i n e rw i t hs o m ec o n s t r a i n s t h ec l pi san p - c o m p l e t ep r o b l e m ，w h i c hc a n n o tg i v ea no p t i m a ls o l u t i o nw i t h i nar e a s o n a b l et i m el i m i t c o n t a i n e ri r o ns h e l f l o a d i n g ( c i s l ) i sas p e c i a lc a s ei nc o n t a i n e rl o a d i n g ，w h i c h a i m sn o to n l yt os e tg o o d si nt h ei r o ns h e l fw i t hs o m e c o n s t r a i n s ，b u ta l s ot om a k et h e l o a d i n gw i t hg r e a tc a p a b i l i t y b u tl o we f f i c i e n c yc o m m o n l ye x i s t sc o m m o n l yi nt h i s a r e a i nt h i st h e s i s ，r e s e a r c hf o c u so nt h et w om e n t i o n e da b o v e ，a n dt h eo p t i m a lm o d e l a n ds o l v i n ga l g o r i t h ma r ec r e a t e d 1 ) t h r o u g hr e s e a r c h i n go t h e rr e l a t i v em o d e l ，an e wo p t i m a lm o d e li sd e v e l o p e d 2 ) a st ot h en e wo p t i m a lm o d e l ，h e u r i s t i c & s e l f - a d a p t e da l g o r i t h mi sp r o p o s e d 3 ) t h r o u g ht h ed a t as i m u l a t e d ，i tc a ns t a t et h a tt h en e wm e t h o di sa v a i l a b l ea n d e f f e c t i v e 4 ) w i t ht h ec o m b i n a t i o no fs c i e n t i f i ca n dr e l a t i v er e s e a r c h i n g ，s o f t w a r en a m e d k i n g o fl o a d i n gv e r s i o no fi c o ns h e l f i s d e v d o p e d w i t hh e l po ft h i s s o f t w a r e ，c l i e n tc a ng e tt h ee x a c ta m o u n to fc o n t a i n e r sn e e dt ob o o k f u r t h e r , t h e3 dg r a p h i cs h o wc a nh e l pl o a d e rt ol o c a t et h ee x a c tp l a c e a l lo fa b o v e c a nr a i s et h er e t u r na n de f f i c i e n c yi nt h ee n t e r p r i s e s k e y w o r d ：c o n t a i n e rl o a d i n g ；o p t i m i z a t i o nm o d e l s ；h e u r i s t i c 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。 声明人( 签名) ： 铂、弓 7 年f 月7 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其他指定机构送交论文的纸质版和 电子版，有权将学位论文用于非营利目的的少量复制并允许论文进入 学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检 索，有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密 后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密() 作者签 导师签 日期：竹 日期一哕 ( r7 e t ， f 月7 日 第1 章绪论 第一章绪论 随着经济全球化和区域经济一体化进程的加快，在全球贸易强劲增长的背景 下，目前大约有9 0 的包装货物采用集装箱运输【1 1 。因此，对集装箱装载问题 ( c o n t a i n e rl o a d i n gp r o b l e m ，以下简称c l p ) 的研究在国内外备受关注，这里我们 将对集装箱装载问题的研究现状以及存在的问题进行阐述，最后对本文研究内容 以及本文的结构安排等进行总体概述。 1 1 研究背景及选题意义 随着海峡西岸经济区建设的全面推进，厦门经济迈向新一轮跨越式发展。厦 门以港立市，厦门港集装箱吞吐量在2 0 0 6 年已突破4 0 0 万标箱，名列全国第7 位，跻身世界2 0 强【2 】。同时，“厦门港是中国石材进出口最大的口岸，其石材 进出口总额已连续多年居全国首位，并且所占比例逐年提高。2 0 0 6 年厦门口岸 石材进出口9 3 0 万吨，金额2 3 亿美元，占全国石材进出口6 0 以上。 【3 】由于 2 0 0 6 年1 1 月，日本农林水产省决定，自2 0 0 7 年4 月1 日起，对进口产品的木 质包装实旌国际植物检疫措施第1 5 号标准( i s p m l 5 ) f 4 】。这将影响广大出口企 业尤其是木质包装用量较大的输日石材企业，主要是由于木质包装会增加不少附 加的熏蒸费用。而厦门市岚磊进出口有限公司( 以下简称岚磊公司) 是以生产和 贸易为一体的综合性企业。主要经营各式墓石，外栅，雕刻品，工艺品，建筑材 料等，产品远销欧美，日本，东南亚等地。岚磊公司为了降低成本，研发了种 可回收利用的铁架。在实际集装箱运输过程中，并使用这种铁架时，石材包装只 需用到熏蒸的木质托盘和太空袋，一定程度上可以降低成本。 然而，这是一种崭新的装载运输方式，到目前为止，将石材装到集装箱铁架 上的工作完全依靠人工调度来完成。调度员在现场仅凭经验估计被装入各种尺寸 石材的数量以及所需集装箱数，并开出装载单据。然后，装载工人按照单据将石 材放入集装箱。这种操作程序存在四个方面的问题： 1 ) 不能根据客户下的订单准确预测集装箱的数量； 2 ) 虽然调度员经验丰富，但是只凭直观经验估计出来的数字却很难保证集装 集装箱铁架装载的优化模型研究 箱的高利用率； 3 ) 装载工人没有任何装载方案的依据，完全是随意地或经验式地装载，造成 石材摆放不合理，导致集装箱低利用率； 4 ) 装载工人在装载时，由于剩下的石材不好装入，必须把某些已被装入的石 材取出，重新装载，甚至出现装载单上的石材不能装入而重复改写单据的 现象，降低了工作效率。 岚磊公司在这个石材运输环节中的这种人工装载方式无形中增加了产品的成本， 降低了企业的经济效益。 从实际问题来看，随着现代化生产的飞速发展，人们对货物运输提出了更高 的要求，如何快速有效地将货物装载成为生产行业迫切需要解决的一个重要问 题。解决集装箱装载问题，将直接降低运输成本，为生产部门和运输部门带来巨 大的经济效益。因此，研究和解决集装箱装载问题也就有了非常重要的现实意义。 从理论角度来看，集装箱装载问题是n p 完全问题【6 】，研究和解决集装箱装载问 题也会影响到许多领域的优化策略问题。集装箱装载问题实际上是一类三维物理 空间裁减装填问题。这种局限于物理空间内的裁减装填又可被称作“空间裁减装 填问题”。如果我们把裁减与装填问题抽象化，会发现对这类问题研究广泛适用 于其它许多领域。换句话说，很多其它领域的问题实际上就是裁减与装填问题， 这种进一步的理解为探讨这类问题注入了新的活力。例如，如果将时间参数当作 前述“空间裁剪装填问题”的某一维数据，那么计算机系统结构中的流水线指令 处理问题和多处理器调度问题就是一类典型的裁剪装填问题；计算机内存的分配 从某种意义上看也是一种裁剪装填问题等等。这类问题可被称作“非空间裁剪装 填问题 。所有在“空间裁剪装填问题”中提出的裁剪或布局算法都与“非空间 裁剪装填问题”有着直接的联系，这使得对裁剪与装填问题这一领域的研究工作 有了更深远的意义。同时，其它许多三维布局问题( 如机械零件的布局、电子元 器件的布局等) 实际上也是同一类问题。另外，由于装填问题与裁减问题之间的 天然联系【5 】，这类问题的解决方案同样适用于许多三维裁减与下料问题。 本文就是针对上述石材运输环节中所存在的问题着重进行如下工作：通过研 究集装箱装载问题的模型和求解算法，结合实际的装载约束条件，建立了一个新 的数学模型，提出一种新的启发式算法来解决集装箱装载问题，并且在厦门东晨 科技有限公司( 以下简称东晨公司) 资助下，调查分析岚磊公司的需求，针对上 2 第l 章绪论 述集装箱铁架装载问题( 一种特殊的集装箱装载问题) 进行优化研究，并设计出 一套“装柜王一铁架版软件。该软件在事先根据客户下的订单预定集装箱数量 时提供了准确依据。同时，一方面提高了集装箱利用率；另一方面，以3 d 图形 方式给出每件石材在集装箱铁架上的准确位置，并给出了打印的装载方案，以指 导工人装载，提高装载的工作效率。 1 2 研究现状及存在问题 集装箱装载问题( 以下简称c l p ) 的研究始于国外。自1 9 3 9 ( k a n t o r o v i c h ) 、 1 9 4 0 年( b r o o k s 等) 以来【6 】，由于行业的需要，国外开始出现裁剪与装填问题 ( c u t t i n ga n dp a c k i n g ，以下简称c & p ) 的研究。研究的重点开始集中于一维、 二维的情形下，且多见于使用确定性算法。确定性算法主要包括线性规划、整数 规划和动态规划等传统算法。确定性算法只能解决小规模问题。由于c & p 问题是 n p 问题，当情况复杂或问题增大时，确定性算法就会因为涉及的变量太多而大 大提高计算的复杂性，不能在合理的时间内给出最优解【刀。二十世纪八十年代后， 对三维c & p 问题的研究才逐渐展开。此时，随着问题求解空间的增大，确定性算 法将失去其原有的效果，取而代之的是各类启发式算法。启发式算法主要包括构 造型启发式、模拟退火、遗传算法和禁忌搜索等现代算法。作为c & p 问题的一个 重要分支，新西兰的g e o r g ej a 和r o b i n s o nd f 给出了c l p 的第一个启发式 算法【8 】。此后，许多科学家就不同层面的c l p 提出了各自的算法或解决方案，并 使用了公开的测试数据进行测试，以求探索一种解决问题的有效算法。迄今为止， 比较还没有一种算法能够肯定在各个方面优于其它，所以仍旧有许多人对c l p 进 行研究。 大部分研究都针对c l p 算法的研究，而对于c l p 相关的数学模型研究较少， 近年来比较经典的有文献 8 、 9 和 i o 等。c h e n 等【s 】于1 9 9 3 年提出了一个c l p 模型，但该模型设计过于复杂，需要根据实际应用问题来简化。s t o y a n 等在文献 9 】中提出的模型主要讨论是矩形和圆的布局问题，其不足在于它只涉及到二维 的情况。l o d i 等于2 0 0 4 年在文献 1 0 中主要针对二维装箱问题( b i np a c k i n g ) 等提 出了一个新的模型，该模型的成功地将时间复杂度降为o ( n l o g n ) ，然而它只是 局限于二维的情况。有关更详细的综述可参考文献 5 和 “】。d y c k h o f f 于1 9 9 0 3 集装箱铁架装载的优化模型研究 年在文献【5 】中对许多属于裁剪与装填的不同问题进行合理组织，并详细地介绍 了裁剪与装填问题，此外还给出了一套标准符号来描述它们的不同特征。在2 0 0 6 年，根据d y c k h o f f 的工作和1 9 9 5 年到2 0 0 5 年有关空间裁剪与装填问题( h at h e n a r r o ws e n s e ) 的4 0 0 多篇文章，w 萏s c h e r 等【l l 】指出了d y c k h o f f 对空间裁剪与装填 问题分类存在的不足，并给出了更准确分类方案( 如图1 1 ) 。值得一提地是，在 w i s c h e l 等的文章中，所有参考文献来源于e s i c u p 1 2 】。 i 吐嘲哺 爱画伊嘲斟嚏 c & p p t o b l o m 睁p a s 圈回国国国圉 图1 1 基本的裁剪与装填问题类型 资料来源：( e u r o p e a nj o u r n a lo f o p t i o n sr e s e a r c h 【1 u 目前，国内的集装箱装载问题( 包括广义的三维装载问题) 及其相关问题的研 究相对较少，下面简单介绍一下相关研究。 1 ) 北方交通大学机电工程学院的何大勇等人提出了一种利用三叉树结构 描述三维矩形物体布局状态的方法来解决集装箱装载问题。该算法是一个 构造型启发式算法。算法中，盒子的尺寸由计算机随机产生，算法没有提 到盒子的特征以及所属问题的类别；算法通过将布局空间依次分割为三个 方向的待布局空间，采用三叉树数据结构对三个空间分别装填；算法将整 个集装箱空间作为三叉树的根结点，将按一定优先级确定的第一个盒子放 在根结点的左、中、右三个子节点，再按深度优先的原则分别对这三个独 立的局部空间重复上述分解过程，直到没有待布局物体时为止；但是这种 算法没有处理空隙问题。 4 第1 章绪论 2 ) 天大机械工程学院的王金敏等人【1 4 】用标准模拟退火算法求解三维布局问 题。算法中给出了目标函数及约束条件，求解的初始温度和退火策略 ( u p d a t e ( t k ) = 0 8 5 0 9 9 ) 。该算法的初始解是采用随机解，且邻域解也是 通过随机移动操作产生；算法收敛速度较慢，同时没有明确给出和其它算 法的比较测试结果。该算法没有提到三维矩形物的种类情况。 3 ) 中国科技大学计算机科学技术系的曹先彬等人 1 5 , 1 6 1 先后给出了采用遗传 算法和免疫遗传算法解决装载问题的算法。他们的第一个算法是一个标准 遗传算法，该算法由下向上装填，所以不能很好地用于集装箱装载问题， 按照各盒子之间的宽度差、高度差以及装入盒子的总长与箱子之间的长度 差给出了适应度函数，编码为二进制编码，交叉算子采用两点交叉，变异 概率取为0 1 。他们试验的验证对象是4 0 个随机产生的小长方体和一个指 定尺寸的大长方体。 由于集装箱装载工作到目前为止大多还停留在人工阶段，所以，对这类问题 进行科学的研究并从理论上给出指导显得至关重要。集装箱装载问题在理论上已 被证明为n p 完全问题，求解时具有相当的时间复杂度和空间复杂度，在一个合 理的时间内无法确定最优解。所以为研究工作带来了一定的难度。目前求解这类 问题通常采用不确定性算法，也就是通常所说的启发式方法，这类算法凭借有效 的优化策略减小搜索空间的规模，缩小搜索范围，从而尽可能在有限的时间内找 到问题的最优解或近似最优解。 在研究集装箱装载问题时，可以研究和借鉴与之相关的问题的相应算法。在 三维装填问题中，如下几类问题与集装箱装载问题极为相似： 1 ) 背包装入问题( k n a p s a c kl o a d in g ) 在经典的背包问题中，有玎个体积为v 的小物体。每一个要装入容器( 即 背包，总体积为b ) 中的小物体都具有一个与之关联的效用值( p r o f it ) a ， 背包问题的目标就是从所要装入的所有小物体中找到一个子集，使得装入 容器( 背包) 的这些小物体的效用总值达到最大【5 9 1 。如果我们将这些小物体 的效用值设定为它们的体积，则该问题就是一个最大化空间利用率的问 题。 2 ) 装箱问题( b i np a c k i n gp r o b l e m ) 5 集装箱铁架装载的优化模型研究 原指单元装载问题，常见于一维和二维的情形，指如何向个数最少的尺寸 为1 的箱子装入刀个尺寸不超过1 的物品。现在装载问题一般不再有单元 的限制，而是泛指如何将所有给定的小物体装入给定尺寸的箱子中，以使 所用箱子的数量最少，就三维装载问题而言，与集装箱装载问题中的多集 装箱问题没有明显区别。 3 ) 货盘装填问题( p a l l e tp a c k i n gp r o b l e m 或p a l l e tl o a d i n gp r o b l e m ) 原指将同一规格的长方体箱子按某种方式码放在一个矩形货盘或货架上， 从而使所码放货物的总体积最大。现在一般不再有“同一规格”的限制。 货盘装填问题的最大特点是，货盘或货架本身只有一个矩形底座，并不是 一个三维长方体，因而货物码放时的稳定性( l o a ds t a b i l i t y ) 是此类问题 必须考虑的一个重要约束，即必须保证货物不会从上面翻滚下来。而集装 箱装载问题则可不必加上这个约束。 事实上，只要在一定意义上能够给出令客户满意的解，就具有很大的实用价值。 所以，尽管各类启发式方法( 包括智能化搜索的启发式算法) 并不一定能够给出最 优解，但足以满足实际问题的需要。 就国内情况而言，除去几篇相关的文章外，对这类问题领域的专门研究相对 较少。虽然五十多年来，特别是近十多年，对集装箱装载问题研究取得了不少进 展，有些软件系统( 如装柜王【5 6 】，装柜专家5 7 】等) 投入实际的应用中，然而，集 装箱装载方面还是普遍存在以下一些问题： 1 ) 由于集装箱问题是n p 完全问题，随着求解规模的扩大，不能在有效确定 的时间内求得最优解； 2 ) 目前主流的算法大多数只考虑单一集装箱装载的优化问题，而未考虑多个 集装箱装载问题； 3 ) 很多算法启发式算法未考虑剩余空隙，其实，通过有效的优化整合，可以 有效的利用剩余小空隙，提高装载率； 4 ) 很多算法未考虑约束条件，通常实际的集装箱装载存在很多约束条件，若 不考虑约束条件，基本上没有实用价值。 本文以最大空间利用率为目标，建立针对实际问题的模型，并力图找出前人 算法中存在的问题，探讨一种更为有效的算法，并结合实际问题，给出解决方案。 6 第1 章绪论 1 3 主要研究内容及创新点 本文在参考了国内外的有关文献和书籍，对集装箱装载问题及其相关问题做 了大量研究的基础上，对比分析了现有多种模型和求解算法的优劣，提出了一种 集装箱装载的新模型和求解算法，并取得了较好的效果。此外还实现了相关的软 件系统，包括输入界面及三维图形输出和二维装箱方案打印部分。 本文的重点在于分析集装箱优化模型的设计和模型求解算法。常用的模型通 常过于抽象或复杂化，且其相关的求解算法有一个共同的特点，即在装载时每个 盒子被作为单独的个体予以考虑，致使在算法中存在三个突出问题：一是算法速 度，不能把一类盒子作为一个整体，而是逐个盒子的搜索处理，势必大大降低算 法的时间效率；二是对集装箱本身的空间利用率的影响，孤立地考虑每个盒子， 会直接造成集装箱空间地浪费；三是工人地装载效率，把一类盒子作为一个整体 考虑，会便于盒子地装卸工作，提高实际地装卸速度。基于以上分析，本文提出 了“整体装填”的思想，并把模型设计和求解算法的重点放在整体装填策略上。 本文的主要创新点如下： 1 ) 建立一个集装箱装载问题的新模型m c l ( m o d e lf o rc o n t a i n e rl o a d i n g ) ： 2 ) 根据新模型，以及改进了启发式规则，整合优化了剩余空隙，提出了一种 新算法，本算法可提高货物的装载率； 3 ) 新模型和新算法专门针对集装箱铁架装载问题进行优化处理； 4 ) 软件设计综合了插件管理技术，o p e n g l 和数据库技术等多种技术。使用 m i c r o s o f tv c + + n e t 等工具进行开发。 1 4 本文结构安排 本文共分为五章，各章的内容如下： 第一章绪论：介绍了本文的研究背景和潜在意义、集装箱装载问题在国内 外的研究现状等，最后简述了本文的研究内容以及创新点。 第二章集装箱装载问题概述：介绍了c & p 问题，以及c l p 的一般性描述、 分类、相关的经典模型及其c p l 各种经典算法。本文针对经典模型 存在过于复杂化或抽象化，结合实际指出了本文新模型提出的缘由； 并通过研究构造型启发式、模拟退火、遗传及其禁忌搜索等算法和 7 集装箱铁架装载的优化模型研究 比较，指出了算法的改进思路。 第三章集装箱铁架装载的优化模型：详细阐述了集装箱装载的问题描述、 新优化模型的设计和求解的新算法。该章重点放在整体填充策略和 剩余空间进行优化整合。最后，通过综合实验，给出了测试报告。 实验结果表明我们的模型和算法的可行性和有效性。 第四章“装柜王一铁架版 系统：介绍了o p e n g l 技术，以及系统的设计思 想和系统架构，并结合系统界面简单介绍了相关的功能。 第五章总结与展望：对所做工作进行总结，并对未来的研究做了展望。 8 第2 章集装箱装载问题概述 第二章集装箱装载问题概述 集装箱装载问题是一个三维装载问题，这类问题属于裁剪与装填问题。而以 上问题则可以归结为优化组合问题( 如图2 1 ) 。在本章中，先简单介绍相关的裁 剪与装填问题，然后再阐述集装箱装载问题模型及其算法概述。 2 1 裁剪与装填问题 裁剪问题，通常是指在一种材料上寻找各种形状的最佳布局以使材料浪费最 少。装填问题则通常是指将若干小的物体以最佳组合装入一个大的容器从而使空 间利用率最大5 1 。 图2 1 裁剪与装填问题分类图示 资料来源：图参考了( e u r o p e a nj o u r n a lo f o p e r a t i o n sr e s e a r c h 【5 1 对裁剪与装填问题的研究最早出现在大约五十年代。当时人们试图使用线性 规划求出在一大片材料上合理放置矩形的最优解。但是，随着问题规模的增大和 不规则形状的引入，人们发现不可能遍历全部的搜索空间，于是近年来出现了针 对不同的材料、形状、目标和约束等情况的裁剪装填问题的各类算法研究n 1 1 。然 而，尽管裁剪与装填问题有很强的工程代表性，求出它的最优解却很难，其主要 原因是，此类问题属于组合优化问题，它的求解空间大的惊人，事实上，这类问 题涉及面广、潜在价值巨大，同时又具有较高的复杂度，因此吸引了许多领域的 许多研究人员对它进行深入的研究，使它成为涉及到管理科学、工程科学、信息 与计算机科学、数学和运筹学等众多学科的一个重要研究领域【3 0 1 。集装箱装载问 9 集装箱铁架装载的优化模型研究 题属于三维裁剪与装填问题，下面将概述集装箱装载问题。 2 2 集装箱装载问题 所谓集装箱装载问题，简单地说，是指如何将一些小的长方体盒子按照某种 方式装入集装箱。集装箱装载问题是货物运输过程中普遍存在的一个重要环节。 它是一类组合优化问题。如何给出一个合理的布局及装载方案，以在保证装运的 稳定性( 防止运输中货物的移动而导致的货物损坏) 、多目的地运送、负重限制、 箱体内的重量分布、装载的效率等问题地基础上，使集装箱的空间利用率达到最 大，是这类问题的主要目标。 2 2 1 集装箱装载问题分类 集装箱装载问题并不是一类单纯的问题。它又可以细划为许多不同的分支， 这些分支问题具有不同的分类标准、不同的目标函数和不同的结束条件。例如， 一种常见的划分依据为：是将给定的大批货物全部装入多个集装箱( 以使所需集 装箱个数最少) ，还是将尽可能多的货物装入一个集装箱；而另外一种分类原则 可以确定为是否考虑约束：如是以集装箱的重量限制为主要约束而使得集装箱的 空间利用率最大呢，还是以货物重量分布是否均匀为主要约束来最大化空间利用 率，还是不考虑约束，仅以使空间利用率最大为目标；而仅就空间利用率而言， 还可以分为：是以某类货物占有集装箱的体积最大为目标。除此之外，集装箱装 载问题还会涉及到其它方方面面的考虑。 c p l 有许多不同的分类方法。其中最主要的一种分类方法是由德国的h d y c k h o f f 提出的【5 】，其类别的划分定位在所需集装箱的数量上，即：给定的一组 货物( 放于长方体的容器内，以后简称盒子) 必须完全装入集装箱，还是允许剩下 的一些货物。前者实际上是多集装箱装载问题，以所需要的集装箱个数最少为目 标；而后者是单集装箱问题，以装入集装箱的货物总体积最大为目标。另外一种 重要的分类方法是由德国的a b o r t f e l d t 提出的【2 2 1 。这种方法的依据是按照欲装 入的货物情形来划分。按照这一方法，c l p 被分为三类： 1 ) 盒子的规格完全相同，即单一尺寸的盒子的装载问题，这类问题被称为“同 类”( h o m o g e n e o u s ) 问题； 2 ) 盒子有很多不同的类型，这类问题被称作“强异类”( s t r o n g l y h e t e r o g e n e o u s ) “1 第2 章集装箱装载问题概述 问题； 3 ) 盒子只有少数几种不同的类型，但每类盒子具有一定的数量。这类问题被 称作“弱异类 ( w e a k l yh e t e r o g e n e o u s ) l h - j 题。 其它的分类方法还有很多，多半集中在对问题的不同约束上。如是否考虑重量的 限制、重量的分布，以及多目的地运送问题等等。 2 2 2 集装箱装载问题的一般描述 为了简化问题的描述而又不失一般性，这类问题通常有如下假设【剐： 1 ) 货物被装在一个长方体的盒子内，盒子的几何中心即为其重心，盒子本身 的挤压形变将被忽略。 2 ) 集装箱是具有标准尺寸的长方体箱体，后部开门，它的深度( 即长度) 、宽 度和高度被分别看作笛卡儿坐标系的x 轴、】r 轴和z 轴方向。 3 ) 货物理论上可以放在集装箱的任意位置，但不能超出集装箱的容纳范围， 也不能与其它货物交叠放置，也就是说，箱内货物的总体积应小于等于集 装箱的体积；货物的摆放必须与坐标轴平行或正交，而不能斜放；一种货 物可与其它任意类型的货物相邻。 4 ) 不考虑集装箱的重量限制、货物在箱内的重量分布等问题。 为了便于描述，本文在一个统一的笛卡儿坐标系中( 图2 2 ) 讨论模型和各种算法。 2 2 3 相关数学模型 图2 2 集装箱坐标系 这里我们先介绍一下集装箱装载问题相关的经典数学模型。由于集装箱问题 是优化组合问题，我们先考虑通用的组合优化模型【1 7 】： 集装箱铁架装载的优化模型研究 m i n 厂( x ) s t g ( x ) x d ( 2 1 ) 其中f ( x ) 为目标函数，g ( x ) 为约束函数，x 为决策变量，d 表示决策变量 的定义域。一个组合最优化问题可以用( d ，f ，厂) 表示，其中f 表示可行解区域， f = 缸lx d ，g ( x ) o ) ，f 中的任何一个元素称为该项问题的可行解。厂称为目 标函数，满足f ( x ) = r a i n ( f ( x ) i 石f ) 的可行解称为该问题的最优解。组合最优 化的特点是可行解集合为有限点的集合。所有的集装箱装载问题都可以用该模型 来刻画。不过由于该模型太抽象了，因此在实际应用中比较困难。 羁i髓 b l i n i m i z 。e 嘭q ，唧一一吼- 吩 j li - t s u t j ! i c c tt o 善l + 臃+ 如f + 嘶l + 匕。 耐x k + l 一露谴) 。m f o ra l ll ，k ， i 七， 善 + 魄k + 瓠。彬哇+ 气矗娃g 善i + l 一觑蠢) m f o ra l lf 。惫，七， 辨年绥+ + a f ，+ 乃 一欺+ l 一) m f o r a l lf ，惫，l k ， 岁量+ 口m ，+ a + l 蟑+ 玉体墨+ ( 1 一d 0 ) 尉 f o ra l lj ，。 j 七， + 吒卉耐+ 氇。十辫厶i 墨z 詹十( 1 一t 治) 。m f o ra l ! l ，惫， ；惫， j z 量+ - a 娃+ 级。w z 七+ p t ，娃蔓+ ( 王一氩) 。艏衙a l lf ，k ，f k ， + 钆露+ 白七十也是+ e 豫十缸 - - 8 0 + s t j l 衙棚lf ，詹，j ， j f 老， 棚 斯一l f o ra l li ， j 蕾l s o 墨掰携， f o r a l i l j 鳓+ 巧。k + 嘞。4 - ， 矗，i 墨0 + ( 1 一) + 脚f b f a l ll 。j f ， 觐+ 诉伸k 争瑰；+ + 墨彬+ ( 1 一断) 。m 如瞪a ui ， 毛+ 吒。 矗+ 吼w a + p ：i f 墨吩+ ( 1 一& ，) 掰 细a l lf 。歹， 0 ，心i ，i ，f ，靠撕， ，j | ；i 鲥，4 捷，咄，d 汝，i i k ，s o ，n j 案oo r1 ， 缸，嚣，毛o 图2 3m i p 模型 资料来源：( e u r o p e a nj o u r n a lo f o p e x a t i o mr e s e a r c h ) s i 由此，c h c n 等【8 1 于1 9 9 3 年提出了关于c l p 的m i p 模型，该模型定义了很 多变量。由于m 口模型太复杂，定义的变量过多，对于小问题的解决是可行的。 但是，随着问题规模的扩大，求解空间也随着的急剧增大，不能在确定的时间内 1 2 第2 章集装箱装载问题概述 找到最优解。该模型如图2 3 所示。 2 3 模型求解的算法 这类启发式算法凭借专家经验建立直接的搜索策略和搜索规则，并依此规则 在搜索空间中求解由于采用经验机制，缺乏严格的理论证明，所以这类算法无 法保证找到最优解。而另一方面由于规则的建立具有一定的合理性，通常能得出 一个令人满意的可行解。再加上算法描述直观，易于实现，非常具有实用价值， 所以，大量的研究集中在这类算法上。 2 j 1 构造型算法 文献 6 0 中g e o r g e 和r o b i n s o n 首先采用构造型启发式算法来解决集装箱装 载问题。他们把研究的问题集中在多种盒子( 8 种至2 1 种，且每种盒子的数量很多) 的装填上，这些盒子可以以任意方向放置。在算法中他们首次给出了层的概念， 这一概念对后来相继涌现出来的算法产生了很大影响。 他们的算法中有两个非常关键的地方：一是层的概念的引入，二是如何确定 待装填盒子的优先顺序( 即应该先装入哪类盒子) 。至于应把第一个盒子的哪个尺 寸作为层的深度，g e o r g e 和r o b i n s o n 并没有详细提及。还有一点需要特别提及。 如果一层中出现了不同类型的盒子，很可能会使这一层的横截面产生一个或几个 凹陷( 称之为被拒绝的空间r e j e c t e ds p a c e s ) 。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 把 凹陷的宽度称为f l e x i b l ew i d t h ) 保留起来，在对新层进行装填时，将新层中的 剩余空间与其前一层的凹陷空间有效的融合在一起，作为新层中统一的可用空间 一并处理，从而提高了空间的利用率。 g e o r g e 和r o b i n s o n 的算法中，有许多值得借鉴之处。如按层装填的思想使得 算法在一定程度上得以简化；优先级的确定可以保证较整齐地利用集装箱空间； 融合被拒绝的空间以提高集装箱的空间利用率等等。 g e h r i n g 等人的算澍6 1 】同样是基于层的一种构建方法。与g e o r g e 和r o b i n s o n 研究的问题不同，在g e h r i n g 等人研究的装载问题中，虽然盒子仍然可以按任意 方向放置，但盒子的尺寸无一相同，属于强异类问题。所以，g e h r i n g 等人的算 法中没有“打开状态”与“非打开状态 ，而且盒子的优先级只是按体积大小来 1 3 集装箱铁架装载的优化模型研究 确定，体积越大，优先级越高，这样做可以保证集装箱的空间利用率。g e h r i n g 等人同样将当前优先级最高的盒子做为一层中的第一个盒子，并且为这个盒子起 了一个名字，叫做l d b ( l a y e rd e t e r m i n i n gb o x ) 。先将l d b 按任意一种方式( 显然， 一个长方体共有六种放置方式) 放入层的起始位置，并以这种方式对应的l d b 深度 作为本层的深度。本层其它盒子的放置不得超过这个深度。与g e o r g e 和r o b i n s o n 算法不同的是，g e h r i n g 等人在用盒子装填每一层时尝试了另外一种摆放顺序， 即：一旦一个盒子被装入，盒子会在正右方、前方和上方产生三个剩余空间，在 装入下一个盒子时，以前一个盒子为基准，按照先向旁边、再向前面、最后向上 的遍历方式，选取优先级较高的盒子进行装填。由于最后才沿高度方向摆放，即 在一层中先摆满水平的一条，再向上摆放另一条，所以，g e h r i n g 等人要求一层 中其它盒子的高度不能超过l d b 的高度。一层装填完毕后，再重复刚才的做法， 沿集装箱深度方向装填新层，直至没有剩余的盒子或集装箱没有剩余空间。由于 g e h r i n g 等人处理的是强异类问题，所以也采用了逐个处理盒子的方法。该算法 的优点是，通过充分变换第一层中l d b 的放置方式以及将优先级置后的盒子充当 第一层的l d b ，产生了多种装载方案，从而为解的优化提供了更大的保证。 另外，算法不允许盒子在两层之间跨骑。这样可以保证各层独立存在，从而 可以互换层的位置以保证集装箱负载平衡。然而，上述算法存在两点问题： 1 ) 在对一层内部进行装填时，先水平摆满一条，再向上摆放另一条，这样做 带来的问题是：除非用某种填充物将盒子之间的高度差异填平，否则，这 种方式会因为盒子的高度不等造成盒子倾斜放置。而填平高度的工作会为 实际的装载工作带来困难。 2 ) 算法为保证集装箱的负载平衡，不允许盒子在两层之间跨骑，因而没有尝 试对盒子之间的空隙进行填充，这样做会大大降低集装箱的空间利用率。 针对集装箱装载问题，b i s c h o f f 和m a r r i o t t 提出了一种基于b i s c h o f f 和d o w s l a n d 技术的启发式算法( b i s c h o f f 和d o w s l a n d 算法是一种二维装填问题的优化算 法) h 1 。b i s c h o f f m a r r i o t t 算法对于盒子的放置方向同样没有限制。但是，在 这种算法中，要求每一层尽可能由单一类型的盒子组成，这种完全由单一尺寸的 盒子填充的层被称作一个“完全层 ( c o m p l e t el a y e r ) 。 他们所提出算法的构想是：先用某种标准确定盒子的优先级，然后取出较高 级别的盒子，分别尝试用它的长、宽、高充当层的深度。一旦层的深度确定，由 1 4 第2 章集装箱装载问题概述 于每一层盒子的尺寸完全一样，一层之内，深度这一维就可以不必再去考虑，剩 下的工作仅仅是一个二维装填问题，采用b i s c h o f f 和d o w s l a n d 的二维装填技术 ( 这种二维填充算法并没有被b i s c h o f f m a r r i o t t 详细描述) 就可以完成层的装 填。由于一层可能有三个深度，所以一层会有三种装填结果，从中选取是“完全 层 且横截面被装填的百分比最高的那一种方案。如果事先用b i s c h o f f 和 d o w s l a n d 技术计算出来的本层可被装填的某类盒子的数量大于这一类中待装盒 子的数量，即没有那么多尺寸相同的盒子能够把一层装满，则不能产生“完全层”。 那么就应暂时放弃对这种盒子的处理，而对另外一种类型的盒子进行装填工作。 这样一直进行下去，会有两种结果，一种结果是，所有待装填的盒子刚好放入所 有的“完全层”中，装载工作顺利结束，而更多的可能是，剩下的每一类盒子都 不可能形成一个“完全层”，对于后一种情况，该算法采用了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 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 算法，但它在用二维技术来解决三维技术，从而对问题进行 简化方面给了我们某种启示。 将针对多类盒子进行装载问题的算法用在单一类别盒子的装载问题上，未必 能得到满意解。所以，作为装载问题的一个特例，j a g e o r g e 给出了一种基于将 单一尺寸的盒子装入集装箱问题的算法嘲。在这个算法中，盒子可以任意方向放 置。这一算法完全采用了b i s c h o f f 和m a r r i o t t 提出的基于b i s c h o f f 和d o w s l a n d 技术的构建完全层的算法n0 1 。算法中唯一改进的一点是，给出了一种“集装箱旋 转 的方法。即允许集装箱在坐标系中绕y 轴或z 轴旋转，并改变坐标原点的位 置，从而使得原本将各层沿着集装箱的深度方向码放的工作变为沿宽度甚至高度 方向进行，这样会在一个更大的空间内找到满意解。当然，在实际装载工作中并 不旋转集装箱，而是按这种“旋转集装箱算法 得到的布局结果将盒子依次装入 集装箱内。 l o h 和n e e 的算法【1 1 】主要考虑到待装载的盒子有很多都具有相同的尺寸这一 特点。即，他们研究的是弱异类问题。在他们的算法中，层以水平的形态出现， 1 5 集装箱铁架装载的优化模型研究 各层由下向上码放，最终完成装载工作。为了构建平坦的截面