（系统工程专业论文）面向同城配送的车厢装载优化.pdf

山东大学硕士学位论文 摘要 货物装载是物流配送的重要环节，其方案的优劣对提高整个物流系 统的效率和降低运输成本都有着重大的影响。目前绝大部分研究都集 中在集装箱等规则容器的空间布局上，很少有人对m p v 、厢式车等载 货厢体为非规则长方体的布局问题进行深入的研究。对于同城配送来 讲，货物的装载不需要太大空问，又由于城市交通的特点，大型的载 货车不适合用于同城配送由于同城配送的特点，城市交通道路状况， 一些轻便灵活而且拥有大的载物空问能力的车型成为同城配送的首 选目前，同城配送一般选用依维柯、金杯车等车型，这类车在侧面 有一定的倾斜弧度，如果考虑这些因素，货物在车厢的装载仍然具有 提升的空间。 本课题对同城配送中使用的客货两用车车车厢进行优化研究，针对 装箱问题中的弱差异问题提出个合理的布局及装载方案，以提高客 货两用车车厢的空间利用率。本文在分析了集装箱问题的优化方法基 础上结合客货两用车的特点，使用构造式启发算法提出了按完全层装 填车厢的方法，结合剩余空间搜索策略，为异型车厢装载提出一种布 局方法，在本课题装入算法的研究中，提高车厢空间的利用率是主要 的目标空间装填的废弃空间的利用向来是集装箱装载问题的难点， 通过空隙融合策略，在装箱时充分利用了剩余空间填充过程中浪费掉 的许多空隙，进一步提高了算法的有效性。 关键词：集装箱装载启发式算法弱差异同城配送 山东大学硕士学位论文 a b s t r a c t i ti st h ei m p o r t a n te i e m e n tf o rl o g i s t i c sd e i i v e r yt h a tt h e g o o d sa r el o a d e d i nc o n t a i n e r s ，t h eq u a l i t yo fi t ss c h e m eh a s g r e a ti n f l u e n c et oi m p r o v et h ee f f i c i e n c yo ft h ew h o l el o g i s t i c s s y s t e ma n dr e d u c et h et r a n s p o r tc o s t a tp r e s e n t 。m o s tr e s e a r c h e s c o n c e n t r a t eo nt h ep a c k i n go fr e g u l a rc o n t a i n e r s ，s u c ha st h e c o n t a i n e r1 0 a d i n g ，t h ep a l l e tp a c k i n g ，e t c t o1 0 9 is t i c s s p e c i a l p u r p o s ev e h i c l e u s e df o rl o c a lt o w nd e l i v e r y ，s u c ha sm p v ， v a n ，e t c w h i c hd o n th a v et h er e g u l a rf o r ma n ds t r u c t u r e ，f e w p e o p l ec a r r i e so nd e e pr e s e a r c hf o rt h i sq u e s t i o no fo v e r a l i a r r a n g e m e n ts p a c eo ft h en o n r e g u l a rc u b o i d s t h ev e h i c l et o p r o v i d ea n dd e l i v e rt h eg o o d si nt h es a m ec i t yd o e sn o tn e e dt o o b i g1 0 a d i n gs p a c e ，t h es p a c eo ft h ec o n t a i h e rc a r r i a g eist o o 1 a r g e 。d o e sn o ta c c o r dw i t ht h ed e l i v e r yu s e di nt h es a m ec i t y t h el o c a lt o w n d e l i v e r yg e n e r a l l y s e l e c tt h es p e c i a l p u r p o s e v e h i c l e s ，s u c ha si v e c o ，g o l d e nc u pc a r ，e t c t h i sk i n do fc a r s h a sc e r t a i ns l o p er a d i a n so nt h es i d e ，i fc o n s i d e r i n gt h e s e f a c t o r s 。，t h e1 0 a d i n gt h es p a c et h a ts t i l lh a sp r o m o t i o ni nt h e c a r r i a g es p a c eu s i n go fg o o d sl o a d i n g t h i ss u b j e c to p t i m i z e st h eu r b a n1 0 9 i s t i c ss p e c i a l p u r p o s e v e h i c l et h a ti sp r o v i d e da n dd e i i v e r e di nt h es a m ec i t y ，a n dp u t f o r w a r dar a t i o n a lp a c k i n ga n dl o a dt h es c h e m et ot h ec a r g oo f t h ew e a k l yh e t e r o g e n e o u st y p ei nt h e1 0 a d i n gp r o b l e m ，i m p r o v e t h es p a c eu t i i i z a t i o nr a t i oo ft h es p e c i a l p u r p o s ec a r r i a g eo f t h eu r b a nl o g i s t i c sa n dc o n t a i h e rl o a d i n ge f f i c i e n c y i nt h e r e s e a r c ho ft h ep a c k i n ga l g o r i t h mi nt h i ss u b j e c t ，t h em a i ng o a l i st h eu t i i i z a t i o nr a t i oo fi m p r o v i n gt h ec a r r i a g es p a c e t h i s s u b j e c t c o m b i n e s t h ec h a r a c t e r i s t i co ft h e s p e c i a l p u r p o s e v e h i c l eo fu r b a nl o g i s t i a so nt h eb a s i so fa n a l y z i n gt h eq u e s t i o n o p t i m i z a t i o n m e t h o do ft h ec o n t a i n e rl o a d i n gp r o b l e m ，a n dp u t m 山东大学硕士学位论文 f o r w a r dam e t h o dt o1 0 a dt h ev e h i c l ea c c o r d i n gt ot h ec o m p l e t e l a y e rw h i c hi sl o a d e dm a i n l yw i t has o r to fc a r g o c o m b i n i n gt h e d i s c a r d e ds p a c es e a r c h i n gt a c t i c s ，ig i v eak i n do fp a c k i n g m e t h o df o rt h el o a d i n go ft h eh e t e r o t y p i c c a r r i a g e t h ei s s u e t ou t i l i z ed i s c a r d e d s p a c ei st h ed i f f i c u l tp o i n ti nt h e c o n t a i n e rl o a d i n gp r o b l e m 。t h r o u g ht h es p a c em e r g i n gt a c t i c s ， t h ed is c a r d e ds p a c ei o s ti nt h ec o u r s eo fl o a d i n gc a nb e f u l l y u t i l i z e d ；i tc o u l df u r t h e ri m p r o v et h ev a l i d i t yo ft h ea l g o r i t h m k e y w 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 ；h e u r i s t i ca l g o r i t h m ； w e a k l yh e t e r o g e n e o u s ；l o c a lt o w bd e l i v e r y 1 v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写过的科 一 研成果。对本文的研究作出重要贡献的个人和集体，均已在文 中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：基猛盎 日期：兰! 堕：丝星 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文 和汇编本学位论文 ( 保密论文在解密后应遵守此规定) 论文作者签名：二睥导师签名： 山东大学硕士学位论文 1 1 课题背景 第1 章绪论 运输是物流活动的一个重要内容，在整个物流成本中占有很大 的比例，是影响物流成本的一项重要因素。物流成本占g d p 的比 重已经成为衡量一个国家物流业发展水平的重要指标，普遍认为物 流业越发达效率越高，物流成本越低，物流总成本在g d p 中的比 重就越小【l 】。在美国，运输费用占g d p 的比重大约为6 ，大于库 存费用的3 7 的比重；商品从产品到消费者手中所花费的物流费 用中，运输费占的比例约为4 5 【2 1 。中国物流与采购联合会于2 0 0 1 年对我国的物流成本进行了调查与研究，我国的物流费用占g d p 的比重约为1 6 7 ，运输成本约占物流总成本的6 0 【l 】。物流费用 以年增长率为7 计算，物流成本每年降低o 5 个百分点，则我国 每年至少可以节省5 5 0 亿元的物流费用由此可见应当努力采取各 种措施降低运输费用，从而降低物流活动的总成本。 随着城市化进程的加快与电子商务的发展，快速兴起了一些中 小型物流企业，如小型速递公司，送水公司，送奶公司等。这类企 业主要为百姓日常生活用品为主的配送服务，也可为连锁超市，零 售商店，电子商务网站提供配送服务。由于企业投资不大、门槛低， 但市场需求增长快，因此大量的小型企业加入这类物流服务中来。 这类企业通常以局部市场为主，在特定的区域提供特定的物流服 务，决定了企业服务特点以同城配送为主。同城配送具有服务区域 小，但配送时间短、效率高、费用低等特点，非常适合于电子商务 模式【3 】。同城配送的特色是。代理”配送，是以烟草，电器、汽配、 医药、出版物等为内容的同城配送每次的交易批量比较少，服务 客户比较广泛，同城配送是传统物流和现代物流的显著区别之一。 随着经济的发展，中国城市物流的需求空前增长。但是，目前 山东大学硕士学位论文 的城市物流与现代化的城市管理产生了尖锐的冲突：一方面，居民 的活动半径与城市一起不断扩大，城市物流量、物流用车需求日益 增长；另一方面，出于城市形象和城市管理的考虑，各大中城市主 城区禁行载货车的力度也在加大。作为城市现代化物流配送供应链 末端的一个环节，人们对于物流配送效率的要求也越来越高由于 城市交通、道路状况，一些轻便灵活而且拥有大的载物空间能力的 车型，如轻型客货两用车或s u v ，担当起了现代物流的重任，成为 城市物流用车的第一选择。 目前，主要通过提高运输效率和降低运输成本来降低运输费 用，一些与运输相关的问题研究，如配送中心的选址、运输车辆路 线规划、物流器具及运载工具的装载优化等，已经为研究的热点 物流成本的降低是增强企业竞争力的关键，车厢装载优化具有很高 的研究侨值。 1 2 课题意义 随着我国物流业的蓬勃兴起，“合理化配送”已成为当今物流 发展的一种内在要求，正日益受到人们的广泛关注：针对配送的运 筹方法研究已成为业界与学术界的热点充分发挥装载工具的运载 能力，可以降低货物运输的单位成本，节约可观的物流费用如何 最大限度地发挥车厢容积和承载能力从而降低配送成本的问题是 一种集装箱装载问题( c o n t a i n e rl o a d i n gp r o b l e m ) ，本文的车厢装载 即属于这类问题。 本人在对同城物流配送进行调查过程中发现，同城配送有着不 同于集装箱装载的特点：所使用的车型一般为金杯面包车、依维柯 等客货两用车作为城市物流用车，车厢容积比较小，并且车厢不是 规则的长方体，装箱操作不容易充分利用车厢的有效空间；配送的 路线比较短，客户量大而且服务对象比较单一，货物的种类少；装 箱作业基本上依赖人工经验，调度员凭借经验估计出装箱的数量和 所需车厢的数量，装箱工人作业也依靠经验而且带有较大的随机 2 山东大学硕士学位论文 性。配送的路线都是根据街区固定的，不管所需要配送的货物为多 少都需要是用一辆车进行配送，严重浪费了车厢空间，不具有灵活 性同城配送的车厢装载有别于集装箱装载，但是车厢的配载仍然 可以借鉴集装箱问题的优化方法进行优化，本课题即对同城配送中 所使用的城市物流用车车厢进行优化，为解决同类的问题提出一个 合理的布局及装载方案，从而提高城市物流用车厢的空间利用率。 1 3 集装箱装载 在实际运输中，为了产品的安全和便于运输，很多产品在生产 出来后就被装入到各种尺寸的矩形木箱或纸箱中，然后这些箱子再 被装入集装箱进行运送。集装箱装载是一种很重要的集装化方式， 它有利于货物的装卸和运输管理所谓的集装箱装载问题 ( c o n t a i n e rl o a d i n gp r o b l e m ，简称c l p ) ，是指将一些长方体货物按 一定的方式装入集装箱，从而最大限度的提高集装箱的空问利用能 力集装箱问题是矩形货物在集装箱中的摆放安排问题，以最大化 集装箱空间的使用率为目标。一般情况下，称这类问题称为三维装 箱问题。 集装箱装载问题( 以下简称c l p ) 是一个非常有价值的研究课 题，在学术上属于相当复杂的几何组合优化问题( g e o m e t r i c c o m b i n a t o r i a lo p t i m i z a t i o n ) 。集装箱装载闯题是布局问题领域的三 维问题，在理论上属于n p 完全问题。在实际问题上直接利用数学 中的优化方法很难解决，因为数学优化方法一般是对量的优化，通 过方程求解得到目标解。但是集装箱装载问题不仅是量的问题，它 还需要对物体以及剩余空间进行形状描述，使得该闯题无法用纯数 学方法进行描述，无法通过数学公式进行求解，因此该类问题只能 通过一些近似的方法来解决【4 】。 集装箱装载问题广泛地出现在铁路货车车厢装载，汽车车厢 装载，轮船配载，集装箱装载中。集装箱装载是配送过程的关键环 节，托盘装载以及卡车等运输车辆的装载与集装箱装载具有相似 性。如何给出一个合理的布局及装载方案，在保证装运的稳定性、 山东大学硕士学位论文 多目的地运送、负重限制、箱体内的重量分布、装箱效率等问题的 基础上，使集装箱的空间利用率最大，是这类问题的主要目标 分别从集装箱和货物两方面考虑，根据现有文献显示，集装箱 配载大致分为四种配装情形，相同体积货物与不同体积货物的配 载，单个集装箱和多个集装箱的配载。d y c k h o f f 在文献f 5 】中提出将 集装箱装载分为单个集装箱与多个集装箱的配装( d y c k h o f f , 1 9 9 0 ) 对于体积不同货物的配装情形，b o r t f e l d t 又将之细分为弱差异情形 ( w e a k l yh e t e r o g e n e o u s ) 与强差异情形( s t r o n gh e t e r o g e n e o u s ) ， 弱差异即只有少数几种体积不同货物但每种货物数量较多情况，反 之多种体积不同的货物但每种数量较少则称为强差异情形【6 l ( g c h r i n g ，1 9 9 7 ) 。 尽管同城配送企业使用多辆车进行配送，但是由于配送路线 的限制，仍然属于单个集装箱装载情况。又由于同城配送的针对性 比较强，配送的货物种类比较少数量相对较多，因此同城配送可以 视为单集装箱弱差异情形。 1 4 国内外相关研究 目前对车厢装载几种在规则车厢的研究中，下面仅就c l p 问 题的研究进行介绍c l p 问题的研究方法有线性规划、整数规划、 动态规划等传统优化方法，构造型启发式算法及严谨启发式算法 ( 包括模拟退火算法、禁忌算法，基因算法) 等等。对于传统的优 化方法由于问题规模的增大，解空间呈指数倍数增长，这就会导致 常说的? 组合爆炸”问题，使问题难以求解。为了避免搜索空间时 出现“组合爆炸”现象，必须恰当地利用与问题有关的某些特殊信 息来控制搜索过程，因此结合优化的搜索策略降低搜索空间即启发 式搜索，才是c l p 闯题研究的方向。目前，国内外的研究成果主 要也集中在启发式算法方面启发式算法分为两大类构造型启发式 算法与严谨型启发式算法，下面就这两方面成果分别论述。 1 4 1 国外的研究概况 4 山东大学硕士学位论文 一、构造型启发式算法 这二类启发式算法凭借实践经验建立直接的搜索策略和搜索 规则，并以此规则在搜囊空间中求解。由于采用经验机制，没有严 格的理论支撑，所以这类算法无法保证找到最优解【7 l ；另一方面， 由于启发式规则是根据实际问题建立的，具有较强的针对性和一定 的合理性，虽然无法保证得到最优解，但是通常可以得出令人满意 的可行解。由于构造型启发算法描述直观，易于实现，对于具体装 载问题的优化有很高的实用价值。所以大量的研究集中在这类算法 中，下面就几种有影响的算法分别进行介绍 ( 1 ) g e o r g e & r o bin s o n 算法 g e o r g e & r o b i n s o n ( 以下简称g & r ) 算法是影响最广的一种算法， 他们首先采用构造型启发式算法来解决c l p 问题i s ) 他们把研究的 问题集中在多种物体的装填上，这些物体可以以任意方向放置 g & r 算法有两个关键的地方：一是层的划分，二是确定物体的装 入优先级在c l p 问题研究中为了便于装填，他们首次提出层的 概念，后来很多算法都使用了层的概念，层这一概念的提出对于后 来的研究产生了很大影响。 该算法的基本思想如下： g & r 方法分阶段填充，将物体在深度方向按层布局，尽量使 每一层的外表面平整。装填的每一类物体都被赋予一个状态：打开 状态( o p e n ) 或非打开状态( u n o p e n ) 。如果某类物体中已经有物体装 入箱体内，则标识该类物体为o p e n 状态，反之标识为u n o p e n 状态 处于打开状态的物体优先装入，通常选取处于打开状态且没有装入 箱体的物体数量最多的那类物体首先装填新层。 对于处于非打开状态的物体设置优先级，首先对物体的长宽高 三尺寸中的最小尺寸进行排序，最小尺寸越大，物体级别越高因 为最小尺寸越大的物体到最后越难装入：对于处于同一级别的物 体，按物体的数量进行分级，数量多者级别高这样儆是考虑在同 一层中尽量装填同一类型的物体，以提高层的空间利用率；如果按 山东大学硕士学位论文 前面两种规则进行排序后，仍然有物体优先级相同，则按每一类物 体的长宽高三尺寸中的最大尺寸进行排序，尺寸越大，级别越高 优先级确定后，按照构建层的方式装填每一层中的第一个物 体的选取至关重要，由于没有物体装入该层，它的装入将决定这一 层的厚度。优先级确定后选取优先级最大的物体作为装入的第一个 物体。以后各层，装入的第一个物体在处于o p e n 状态且数量最多 的一类物体中选取，如果没有处于o p e n 状态的物体，则按照物体 优先级确定。但是g & r 对使用第一个物体的那一个尺寸作为层的 厚度没有详细的提及 g & r 方法还对装入物体后产生的剩余空间进行了叙述一旦 物体装入箱子，就会在物体周围产生剩余窆间，即上方，右方和前 方。装入下一个物体时，按照先上，再向右最后向前的遍历方式进 行装填，下一个物体的装入以前一个物体为基准。一层装填完毕后， 再沿集装箱长度方向装填新层，直到物体全部装入箱内或装满为 止。 可以说以后涉及到分层的算法研究都是在g & r 基础上进行研 究探讨的该方法适用于弱差异情形。缺点就是每个物体都要逐一 分析处理，会牺牲大量的时间，算法效率较低；孤立的按照每个物 体考虑，降低了装箱的效率。 ( 2 ) b is o h o f f & m arr i o t t 算法p 3 b & m 算法仍然是建立在层的基础上进行讨论的。该算法的构想 是，先按照某种标准确定物体的优先级，然后取出级别高的物体， 分别尝试用它的长、宽、高充当层的宽度，一旦层的厚度确定，由 于同层的物体尺寸相同，问题就转化为二维装填问题。该算法的特 点是要求每一层尽可能由同一类物体组成 如果没有足够的尺寸相同的物体能够把一层装满，那么就应该 暂时放弃对这种物体的处理，转而处理下一个优先级类型的物体 到最后可能所有的物体刚好装入集装箱内，但是更多的情况是剩下 6 山东大学硕士学位论文 的每类物体都不能装满一个完全层对于后一种情况采用g & r 算 法可将剩下的装箱工作完成。该算法实际上是对g & r 算法的改进 本算法运用二维装填技术来解决三维布局问题，给我们对c l p 问 题研究进行简化给了很大的启示 ( 3 ) g e o r g e 算法 本算法是建立在同一尺寸的物体基础上的装箱问题，属于装箱 问题的一个特例【1 0 】。本算法中的物体可以任意方向放置。这一算 法完全采用了b i s c h o f f & m a r r i o t t 算法中建立层的算法。算法中唯一 改进的地方是提出了一种“集装箱旋转”的方法，即允许集装箱在 坐标系中绕y 轴或z 轴旋转，从而使得原来沿集装箱深度方向码 放的工作转变为沿集装箱宽度方向进行码放，从而在不改变装箱策 略的情况下改变了布局结果，在更大的空间范围内找到满意解。该 方法简化了对物体布局情况的搜索，使得物体的装填更容易使用计 算机实现 ( t ) l o h & n e e 算法 l o h & n e e 研究的是弱差异情形，他们采用了水平方向进行构建 层，为使层表面趋于平坦按照物体高度设置优先级，并定义移动边 界分隔集装箱为已装填和未装填空间值得强调的是，该算法给出 1 5 组数据被很多算法当作标准测试数据使用【1 1 1 。 ( 5 ) n g o i 算法 n g o i 等人提出一种新算法，该算法舍弃了层的构建方式，用一 种特殊矩阵空间描述方法表示空闲空间和已装填空间【1 2 儿36 1 ，使得 算法的描述直自而简单例如，一个长、宽、高为( 1 0 0 ，8 0 ，6 0 ) 的箱中左下角放入了一个尺寸为( 4 0 ，2 8 ，1 2 ) 的物体，则箱的边 x 、y 、z 分别被分割为两段，空间表示法将这一布局描述成如下两 个矩阵： 山东大学硕士学位论文 y 矧 图i in g o i 的空间表示法及对应的空闲状态 两个矩阵分别表示箱体以物体高1 2 为分割点的上下两个空间状 态。矩阵中的第一个元素表示竖直方向的两个分割点。第一行的第 二、三个元素表示x 方向的两个分割点，第一列的第二、三个元素 表示z 方向的两个分割点。2 表示装入物体的标识号，o 表示剩余空 间这种表示法简单、直观，且非常准确的反映了物理空间的占用 状态。 该算法流程简单，利于计算机编程实现，但是该算法缺点就是 耗费内存较多，增加了时间复杂度，而且使用该方法产生的盒柱之 间有空隙【挖】，剩余空间不能得到充分利用。 b i s c h o f f & r a t c l i f f 采用了n g o i 等人的空间描述方法，算法独到 之处在于尽量使相同的物体组成盒柱，并且对于物体的优先级制定 了四个标准即空间利用率，深度方向尺寸，物体体积，剩余空间y 坐标最小【1 3 1 。他们的算法中，物体可以任意放置算法既适用于 弱差异类问题，又适用于强差异类问题 二、严谨型启发式算法 严谨启发式方法也称为智能优化算法，是近年来解决复杂优化 问题备受关注的一类方法该类方法以试图寻找全局最优解为目 标，这种算法一般具有严密的理论依据，丽不是单纯凭借专家经验 用于装箱问题的这类方法有模拟退火算法( s i m u l a t e d a n n e a l i n g ，简 称s a ) 、基因算法( g e n e t i ca l g o r i t h m s ，简称g a ) 、禁忌算法( t a b u s e a r c h ，简称t s ) 。 遗传算法是建立在自然选择和群体遗传机理基虢i i 上的自适应 、， o o 加o o 山东大学硕士学位论文 概率性搜索算法遗传算法把优化问题的解的搜索空间转化为遗传 空间，将每个可能的问题解表示为“染色体”，从而得到一个由染 色体组成的“解集”。这个群体被限制在问题特定环境里，根据预 定的目标函数对每个个体( 即候选解) ，利用遗传算子对这些个体 按“适者”有更多的机会生存的原则进行交叉组合产生后代。由于 继承了父代的一些优良性状，后代明显优于上一代。这样，“染色 体”组成的“群体”将逐步朝着更优解的方向进化。主要流程图如 图一所示： 圈1 - 2 遗传算法流程图 模拟退火算法( s a ) 又称为模拟冷却法、随机松弛法和概率爬山 法等。其思想是由n m e t r o p o l i s 1 4 】等提出的。该算法是根据目标函 数进行评价的，判定是否接受某一状态为当前状态。s a 算法将解 决布局问题的约束转化到目标函数中去，从而将有约束问题转化为 无约束问题，即将目标函数用于衡量约束违反状况并作为模拟退火 9 山东大学硕士学位论文 l i i s ! e ! e e _ 目! e ! g ! ! e 自! ! ! e 目! 目! 目j 目e ! | 自! 自! g ! ! ! | 目_ g j e ! _ 算法的评价函数 模拟退火算法的特点： a ) 能够以一定的概率接受劣解，使得算法过程具有跳跃性，可 能跳出局部最优的“陷阱”化解了算法对初值得依赖性； b ) 新状态产生函数、新状态接受函数、退温函数、抽样稳定准 则和结束准则及初始温度是直接影响算法优化性能的主要 因素； c 1 算法解具有质量高、初值鲁棒性强、通用易实现的优点； d ) 较高的初温、较慢的降温速度、较低的终止温度以及各温度 下足够多次的抽样，因此优化过程较长 该算法初温的选择很重要，初始温度应选的足够的高，使得算 法在布局初始阶段，每一布局方案基本上都可以被接受采纳。初始 温度选的很高的目的是为了避免算法落入局部最优的陷阱中，导致 无法取得全局最优解；如果初始温度太高，则算法的计算量增加许 多从而使计算时间无法忍受。 涉及严谨式启发式算法的在三维装箱方面的研究，没有形成系 统的理论，目前在这方面的研究都是采用构造式启发式算法与严谨 启发式算法相结合的办法。 1 4 2 国内的研究概况 目前国内对集装箱装载问题及其相关问题的研究比较少。就传 统算法而言，其中青岛大学的富佩珊( 1 9 9 7 ) 针对单一产品且产品无 摆放限制的情况提出了一种递归方法【钉，对单一产品摆放取得了1 不错的效果；天津商学院的杨传民教授对于立体包装件的混装使用 离散优化的方法进行研究【1 6 】，该方法只适用于小规模问题 对于启发式算法下面是几个有代表性的算法。 一类是采用构造型启发式算法，比较有代表性的是何大勇、查 建中【 1 提出一种利用三叉树结构表达三维矩形物体布局状态空间 的方法。该算法通过布局空间依次分割为三个方向的待布局空间， l o 山东大学硕士学位论文 将分割后的空间作为根节点的三个子节点。采取优先放置体积大的 物体策略，每次都先把最大物体放入剩余空间，这样每次放入相对 于当前布局空间来说是满足特定条件得最优解每放一个物体，就 把当前空间划分成了三个小空间，然后重复上面的过程逐个对分割 空间进行填充，直到没有剩余物体为止 上海交通大学的阎威武【1 8 1 在此基础上加入了重量的限制，通过 平均高度装载、货物合并、空间合并等策略，考虑了方向、重量、 优先顺序、货物的配置位置等约束条件，通过逐步淘汰差的装载方 案，得出最终优化方案 o 山东交通学院的陈建岭0 9 1 在g & r 算法的基础上对背包型集装 箱向题提出采用对每个货物“层”划分为一系列的垂直或水平的货 物“条”；从而将每个货物“条”的装填转化为求解容量等于货物 “条”长度的背包问题，另外为了保证货物层表面的平整性采取了 货物合并策略以减少空间碎片的产生 由于遗传算法在理论和应用上存在一些不足，在理论上它缺乏 深刻而又具有普遍意义的理论指导和数学分析模型，对于遗传算法 的评估都是基于对比实验的。对于严谨型启发式算法的研究，有北 方交通大学的何大勇、山东师范大学的王静莲对集装箱采用遗传算 法对集装箱 2 0 1 2 1 1 ，西南交通大学的卜雷 2 2 1 对零担货物装载进行研 究 目前，虽然较为成熟的商用软件已经面世，但由于商业及知识 产权保护原因，有关三维布局的空间规划问题公开发表的文献并不 多，而且很多只涉及较小规模的问题，并且都没有涉及到算法核心， 对于中等规模以上的问题，迅速上升的变量和约束条件的数目的算 法的计算时间难以承受但是从文献中可以看出，他们基本上都是 沿用启发式算法的思路寻找三维空间布局问题的可行算法。就国内 情况而言，除去几篇相关的文章外，对这一问题领域作专门研究的 相对较少。 山东大学硕士学位论文 1 5 课题的主要工作和内容 本课题研究的是车厢装入算法与软件实现。软件实现是把车厢 装入算法实用化，把理论算法与具体应用相结合。本文研究的是同 城配送所使用的客货两用车，这类车在侧面有一定的倾斜弧度，与 集装箱装载有所不同，本课题通过分析比较集装箱装载问题的研究 方法在借鉴集装箱装载的基础上，考虑这些因素，给出布局方案。 本文参考了国内外的有关文献和书籍，对集装箱装载问题及其 相关问题作了大量研究的基础上，深入分析了客货两用车车厢形体 的布局空间状态的有效表达，提出车厢装载的布局方案。根据城市 物流用车车厢空间不大的特点将空间按水平分层，根据物体的不同 边长作为层厚进行空间分割前人算法是将待装物体逐个搜索处 理，影响了算法的效率，本文将一层看作一个整体，将对物体的搜 索转化为对物体不同层厚的分层策略进行空间搜索，有效提高了算 法的效率。对于不能进行完全层装填的待装物体仍采用三叉树进行 空间分割装载。由于装填过程中对空间进行了切割，会产生虚拟的 废弃空间，在进行下一步装填时，这些废弃空间可以结合再利用， 剩余空间的结合也是本文的重点。最后以烟草配送为实验对象进行 研究，给出仿真优化结果 本文共分五章。研究内容分别为：第1 章绪论，介绍课题背景 与意义以及课题的内容，国内外的相关研究。第2 章阐述集装箱装 载优化的产生根源，相关问题的研究，集装箱装载问题的特点、分 类第3 章装箱启发式算法求解，详细给出本文问题的描述，重点 放在剩余空间搜索策略及空间积累策略上。第4 章基于计算机技术 的软件实现，通过卷烟配送案例进行分析，给出优化仿真结果。第 5 章总结与展望，对所做的工作进行总结，并对未来的研究做了展 望 山东大学硕士学位论文 第2 章集装箱问题简介 在集装箱运输中，降低运输成本，关键是提高集装箱的装箱量， 以降低单件包装产品的运费本文研究的是同城配送所使用的客货 两用车，车厢的形状不再是规则的长方体，这类车厢有自己的形状 特点，不能在完全按照集装箱装载的方法进行装载。但是我们研究 的对象同集装箱问题有很大的相似之处，但是都是将货物装填到一 个三维空间中去，同属于三维布局问题所以，可以借鉴集装箱的 研究方法来对本课题进行研究，有必要对集装箱问题进行分析研 究，为下一步的车厢装载实现提供思路。 2 1 装填与剪裁 集装箱装载闯题是一个三维装箱问题，这类问题属于裁剪与装 填问题( c u t t i n ga n dp a c k i n gp r o b l e m s ) 的一个分支。 ( 1 ) 装填与剪裁问题 剪裁问题，通常是指在一种材料上寻找各种形状的最佳布局以 使材料的浪费率最小，装填问题则通常是指将若干小的物体以最佳 方式组合并装入一个大的空间从而使空间的利用率最大 2 3 】切割 与装填问题的目标是寻求一种有效的切割和装入方式，最大化原料 利用率，装填问题与剪裁问题也称为布局问题。 剪切与装填问题是国际上备受关注的一类问题，剪切与装填问 题涉及现实生活中的许多行业，其中剪切问题主要涉及到诸如木材 加工业、服装皮革业、玻璃加工业、塑料行业、金属加工以及其他 很多行业中各种板材的合理下料闯题；装填问题主要涉及到半导体 加工业以及其他行业的布局设计、交通运输业中不同大小与形状的 货物的装载问题，货架上货物的摆放问题【2 4 1 布局优化能节省大 量的材料、缩减产品成本、提高材料的利用率，从而提高产品的利 润空间，收到明显的经济效益。 由于此类问题涉及面广、潜在价值巨大但复杂度高，因此吸引 山东大学硕士学位论文 了许多领域的研究者对它进行深入研究，使它成为涉及到数学、管 理及信息与计算机科学等众多学科的一个重要研究领域。 ( 2 ) 剪裁与装填的分类 从狭义上讲，剪裁与装填问题可在一维、二维、三维物理空间 中进行讨论。剪裁与装填问题可以分为：对各种原材料的剪裁问题， 包括一维剪裁问题( o n e d i m e n s i o n a lc u t t i n gp r o b l e m ) 、二维剪裁问 题( t w o d i m e n s i o n a lc u t t i n gp r o b l e m ) 、 三维剪裁问题 ( t h r e e d i m e n s i o n a lc u t t i n gp r o b l e m ) 等等各种装填问题包括：一 维装填问题( o n e d i m e n s i o n a lp a c k i n gp r o b l e m ) 、二维装填问题 ( t w o d i m e n s i o n a lp a c k i n gp r o b l e m ) 、 三维装填问题 ( t h r e e d i m e n s i o n a lp a c k i n gp r o b l e m ) 等其中，三维装填问题又可 细分为装柜问题( b i np a c k i n gp r o b l e m ) 、平板车装填问题( p a l l e t l o a d i n gp r o b l e m ) 、集装箱装载问题 2 3 2 5 l ( c o n t a i n e rl o a d i n g p r o b l e m ) 等。还可进一步根据物体的形状分为规则形状问题、不规 则形状问题等等。 从广义上讲，不仅物理空间才存在着剪裁与装填问题。如果我 们把剪裁与装填问题抽象化，就会发现对此类问题的研究广泛使用 于其他领域如将包内物体的价值当作某一维数据，这就是经典的 背包问题( k n a p s a c kp r o b l e m ) ；将时间参数当作前述剪裁与装填问 题的某一维数据，那么计算机系统结构中的流水线指令处理问题和 多处理器的并行处理问题就是一类典型的剪裁与装填问题；计算机 存储器的分配从某种意义上看也是一种剪裁装填问题【25 1 。这样的 例子还有很多，这类问题可被称为。非空间剪裁装填问题”。 ( 3 ) 剪裁与装填问题的关系 剪裁与装填，它们在本质上有着天然的内在联系，是一个互逆 的过程，很难用一个严格的界限将它们区分开来 2 6 1 。首先，它们 有两组相同的基本数据，一组是大的空间或原料，另一组是小的物 体或形状；其次，它们本质上都是一种几何组合，即将小的物体或 形状进行某种组合，使之能充分利用大的空间或原料。对于装填问 1 4 山东大学硕士学位论文 题，可以把向大空间中装入小物体的过程看作是将大空间以最小浪 费为目标剪裁成若干小空间，每一个小空间对应一个小物体；反之， 在剪裁问题中，可以将剪裁过程看作是将要裁减的形状以最大的原 料利用率为目标组合填回原来大的原料中去因此可以将这两类问 题视为同一个问题来研究。 ( 4 ) 剪裁与装填问题的常用算法 剪切与装填问题是一类被广泛应用的组合优化问题，属于 n p h a r d 问题，通常采用启发式算法寻找最优解或满意解。剪裁与 装i 填问题的研究最早出现在大约五十年代。对于剪切与装载问题的 研究，直接利用数学中的优化方法比较困难，在实际闯题上很难解 决，目前这一领域常用的算法有确定性算法和启发式算法。 1 确定性算法主要包括线性规划、整数规划、动态规划等传统算 法2 7 】【23 1 这类算法只能解决小规模问题，情况略加复杂，确定性 算法就会因为涉及的变量太多而大大增加计算的复杂性，因而不能 在确定时间内给出最优解 7 1 所以我们只能依赖于各种启发式方法 来解决这类问题所谓启发式算法实际上就是基于某种思想和机制 建立起来一种搜索规则，按照这个搜索规则，计算机可以在搜索空 间中寻找到一个较好的解，但不能保证找到最优 2 9 1 。运用这些启 发信息，应用某些经验或规则来重新排列节点的顺序，使搜索沿着 某个被认为最有希望的前沿去扩展，通过启发式算法可以在一个合 理的时间内解决非常复杂的问题。常用的启发式算法有：根据经验 建立的启发式方法的搜索即构造启发式算法以及进行全局搜索的 贪婪算法、遗传算法、模拟退火算法等等。 2 2c l p 问题的相关问题 在集装箱转载问题研究中，有三个与c l p 问题相关的布局问 题，可以借鉴其他与之相类似的装填问题所使用的研究方法。分别 介绍如下： ( 1 ) 背包装入问题( k n a p s a c kp r o b ie m ) 背包问题是一个非常有名的问题可以这样叙述如下假设有 山东大学硕士学位论文 一个容积为b 的背包，n 个体积分别为a s ( i = 1 ，2 ，n ) ，价值分 别为珥( i = l ，2 ，n ) 的物品。现在要求用这n 种物品的子集填 满背包，使得背包的价值尽可能高。模型表示为： 占 删缎乙q 薯 ( 2 - 1 ) j | l l s 芝：q 薯6 ( 2 - 2 ) 1|d 而 o ，1 ) o = 1 2 ，功 ( 2 - 3 ) 其中公式( 2 1 ) 欲使背包中所装物品的总价值最大；公式( 2 2 ) 为背包的约束条件，使背包中所装入物体总长度不大予背包的长 度；公式( 2 - 3 ) 表示而为二进制变量，而= l 表示第i 个物品装入背包， 薯= o 表示第i 个物品不装入背包。如果假设物体的利润等于他们的 体积，该问题即变为一个求解装箱空间利用率问题。 ( 2 ) 装箱问题( b jnp a c k in gp r o b i e m ) 有一些( 可以看成是无穷多个) 尺寸或长度相同的箱子，设其 长度为c ( c 0 ) 。现有1 1 个物体q ( i = l ，2 ，n ) ，每一种物品q 的长度为s ( q ) ，且都小于等于箱子长度c 。寻找一种算法，使得可 用最少数目的箱子将这些物品全部装入箱中，且每个箱子中的物品 长度之和不超过箱子长度c 装箱问题常见于一维与= 维情形，就 三维装箱而言与集装箱装箱区别不大【2 ”。 ( 3 ) 平板车装填问题( p a i i e tp a c k in gpr o b le f t l ) 平板车装载是将货物装在侧面没有遮挡或支撑的货盘上，装载 货物的边平行于货盘的边，物体之间互不重叠，而且物体装入的高 度不能超过货盘限定的高度，使得装载的空间利用率最大【23 1 托 盘装载的最大特点是侧面没有遮挡或支撑，货物码放时要考虑其稳 定性从而保证货物不会从货盘上掉下来，而集装箱装载不考虑这种 约束。 2 3 集装箱问题的分类 c l p 有许多不同的分类方式，主要有单集装箱装载 1 0 1 3 0 1 【3 1 】和 山东大学硕士学位论文 多集装箱装载，相同体积与不同体积装载四种分类方式。 集装箱装载问题以集装箱数量的有限和无限来划分，可以分为 二类；集装箱数量无限，货物必须全部装完，要求使所用的