（计算机应用技术专业论文）基于多配送点限制集装箱装载问题研究及应用.pdf

中文摘要 本文对物流行业中实际存在的多配送点限制集装箱装载问题( c o n t a i n e r l o a d i n gp r o b l e m ) 进行了研究。目前，此类问题在实际操作中造成了效率和效益 低下。在这些问题中，本文着重研究了多配送点约束弱异类装箱问题，提出了一 种新的算法，这一算法提高了集装箱装载货物的空间利用率，并确保在到达某一 个配送点时，无需将其他箱子( 或货物) 移动的前提下将待卸货物卸下，提高货 物装载与配送的优化程度，提高了配送业务的工作效率。 文章首先介绍了问题的研究背景以及相关概念。其次，描述了目前对此类问 题的国内外研究情况，并且对几种经典算法进行了较为系统的分析和评测，指出 它们各自的特点和不足。再次，根据对不同算法的特点的分析比较发现，由于装 载问题是n p h a r d 完全问题，不存在有效时间内求得最优解的算法。针对目前在 实际操作中存在多配送点限制，本文采用构造启发式算法、贪心算法以及搜索树 算法相结合，以提高集装箱装载货物的空间利用率的问题，提高货物装载的优化 程度、提高配送业务的工作效率。 最后，本文作者利用v i s u a lb a s i c6 0 集成开发环境开发了一个基于上述实际 问题的集装箱装载程序。此程序能够满足本文提出的系统需求，能够在满足限制 条件下给出装箱利用率以及装箱货物清单，通过模拟实验得到了较以往算法更好 的测试结果，因此表明本文算法对于现实的装箱工作有一定的指导性。 关键词：装箱问题多配送点限制构造启发式贪心算法搜索树 a b s t r a c t t h et h e s i si sa b o u th o wt os o l v ec o n t a i n e rl o a d i n gp r o b l e m s ( c l p ) w i t h m u l t i - d r o pc o n s t r a i n st h a te x i s t sr e a l l yi nl o g i s t i c s a tp r e s e n t ，t h e s ep r o b l e mc a u s e l o w e re f f i c i e n c ya n db e n e f i ti np r a c t i c e a m o n gt h ep r o b l e m s ，t h et h e s i sf o c u s e so n w e a k l yh e t e r o g e n e o u sc l p i ti sa r c h e dt of i n do u tt h es o l u t i o nt ot h ep r o b l e m sa n d o f f e r san e wa r i t h m e t i c i tm a x i m i z e st h ev o l u m eu t i l i t yo f c o n t a i n i n gb o x e s i tm a k e s s u r et h a tw h e ne a c hd r o p - o f fp o i n ti sr e a c h e d ，t h er e l e v a n tb o x e sm u s tb ea v a i l a b l e ， w i t h o u tr e a r r a n g i n go t h e r s a sar e s u l t ，i to p t i m i z e st h em e t h o d so fl o a d i n ga n d d e l i v e r i n ga n di m p r o v e st h ee f f i c i e n c yo fd e l i v e r y f i r s to fa l l ，t h et h e s i si n t r o d u c e st h er e s e a r c hb a c k g r o u n da n dc o n c e p t i o n so f c l es e c o n d l y , i td e s c r i b e st h es o l u t i o n st ot h ep r o b l e m sh o m ea n da b r o a d ，c o m p a r e s t h e s ec l a s s i c a la r i t h m e t i c st h o r o u g h l y , a n dp o i n t so u tt h ev i r t u ea n d s h o r t a g eo ft h e m t h i r d l y , a c c o r d i n gt o t h ec o m p a r i s o na n da n a l y s i so nt h ec h a r a c t e r so ft h e s e a r i t h m e t i c s ，i ti sf o u n do u tt h a tt h ec l pi so n eo fn p h a r dc o m p l e t ep r o b l e m s ，t h e r ei s n oo p t i m u ms o l u t i o n p r e s e n t e di n r e a s o n a b l et i m e - l i m i t a t i o n f a c e dw i t ht h e m u l t i d r o pc o n s t r a i n ti np r a c t i c e ，t h i st h e s i su s e st h ec o n s t r u c t i o nh e u r i s t i ca r i t h m e t i c ， g r e e d ys o l u t i o n sa n dt r e es e a r c hf r a m e w o r kt oi n c r e a s et h ev o l u m eo ft h ep a c k e d b o x e sa n di m p r o v et h ee f f i c i e n c yo f d e l i v e r y f i n a l l y , t h et h e s i sg i v e sac o m p u t e r - b a s e dc l pp r o g r a mt of i n do u tas o l u t i o nt o l o a d i n g a n d u n l o a d i n gb o x e s ，u s i n g v i s u a lb a s i c6 0 i n t e g r a t e d - d e v e l o p i n g e n v i r o n m e n t t h ep r o g r a mc a dm e e tt h es y s t e mr e q u i r e m e n t sa n di m p r o v et h ev o l u m e u t i l i t yo f t h ec o n t a i n e ra n do f f e rt h el i s t so fb o x e su n d e rt h em u l t i - d r o pc o n s t r a i n t s b y t h es i m u l a t ee x p e r i m e n t s ，i tp r o v e st h a tt h ea r i t h m e t i co ft h et h e s i si sf e a s i b l ea n d e f f e c t i v ec o m p a r e dw i t ht h ef o r m e ra r i t h m e t i ci nf a c t k e yw o r d s ：c o n t a i n e rl o a d i n gp r o b l e m ，m u l t i d r o pc o n s t r a i n t ， c o n s t r u c t i o nh e u r i s t i c ，g r e e d ya r i t h m e t i c ，t r e es e a r c h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：琢甜讯 签字日期：江叼年占月垆日 学位论文版权使用授权书 本学位论文作者完全了解丕鲞盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：豫南1 i新签名：祝谰 签字日期：b 蛆年占月垆日签字日期：洒3 年6 月乒日 天津大学硕士学位论文第一章绪论 1 1 课题的背景 第一章绪论 进入2 1 世纪，全球经济一体化的进程明显加快，尤其是我国加入w t o 以 后，物流业迎来了空前的发展机遇。根据国内外物流业发展情况，可以将国际物 流的发展趋势归纳为信息化、自动化、网络化、智能化、柔性化、标准化、社会 化、精益化及绿色物流等。采用高科技手段，不断提高物流管理水平。 随着国内物流业的发展，物流相关技术的应用和发展受到越来越多的重视。 集装箱装箱问题作为物流配送过程中的一个关键性的技术，对提高配送业务的自 动化水平、提高货物装载的优化程度、提高配送业务的工作效率和规范业务流程 等方面都有重要的意义。 考虑实际的集装箱装箱现场工作：首先，货物装箱之前工作主要靠人工估算 完成，通过计算装载货物的体积与集装箱容积之比值，再利用经验值( 例如9 0 ) 乘以此比值是否小于0 9 5 ( 人工经验值) 来判断是否能装下这些货物，此经验值 是由装箱工人经过若干次装箱工作总结出来的，这个条件假如能满足的话，基本 上货物是能实际装入的。若不能装下，考虑将剩余货物装入下一个集装箱或者调 度一辆大一些的集装箱，或者考虑买家退掉剩余货物，下次再购买。原因很简单， 假如买家在上海，他在辽宁买了货物之后，经过装箱预测，发现还有2 件货物没 有装入，反正不能再开一个装箱单把这2 件货物装箱由辽宁运往上海，这样无非 加大了买家或卖家的运输成本，造成不必要的浪费；若能装下，然后再开具装箱 单，最后由装箱工人凭借人工经验进行装箱。考虑到人为因素，每个装箱工人都 有自己的装箱经验，而且每个装箱工人每次在装入同样货物时的方案可能都是不 同的，并不能得到象计算出的值那样装箱结果，所以装箱前又引入经验值来确保 不会出现货物装不进去的情况。假如出现此种情况，装箱单已经开出，说明这些 货物已被派出，只能考虑与同目的地其他买家的货物一起装箱派送。再者，考虑 一些具体的实际情况：物流公司在利用派送货物不只是一个买家的货物，而是多 个买家( 多配送点) 的；一个买家可能会购买多种货物；集装箱的载重量，货物 的承重能力等。通过以上分析可以看出，在考虑多条件限制的前提下，如何能够 天津大学硕士学位论文第一章绪论 快速给出一个能否装入的方案是非常重要的，而可视化的装箱方案显示系统似乎 对装箱过程并不重要，因为可视化的装箱方案显示系统是把一种比较理想的情况 显示出来以便指导装箱工作，由于具体装箱过程还会受到很多现场条件的限制， 装箱工人很难按照理想的方案实施装箱。比如：装箱工人不可能为了把一件货物 放置在理想位置而多次搬动该货物。 针对上述原因，本文选择多配送点限制集装箱装载问题研究及集成应用这一 课题，以解决当前物流配送环节面临的实际问题。旨在寻求面向现代物流企业实 用的优化配送算法，以期达到对现代货物配送装载业务有一个实用、有效的技术 解决方案的目的。 1 2 装箱问题的界定 装箱问题是复杂的离散组合最优化问题。所谓组合优化【1 】，是指在离散的、 有限的数学结构上，寻找一个满足给定条件，并使其目标函数值达到最大或最小 的解。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、 不连续的、多维的、有约束条件的、高度非线性的n p 完全问题。装箱问题也不 例外，同许多组合最优化问题，如旅行商问题、图的划分问题等一样属于 n p h a r d 问题【2 】。经典的装箱问题要求把一定数量的物品放入容量相同的一些 箱子中，使得每个箱子中的物品大小之和不超过盒子容量并使所用的盒子数目最 少。 从2 0 世纪7 0 年代初开始，装箱问题就引起了广泛的探讨和研究，然而装箱 问题可以追溯到1 8 3 1 年高斯( g a u s s ) 开始研究布局问题，因为装箱问题和布局 问题本质上是一样的，到现在己有百余年的历史，在文献上始见于1 9 3 0 年 k a n t o r o v i c h 的俄文文章( 1 9 6 0 年译为英语刊登在m a n a g e m e n ts c i e n c e s 上) 。虽 然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算方法。由于目前 n p 完全问题不存在有效时间内求得精确解的算法，装箱问题的求解极为困难， 因此，从7 0 8 0 年代开始，陆续提出的装箱算法都是各种近似算法，如下次适应、 首次适应、降序下次适应和调和算法等。， 装箱问题广泛存在于工业生产，包括服装行业的面料裁剪、运输行业的集装 箱货物装载、加工行业的板材型材下料、印刷行业的排样和现实生活中包装、整 理物件等。在计算机科学中，多处理器任务调度、资源分配、文件分配、内存管 天津大学硕士学位论文第一章绪论 理等底层操作均是装箱问题的实际应用，甚至还出现在一些棋盘形、方块形的数 学智力游戏中。装箱问题的研究文献分布面很广，在运筹学、计算机辅助设计、 计算机图形学、人工智能、图像处理、大规模集成电路逻辑布线设计、计算机应 用科学等诸多领域都有装箱问题最新的研究动态和成果出现，从这个角度来讲， 布局问题涉及到了工业生产的方方面面，也足以证明了装箱问题的应用前景日趋 广泛而重要。 1 3 装箱问题的分类 装箱问题涉及多学科、多领域的知识，属于复杂的组合最优化问题，在生产 实践中广泛出现并有待解决。文献【3 1 中给出按照装箱物体所属装箱空间、装箱物 体的形状、装箱物体达到情况三种分类方法对于装箱问题进行了分类，本文结合 实际装箱工作又提出了按照装入容器的数量、装箱物体的种类两种分类方法。 1 3 1 按照装箱物体所属装箱空间分类 ( 1 ) 一维装箱问题 经典的一维装箱问题是这样的：设给定一个正数c 和一组数l = a ， a 2 ，a n ，0 a i c ，vi ，问题是要寻求一种分拆方法a 将l 分成一些互不相交 的子集b j ，使得l = b l u b 2 u u b m 。且满足乙口f sc ，v j ，并使m 为满足这一 要求的最小整数。该问题有着广泛的实际背景，如： 1 ) 用户送来一张订货单，l = a l ，a 2 ，a n ) ，a i 表示第i 个货件的长度，货件可 能是钢条、铅管、电缆、原装纸卷等一维线材。假如厂家所供应原材料的标准长 度为c ，同时满足m c ，vi ，如何能以最少量的原材料截出用户所需的货件。 2 ) 有n 个零件需要加工，假定每个零件只需在一台机器上加工一次即可。设 第i 个零件所需的加工时间为a i ，要求所有零件在规定时间c 内全部加工完毕， 试问如何能以最少数的机器和人力在规定时间内完成所需加工任务。 ( 2 ) 二维装箱问题 1 ) 给定n 个矩形l = a l ，a 2 ，a n ( 其中a i - ( x i ，y i ) ；x i ，y i ( 0 ，1 】，i = l ，2 ，n ) ) ， 装入一宽度为1 ，高无限大的矩形a ( 箱子) ，要求将n 个矩形a l , a 2 ，oo - p a n 互不叠 迭地装填入a 中，使布局的总高度最小。对每个小矩形a j ，装填入a 后的姿态 也有直角装填，定向等限制； 天津大学硕士学位论文第一章绪论 2 ) 给定n 个矩形l = a b a 2 ，a n ) 及无限多大小都相等的大矩形( 盒子) ，要 求将a l ，a 2 ，a n 直角定向装填入箱子中，使所占用的箱子个数最少。 对第一类二维装箱问题，若设小矩形的高度都相等，限制装填方式为直角定 向，则问题蜕化为一维装箱问题；对第二类问题若设小矩形之宽与箱子宽相等， 也蜕化为一维情形( 如图1 1 ) 。这类问题广泛应用于板类( 金属板，木板，玻璃、 大理石板等) 切割行业；服装剪裁行业等中的下料问题；建筑业中的房间布局； 工业的模板布局( t e m p l a t el a y o u t ) 、新闻报纸、广告等版面布置，集成电路布 图设计等。 剪裁后的形 状： 布局方案： 1 图1 1 二维装箱问题举例 ( 3 ) 三维装箱问题 与二维装箱问题相似，三维装箱问题( 如图1 2 ) 也有下述两种形式 1 ) 给定n 个矩形体l = a l ，a 2 ，a n ) ，( 其中a i = ( x i ，y i ，z i ) ；x i ，y i ，z i ( 0 ，1 】，i = l ，2 ，n ) 装入一底为l x l ，高为正无穷的柱形箱子a ，要求将n 个矩形体 a l ，a 2 ，a n 互不叠迭地装填入a 中，使布局的总高度z 最小。对每个矩形体a i 装入a 后的姿态也有直角装填，定向等限制。 待装入的盒子： 装入后的图示： 甸甸 图1 2 三维装箱问题举例 4 天津大学硕士学位论文 第一章绪论 2 ) 给定n 个矩形体a l ，a 2 ，a n 及无限多大小都相等的箱子，要求a l ，a 2 ， a n 直角定向装填入箱子中，使所占用的箱子个数最少。 对第一类三维装箱问题，若设矩形体的高度都相等，限制装填方式为直角定 向，则问题蜕化为二维装箱问题；对第二类问题若设矩形体之宽与箱子宽相等， 也蜕化为二维情形。 因此，三维装箱问题可以看作是一维、二维装箱问题的一个泛化。三维装箱 问题有着广泛的应用背景，如运输行业的集装箱货物装载、飞机装舱、码头装货、 列车装箱，机械行业中箱体的布局，航空、航天工业中导弹仓的布局等，涉及建 筑、电子、造船业、纺织业等诸多领域。 1 3 2 按照装箱物体的形状对装箱问题的分类 ( 1 ) 规则物体的装箱 包括二维规则物体的装载和三维规则物体的装载。规则物体是指具有规则外 形的物体，例如圆柱体、矩形体等。在以前及现在的装载研究中，研究较多的仍 然是规则体的装载问题，如：工业应用中的底盘装载问题；三维布局中的集装箱 的货物摆放问题。 货物底盘装载问题广泛存在于工业生产和交通运输中。由于箱子的大小和形 状完全相同，且箱子的边平行于底盘的边，因此该问题也可简化为二维问题。对 于该问题，有的学者使用精确的方法求解。 在运输生产中，常见的集装箱装载要求有两类，一是集装箱数量无限，而待 装的货物有限，要使集装箱利用率最高；二是集装箱数量固定，待装货物数量无 限，远远超过己有集装箱的承载能力，一般是其几倍，要求在有限的集装箱空间 内尽可能地多装货物，使集装箱利用率最高，生产实际中更多地遇到的是第2 类 问题。集装箱布局要考虑货物重量、空间利用率、货物易碎性、以及吊装的可能 性等等，为多目标多约束优化问题。 ( 2 ) 不规则物体的装箱 包括二维不规则物体的装载和三维不规则物体的装载。不规则物体是指具有 任意几何形状的物体。不规则物体的装箱问题在工业生产中大量存在，但同时也 是难度最大的装箱问题。二维不规则物体的装箱如服装样本的下料、皮革下料等。 三维不规则物体的装箱如向具有任意几何形状的容器中放置任意几何外形的装 箱物体，并满足特定的约束条件，达到装箱目标最优。从文献资料中可以看出， 天津大学硕士学位论文 第一章绪论 许多研究者利用人工智能原理求解该复杂问题。该问题的求解算法基本上是启发 式的。 1 3 3 按照装箱物体达到情况对装箱问题的分类 ( 1 ) 在线装箱问题 如果一个装箱算法在装入物品a i 时，只利用a i 前面物品a j ，l 匀的信息， 而不知道后继元素的任何信息，即按照元素到达顺序随到随装，则称该算法为在 线( o n l 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 ) 1 4 1 ，f i r s t f i td e c r e a s i n g h e i g h t ( f f d h ) 【5 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 ) 【4 】，i m p r o v e df i r s t f i t d 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 【4 1 。尽管这些方法都很相似， 但是每个算法都是用不同的方法决定将物品放在哪里。 和二维装箱算法相似的一些算法被应用到三维装箱问题中。在线流行的解决 三维装箱方法之一是s h e l fm e t h o d f 6 1 。该方法也是通过聚组相近尺寸物品来提高 装载利用率的。 ( 2 ) 离线装箱问题 物品装载以前就已得到所有物品信息，之后统一处理所有物品的近似算法称 为离线( o f f i i n e ) 装箱算法。这种情况下的装箱问题称为离线装箱问题。在现代 化的物流配送中，很多都要求按订单送货，因此物品的信息提前都是知道的。该 问题广泛地出现在铁路货车车厢装载、汽车车厢装载、轮船配载、集装箱装载等 情况中。 1 3 4 按照装入容器的数量划分 装入容器的数量为1 个，被装入的盒子总体积略大于或在容器容积范围内， 则称之为单箱装箱问题，势必要求所用容器的空间利用率达到最大；否则为多箱 装箱问题，被装入的盒子总体积多于单个容器容积，其目的就是要求在保证单个 容器空间利用率的基础之上，保证使用容器数量最少。 6 天津大学硕士学位论文 第一章绪论 1 3 5 按照装箱物体的种类划分 ( 1 ) 若装箱货物均属于同一类物体，即拥有相同的物理属性，这种称为同 类( h o m o g e n e o u s ) 【7 1 问题。 ( 2 ) 弱异类( w e a k l yh e t e r o g e n e o u s ) 7 1 问题：装箱货物的种类只有少数几 种，但每类盒子具有一定的数量。即它们拥有各自的物理属性，如长、宽、高等。 ( 3 ) 强异类( s t r o n g l yh e t e r o g e n e o u s ) 7 1 问题：装箱货物的种类有很多。 1 4 集装箱装载问题( c l p ) 集装箱装载问题，又称作c l p ( c o n t a i n e rl o a d i n gp r o b l e m ) ，属于三维装箱 问题，这类问题属于裁剪与装填问题( c u t t i n ga n dp a c k i n gp r o b l e m s ) 的一个分 支。简单地说，是指如何将一些小的长方体盒子按某种方式装入集装箱。集装箱 装载问题是货物运输过程中普遍存在的一个重要环节。它是一类组合优化问题。 如何给出一个合理的布局及装载方案，以在保证装运的稳定性( 防止运输中货物 的移动而导致的货物损坏) 、多目的地运送、负重限制、箱体内的重量分布、装 箱的效率等问题的基础上，使集装箱的空间利用率达到最大，是这类问题的主要 目标。 集装箱装载问题并不是一类单纯的问题。它又可以细划为许多不同的分支， 这些分支问题具有不同的分类标准、不同的目标函数和不同的约束条件。例如， 一种常见的划分依据为：是将给定的大批货物全部装入多个集装箱( 以使所需集 装箱个数最少) ，还是将尽可能多的货物装入一个集装箱；而另外一种分类原则 可以确定为是否考虑约束：如是以集装箱的重量限制为主要约束而使得集装箱的 空间利用率最大呢，还是以货物重量分布是否均匀为主要约束来最大化空间利用 率，还是不考虑约束，仅以使空间利用率最大为目标；而仅就空间利用率而言， 还可以分为：是以某类货物占有集装箱的深度( 即长度) 最小为目标( 便于多目 的地运送) ，还是以货物占有集装箱的体积最大为目标。除此之外，集装箱装载 闯题还会涉及到其它方方面面的考虑。 由于集装箱装载工作到目前为止大多还停留在人工阶段，主要靠装载经验的 积累，所以，对这类问题进行科学的研究并从理论上给出指导显得至关重要。集 装箱装载问题在理论上己被证明为n p 完全问题，求解时具有相当的时间复杂性 和空间复杂性，在一个合理的时间内无法确定最优解。所以，为研究工作带来了 天津大学硕士学位论文第一章绪论 一定的难度。目前，求解这类问题通常采用不确定性算法，也就是通常所说的启 发式方法，这类算法凭借有效的优化策略减小搜索空间的规模，缩小搜索范围， 从而尽可能在有限的时间内找到问题的最优解或近似最优解。 事实上，只要在一定意义上能够给出令用户满意的解，就具有很大的实用价 值。所以，尽管各类启发式方法( 包括智能化搜索的启发式算法) 并不一定能够 给出最优解，但足以满足实际问题的需要。 相对于c l p 这一大类问题的研究而言( 最早源自1 9 4 0 年左右) ，国际上专 门针对集装箱装载问题的研究始于1 9 8 0 年，此后相继出现了一批此类问题的经 典算法。这些算法各有特点和侧重，都在寻求现有算法的改进以及各种的算法的 有机结合，但都不能保证是最优算法，从而为进一步研究此类问题留下了空间。 就国内情况而言，自2 0 0 0 年北方交大的何大勇1 8 1 1 9 】对于集装箱布局问题求解方 法研究【8 j 以来，大概有十多篇相关论文及其相关文摘外，而且他们大多研究在 理想情况下的装箱问题，对于带有约束限制的装箱问题领域的专门研究相对较 少。本文以基于多配送点约束【l0 1 ，针对弱异类单箱装箱问题进行研究，力图找出 前人算法中存在的问题，探讨一种更为有效的算法，并且结合实际问题，给出解 决方案。 1 5 选题的潜在意义 随着物流业的快速发展，人们对货物运输提出了更高的要求，如何快速提供 一个切实有效货物装箱与卸载的方案成为生产行业迫切需要解决的一个重要问 题。本文算法针对在实际工作中单箱装箱问题进行研究，提高集装箱的空间利用 率，考虑多配送点约束，即集装箱装载的货物需要配送至多个客户，这就要求装 箱算法还必须考虑n - 货物重心、货物承重力、是否可以旋转限制，利用本算法 装入货物后，怎样保证在到达某一客户时，不需要搬运其他货物( 盒子) ，而直 接把所需卸载的货物卸下。然后，操作者可以根据算法所得出的装箱结果来开具 装箱单和指导实际的装箱工作。解决这一问题，将直接降低运输成本，为生产部 门、运输部门以及客户带来巨大的效益。 r ， 1 6 本文的内容安排 第一章是绪论，主要介绍课题提出的背景、研究的内容和目的、研究的现状 以及将进行研究的工作内容。 天津大学硕士学位论文第一章绪论 第二章介绍了关于装箱问题常用近似算法。 第三章介绍了本文基于多配送点限制装箱问题的算法研究。 第四章介绍了针对本文研究的问题所开发的集装箱装载程序。 第五章总结了作者所做的工作，并对今后的改进提出了设想。 9 天津大学硕士学位论文第二章装箱问题的常用近似算法 第二章装箱问题的常用近似算法 装箱问题是应用背景较强的离散组合最优化问题。即使是最简单的一维装箱 问题，也属于n p 完全问题。根据g a r e y 和j o h n s o n 关于n p 完全性理论1 2 的研究 表明：在有限合理的时间内，不可能求得大规模n p 完全问题的精确解，问题的 求解只能依赖于各种启发式方法。 启发式算法可以严格定义为：考虑某类问题p ，设其所有实例集合为d p ， 对于每一个实例l d p ，有一个相应的待用解集合s p ( i ) ，若对任意给定的实例l d p ，算法a 总能找到一个待用解集o s p ( i ) ，则称算法a 为问题p 的一个启 发式算法。 韩运实在文献【l i 】中给出启发式装箱求解算法的五种分类：数学规划法、构造 法、数值优化方法、改进法、现代化方法( 遗传算法、模拟退火算法等) 。乐千 桤在文献l l2 】中给出启发式装箱求解算法的七种分类：构造法、改进法、数学规划 法、分解法、分割法、解空间限制法、松弛法。在诸多研究装箱问题的文献中， 大家大多都在尝试使用各类算法的有机结合，寻求更好的装箱速度和装箱效果。 本文就优化机制与行为而分，目前装箱问题中常用的启发式算法主要分为：经典 算法、构造型算法、计算智能算法和混合型算测1 3 】【1 4 】【1 5 】【1 6 1 等。其中计算智能算 法包括：遗传算法【17 】【1 8 】【1 9 1 1 2 0 1 【2 1 1 1 2 2 1 模拟退火算法f 2 3 】【2 4 】【2 5 】【2 6 】、禁忌搜索阿等方法。 2 1 优化方法的分类及特点 装箱问题可以用优化方法来求解，张丽岩在文酬1 1 】中给出传统的优化方法主 要有三种：枚举法、启发式算法和搜索算法。 1 枚举法：枚举出可行解集合内的所有可行解，以求出精确最优解。对于 连续函数，该方法要求先对其进行离散化处理，这样就可能因离散处理而永远达 不到最优解。此外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至 在目前先进计算机工具上无法求解。 2 启发式算法：寻求一种能产生可行解的启发式规则，以找到一个最优解 或近似最优解。该方法的求解效率比较高，但对每一个需求解的问题必须找出其 特有的启发式规则，这个启发式规则一般无通用性，不适合用于其他问题。 目前装箱问题中常用的启发式算法主要有：经典算法、构造型算法、计算智 能算法和混合型算法等。其中计算智能算法包括：遗传算法、模拟退火算法、禁 1 0 天津大学硕士学位论文第二章装箱问题的常用近似算法 忌搜索等方法。 3 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进行 搜索操作，以找到问题的最优解或者近似最优解。该方法虽然保证不了一定能够 得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和效率 上达到一种较好的平衡。 集装箱装箱问题属于组合优化n p h a r d 问题，其可行解的数量是非常庞大 的，通过枚举法进行求解是不现实的，所以要想寻求较优解只能依靠启发式算法 和搜索算法，使算法能够尽量具有全局搜索能力，并避免陷入局部最优点。 2 2 适应启发式算法的概述 装箱问题是经典的n p 完全问题，这意味着该问题不存在在多项式时间内求 得精确解的算法( 如果p n p ) 。因此对装箱问题算法的研究指的是对其近似算 法的研究。所谓近似算法即该算法可以求得与精确解接近的结果，但不一定得到 精确解。在有限合理的时间内，不可能求得大规模；n p 完全问题的精确解，问题 的求解只能依赖于各种启发式方法( h e u r i s t i ca l g o r i t h m s ) 2 7 1 2 8 】【2 9 】3 0 】。但大多数 启发式算法以贪心方法为特点，采用了某些简单规则，比如次优适应、优先适应 或最佳适应。g a r e y 和j o h n s o n ：还指出，简单启发式算法的结果可以不差于( 但也 不好于) 最优解乘以一个相当小的系数。 适应算法( a n yf i ta l g o r i t h m ) 【4 】可以定义为：在处理当前物品时，如果有 己经打开的箱子中能够放下这个物品，则不打开新的箱子，符合该条件的算法被 称为适应算法。次优适应算法、优先适应算法、最佳适应算法、最坏适应算法和 几乎最坏适应算法是几个著名的适应算法。适应算法的最坏情况性能比被证明一 定处于i 1 7 ，2 】范围内，即在最坏情况性能上不可能优于首次适应算法。下面本 文将启发式算法与适应算法相结合，分别加以介绍。 ( 1 ) 下次优适应启发式方法( n e x t f i th e u r i s t i c ，n f ) ( 4 】i 熨。装箱问题最简 单的启发式方法是次优算法，是最早提出、最简单的一个在线算法。下次优适应 算法同一时间内只有一个箱子是打开的，第1 个物品放入第1 个箱子，然后是根据 下标上升的顺序放入第2 ，n 个物品。如果当前箱子的容量允许，则每个物品 放入当前箱子，否则放入一个新的箱子。于是新箱子成为当前箱子。该算法的复 杂性是o ( n ) ，最坏情况性能比为2 ，平均情况性能比为4 3 。其串行算法通用程 序描述如下： 输入：物品序列l = ； 输出：使用的箱子数目m ，各装入物品的箱子p = 天津大学硕士学位论文第二章装箱问题的常用近似算法 b e g i n 初始化当前打开的箱子b ，令b 已满，g p s ( b ) = l ； 使用箱子记数m = o ； f o ri = lt o1 1d o i fs ( a i ) + s ( b ) lt h e n 把a i 放入b 中，s ( b ) = s ( b ) + s ( a i ) ； e l s e m = m + l ； 打开新箱子b m ，b = b m ， s ( b ) = s ( ai ) ； e n di f e n df o r e n d 。 ( 2 ) 优先适应启发式方法( f i r s t f i th e u r i s t i c ，f f ) 【4 】o 优先配合算法也根 据下标上升的顺序考虑物品。但将每个物品放入其能够放入的最小下标的己初始 化的箱子。如果当前物品无法放入任何己初始化的箱子，则放入一个新箱子。即 把w i 放入第一个箱子中，一般地设w i 是当前要装的物品，b 1 ，b 2 ，b i 是当前 己使用过的箱子，在这些箱子中找一个剩余长度不小于w i 且下标最小的箱子，将 w i 放入，如果不存在这样的箱子，则另开一个新箱子b i + l ，将w i 放入b j + 1 中。该 算法的复杂性是o ( n l o g n ) 。 ( 3 ) 最佳适应启发式方法( b e s t f i th e u r i s t i c ，b f ) 【4 】o 最佳配合算法从f f 算法改进而来。它将当前物品放入具有最小剩余容量的可行箱子中。该算法摒弃 了有利于最小下标箱子的思想。f f 和b f 的时间复杂性都是o ( n i o g n ) 。 ( 4 ) 调和装箱算法。带参数k 的调和算法，在1 9 8 5 年由c c l e e 和d t l e e 提出。其基本思想是将原始装箱问题划分为k 个具有相同类型物品的子装箱问 题，然后对每个子问题调用次优适应的策略。其中的参数k 为常数，是指把区间 ( 0 ，l 】划分为k 个子区间i k = ( 1 ( k + 1 ) ，1 k ( 1 k k ) 和i k = ( 0 ，l m ，大小处于区间i k ( 1 k k ) 的物品为第k 类物品，同时箱子也相应地被划分为k 类，规定第k 类箱 子只能装入第k 类的物品。由于参数k 的引入，次优适等算法中存在的前面箱子 的剩余空间不可再用的矛盾得到了一定程度的缓解。k 调和算法对于物品大小参 差不齐的物品序列能很好的减小空间资源的浪费，从而很好的提高了算法的性， 能。其算法的时间复杂度为0 ( n ) ，最坏情祝性能比为1 6 9 1 0 3 ，较之次优适应算 法其最坏情况比有了很大的提高。由于k 的引入其平均情况性能比与k 相关，在 k 无穷大且在( 0 ，1 ) 均匀分布的情况下，其平均情况性能比为1 2 8 9 8 7 。 ( 5 ) 其他启发式方法。如果物品按照重量降序排列，( w l w 2 w n ) ， 1 2 天津大学硕士学位论文 第二章装箱问题的常用近似算法 然后采用n f ，f f 或b f 得到的算法相应称作下次优适应降序( n e x t - f i td e c r e a s i n g ， n f d ) ，优先适应降序( f i r s t f i td e c r e a s i n g ，f f d ) 和最佳适应降序( b e s t f i t d e c r e a s i n g ，b f d ) 。这些算法的时间复杂性都是o ( n l o g n ) 。这些算法通常用于测 试新提出的用于装箱问题算法的有效性。通常他们都嵌入遗传算法来增强遗传搜 索能力，从而为装箱问题寻找到更接近最优解的答案。 表2 1 给出了前人对这些近似算法的重要性能指标的比较，装箱问题近似算 法的三个评价标准是最坏情况性能比，平均情况性能比( 如非特别指出，一般是 指当输入物品满足( 0 ，1 ) 均匀分布情况下的平均性能) ，时间、空间复杂度。c o f f m a n 等从这三个主要标准出发对众多目前已经提出的算法进行了很好的评价，下面列 出其中一部分。 表2 1 一些著名的经典装箱问题的近似算法】 近似算法离在线时间复杂度最坏情况性能比平均性能比 次优适应算法在线 o ( n ) 24 3 优先适应算法在线 o ( n l o g n ) 1 7l 最佳适应算法在线 o ( n l o g n ) 1 71 调和算法( h k ) 在线 o ( n ) 1 6 9 1 0 3 与k 相关 改进的调和算法在线 o ( n ) 1 6 3 5 9 6 与k 相关 n e x t 在线 o ( n ) 1 7 + 0 3 ( k 1 ) 与k 相关 a f b x在线 o ( n )1 7 + 0 3 ( k - 1 ) 与k 相关 k b o u n d e d 在线 o ( n ) 1 7 与k 相关 a b f x在线 o ( n ) 1 7 + 0 3 k 与k 相关 降序首次适应 离线 o ( n l o g n ) l l 91 降序最佳适应离线 o ( n l o g n ) 1 1 91 比较n f ，f f ，f f d 算法，它们的近似化程度一个比一个好，但这并不足说 n f ， f f 就失去了存在价值。f f ， f f d 算法都要求将所有物品全部装好后，所 有箱子才能一起运走，而n f 算法无此限制；f f d 算法还要求所有物品全部到达后 才开始装箱，而n f ，f f 算法在给某一物品装箱时，可以不知道下一个物品的规 格如何，或者可以说物品可以一个个达到，在未到达前不必预先知道它的规格， 即在线( o n l i n e ) f 6 j 装箱问题。如果可以事先知道物品的所有信息，、则称为离线 ( o f f - l i n e ) l o j 装箱问题。 天津大学硕士学位论文第二章装箱问题的常用近似算法 2 3 装箱问题的其它解法 考虑到实际的装箱现场，有的货物是通过物流传送带直接传递过来的，那样 的话，装箱工人必须把货物从上面取下直接装入集装箱；有的货物是已经摆放到 货场，装箱工人需要事先知道货物摆放的位置，依照装箱顺序取得货物，然后再 将其装入集装箱。这样的话，装箱问题的解法就分为在线装箱问题求解和离线装 箱问题的求解。 2 3 1 在线装箱问题的解法 对于在线装箱问题，很多一维、二维在线装箱问题都采用层的思想：物品的 尺寸不能提前知道。层由沿箱子宽度排列的一列物品组成。也就是说箱子是由层 中最大高度的物品来分割的。典型方法包括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 ) ， f i r s t f i td e c r e a s i n gh e i g h t ( f f d h ) ，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 ) 和h a r m o n i ca l g o r i t h m s 。尽管这些方法都很相似， 但是每个算法都是用不同的方法决定将物品放在哪里。 和二维装箱算法相似的一些算法被应用到三维装箱问题中。在线流行的解决 二维装箱方法之一是s h e l f m e t h o d t 引。该方法也是通过聚组相近尺寸物品来提高装 载利用率的。 2 3 2 离线装箱问题的解法 而分支定界方法、遗传算法和模拟退火方法都是用来解决离线的装箱问题的 常用算法。分支定界方法利用递归方法寻找问题的可行解，采取了必要的限制条 件，设法排除可行域中大量非最优解区域，从而能够有效求解一些规模较大的问 题。 遗传算法j 是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开始的， 而一个种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组成。每个个体实际上是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为 遗传物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 是某种基因 组合，它决定了个体的性状的外部表现。因此，在一开始需要实现从表现型到基 因型的映射即编码工作。由于仿照基因编码的工作很复杂，需要进行简化，如二 进制编码。初始