（计算机软件与理论专业论文）集装箱装载问题的分析及其有效算法的研究.pdf

集装箱装载n d 题的分析及其有效算法的研究摘要 论文题目：集装箱装载问题的分析及其有效算法的研究 专业：计算机软件与理论 学号：0 8 2 1 2 2 9 0 硕士生：翁雨键 指导教师：郭嵩山教授 要 随着经济贸易的增长，物流效率的提高成为物流产业发展的一个主题。集装 箱作为物流活动，i - 最为重要的工具之，其优化问题的研究直接影响着食业物流 费刖的支出。集装箱装载问题是个经典的组合优化问题：给定的些不同规格 的三维箱子，将箱子的+ 个子集装载进集装箱，使得集装箱的空间使川率最大。 近几年，该问题的研究相对于过去有较大的突破，这主要源于利基i j 块构造的 观念的提出。本文称使用这个观念的算法为基于块构造途径的算法。近期的些 成功的算法本质上都是一类基于块构造途径的算法。然而这些具体的算法各自包 含了许多看似区别很大的模块，这使得对该问题及其有效算法做一个系统的分析 显得非常困难。 本文针对基于块构造途径的算法提出了一个包含6 个关键决策冈素的分析 框架，它们是：1 ) 可行放置区域的表示：2 ) 候选块的构造；3 ) 可用空问的选 择：4 ) 装载块的选择；5 ) 块在所选的空间- i 一的装载；6 ) 总体上使川怎样的搜 索策略。从本质上讲，所有基于块构造途径的算法之间的区别，仪住十它们对这 6 个决策要素各自采用的f j 发策略不同。基于该框架。本文埘近期发表的两个成 功但内部结构复杂的算法进行剖析，它们分别是划分控制树搜索算法( c l t r s ) 和极 大化空问表示算法( m s ) 。结合该框架的分析使得这些优秀算法内部的工作原理可 以被更好的理解，另外其不足之处也得以呈现。本文通过组合有效的策略，改进 评估函数的准确度，设计了个新的启发式算法。新算法使用个3 维的r - t r e e 来管理集装箱内部的剩余空间，这相对于基于列表的方式能更高效进行数据维护。 此外，新算法也加入了稳定性约束的考虑，保证了装箱方案中货物的摆放平稳。 本文在集装箱装载问题的1 6 0 0 个被j 泛使用的基准数据上进行计算实验， 结果表明新算法优于c l t r s 算法，能够扶得更高的空i 日j 使用宰。 关键词：集装箱装载、启发j 算法、块、树搜索、r - t r e e l 集装箱装载问题的分析及其有效算法的研究 a b s t r a c t t i t l e ： m a j o r n a m e ： a n a l y s i sa n de f f e c t i v ea l g o r i t h mr e s e a r c ho nt h ec o n t a i n e rl o a d i n gp r o b l e m c o m p u t e rs o f t w a r ea n dt h e o w y u j i a nw e n g s u p e r v i s o r ：p r o f e s s o rs o n g s h a ng u o a b s t r a c t a sa ni m p o r t a n tt o o li nl o g i s t i c si n d u s t r y , t h eu s eo fc o n t a i n e ra n di t sr e l a t i v eo p t i m i z a t i o n s d e e p l ya f f e c tt h ee c o n o m i cb e n e f i t so fe n t e r p r i c e s t h i sp a p e ra d d r e s s e st h ec o n t a i n e rl o a d i n g p r o b l e m ，w h i c hi st op a c kt h r e e - d i m e n s i o n a lb o x e si n t oac o n t a i n e rs oa st om a x i m i z et h ev o l u m e u u l i z a t i o no ft h ec o n t a i n e r m a n yr e c e n t l yd e v e l o p e d ，s u c c e s s f u lt e c h n i q u e sf o rt h i sp r o b l e m s h a r eas i m i l a rs t r u c t u r ei n v o l v i n gt h eu s eo fb l o c k so fb o x e s h o w e v e r , e a c ht e c h n i q u ec o m p r i s e s s e v e r a ls e e m i n g l yd i s p a r a t ep a r t s ，w h i c hm a k e si td i f f i c u l tt oa n a l y z et h e s et e c h n i q u e si na s y s t e m a t i cm a n n e r i nt h i sp a p e r , w ee x p l a i nt h e6k e ye l e m e n t si nb l o c kb u i l d i n ga p p r o a c h e s ， n a m e l y1 ) h o wt or e p r e s e n tf r e es p a c ei nac o n t a i n e r ；2 ) h o wt og e n e r a t ec a n d i d a t eb l o c k s ；3 l h o wt os e l e c taf r e es p a c e ；4 ) h o wt os e l e c tas u i t a b l eb l o c k ；5 ) h o wt op l a c et h es e l e c t e db l o c k i n t ot h es e l e c t e ds p a c e ；a n d6 ) w h a ti st h eo v e r a r c h i n gs e a r c hs t r a t e g y a l lb l o c kb u i l d i n g a p p r o a c h e so n l yd i f f e ri nt h es t r a t e g i e se m p l o y e df o re a c hd e d s i o n w es h o wh o wt w ol e a d i n g t e c h n i q u e sf o rt h i sp r o b l e m ，n a m e l yt h ec o n t a i n e rl o a d i n gb yt r e es e a r c ha l g o r i t h ma n dt h e m a x i m a ls p a c ea l g o r i t h mc a nb ee x p r e s s e di nt e r m so ft h e s e6e l e m e n t s ；t h i sa l l o w su st ob e t t e r a n a l y z et h ei n n e rw o r k i n g so ft h e s ea l g o r i t h m s i nt h ep r o c e s s ，w ea t t e m p tt oi d e n t i f yt h em o s t e f f e c t i v es t r a t e g yf o re a c hd e c i s i o n ，a n dc o m b i n et h o s es t r a t e g i e si n t oan e we f f e c t i v ea l g o r i t h m f o rt h ec l pp r o b l e m t h en e wa l g o r i t h mm a k eu s eo fa3 dr - t r e ef o rm a i n t a i n i n gt h es e to ff r e e s p a c e s ，w h i c hm a k ei tm o r ee f f i c i e n ti nc o m p a r et ol i s tb a s e dm e t h o d s m o v e o v e w ea l s ot a k e c o n s i d e r a u o n so ft h ec a r g os t a b i l i t y , o u ra p p r o a c hc a ng e n e r a t es o l u t i o n si nh i g hu t i l i z a t i o nw i t h a l lc a r g o sb ef u l l l ys u p p o r t e d c o m p u t a t i o n a le x p e r i m e n t so n1 ，6 0 0c o m m o n l yu s e dt e s tc a s e s s h o wt h a to u ra p p r o a c ho u t p e r f o r m sa l lo t h e re x i s t i n ga p p r o a c h e s k e yw o r d s ：3 dp a c k i n g ；h e u r i s t i c ；b l o c k ；i m c o m p l e t et r e es e a r c h ；r - t r e e 1 1 1 论文原创性声明 本人郑重声明：所呈交的学位沦义，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 驰显蹙 日期：丛f q 堡委臼翊 学位论文使用授权声明 本人完全了解【 l 山大学有关保留、使用学位沦文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学雠姗者虢镪形枝洲张新易 臼期：仂f o 年月l 日 日期砷年歹月乞悄 集装箱装载问题的分析及其有效算法的研究 第1 章绪论 第1 章绪论 本章介绍集装箱装载问题的背景，研究内容及意义，相关的研究现状，本文 的主要工作和创新点，论文的内锌安排。 1 1 问题的背景与意义 随着经济全球化的发展和网络经济的兴起，全球物流服务业加速发展。近5 年来，随着全球贸易活动的频繁发生，我闻物流总费用迅速增长：从2 0 0 4 年的 2 9 1 万亿元增长到了2 0 0 8 年5 4 5 万亿元。根据中国物流与采购联合会的统计1 ： 2 0 0 9 年前三个季度，我同的物流总费用为3 9 2 万亿元，与g d p 的比例为1 8 ， 比去年同期降低0 3 个百分点。这一方面反映了物流业总体运行效率有了一定的 提高，另一方面也表明了物流业对同家经济自着相当高的影响力。根据我同2 0 0 1 年颁布的物流术语国家标准定义2 ，物流是指物品从供应地向接收地的实体 流动过程。根据实际需要，将运输、储存、装卸、搬运、包装、流通加工、配送、 信息处理等基本功能实现有机结合，形成完整供应链，为用户提供多功能、一体 化的综合性服务。物流效率的提高，能够为企业带来直接的经济利益。 集装箱是现代物流活动在多个方面都会涉及到的一个重要工具。在某些发达 国家，集装箱运输方式儿乎占了物流运输量的全部。多数物流活动( 运输，储存 等) 以集装箱的个数作为计费单位。对于k 距离的运输，i 1 于单个集装箱高额的 运费，充分利用集装箱的空间，减少集装箱的使h j 能为企业节省下一笔b j 观的支 出。 集装箱装载问题( c o n t a i n e rl o a d i n gp r o b l e m ，c l p ) 就是研究如似为企业节省开 支，提高物流效率的一个资源最优化利用问题：当有大量的货物需要装载到集装 箱中时，企业需要求解一个装载方案使得集装箱空间使用率最大化。集装箱装载 问题作为物流配送过程中的一个关键降技术，对提高眦送业务的自动化水平、提 高货物装载的优化程度、提高配送业务的工作效率和规范、i k 务流程都彳j 币要的意 1 巾幽物流与采购暇合会熊岔以塑型丛塑艘型照! ：嫂婴：她 2 l 扛人民j l 帚l 国父通运输潍嗵q ；z 纽烈丝：丛! 鲢：g 鲤：匝 1 集装箱装载m 题的分析及其有效算法的研究 第1 章绪论 义。最大化集装箱的空间使用率，不仅是一个经济需要，也是一个生态优化需求； 交通工具运输货物同时，也在影响着大自然的生态环境。 集装箱装载问题相关的应用包括：港口集装箱货物的装卸；快递行业对投递 物品存货车上的装载等。此外，装箱问题存一些与运输业关系小大的行业上也有 应用的例子：钢板，玻璃，布料等材料裁剪问题( 二维的应州) ；资源调度的相 关问题；大规模集成电路的相关问题，比如t e i c h 等人于文献【1 】中应用三维装箱 模型来求解动态硬件配置问题：通过将二维的平面布局结合时间维度构成三维模 犁。 1 2 问题陈述 集装箱装载问题的形式定义如f ： 现有一些小的长方体箱子( 货物) ，按照箱子规格( 长宽高尺度) 的不同它 们被分为k 种不同的类型。第k 种类型的箱子k = 1 ，2 ，k ) 数量为n k ，长宽高i 个 维度分别为l k , w k , h k 。这些箱子需要被装载到一个人的长方体容器内( 集装箱) ， 集装箱的长宽高分别为l ，w ，h 。 箱子的摆放方向必须正交于集装箱，根据货物的不同，各维度足否允许垂直 放置的具体情7 兑不同。比如装载电冰箱只允许某。面朝上放置，而手机等货品允 许以任意正交与集装箱的方式放置。因此对- 丁每种类犁的箱子，最多会有6 种可 能的旋转方式，旋转后长宽高分别为：( 1 k ，w k ，h k ) ，( 1 k ，h k ，w k ) ，( w k ，l k ，h k ) ， ( w k , h k ，l k ) ，( h k ，i k ，w k ) ，( h k ，w k ，l k ) 。集装箱装载问题的优化目标为求解一个合法 的装箱方案，使得所装载的货物体积和最大( 等价的也是使得集装箱内浪费的空 间体积最小) 。装箱方案为货物的一个子集存集装箱中的摆放位置和旋转方式等 信息。合法的装箱方案要求货物完全处于集装箱内部( 不会有部分货物外露于集 装箱外) ，并且货物之间f i 存在相交。 针对不同的应用，集装箱装载问题的实例具有不同的特征。比如可能包含有 多种不同类型的箱予而同种类型的筘了数量较少( 强相异型，s t r o n g l y h e t e r o g e n e o u s ) 。这在快递服务中较为常见，因为通常米说客户快递的物品规格 不同：也u j 能只包含少数类型的籍f ，口f | i d 种类型的衍了具f j 较火的数量( 弱相 异型，w e a k l yh e t e r o g e n e o u s ) 。通常，从k f 仓库运送一批货物分发给各个零售 2 集装箱装载f n j 题的分析及其有效筇法的研究第1 章绪论 商的情况，属于该种类型的实例。另外还有一种叮能的情况是，实例中只存在一 种类型的货物( 同一型，h o m o g e n e o u s ) ，这种情况大多发生在生产线上配件的 运送。根据w i i s c h e r 等人于2 0 0 7 年提出的关于切割与装箱问题的分类方法 2 ， 弱相异型的集装箱装载问题属- 丁3 维单个长方体容器的物品摆放问题 1 3 - d i m e n s i o n a lr e c t a n g u l a rs i n g l el a r g eo b j e c tp l a c e m e n tp r o b l e m ，3 ds l o p p ) ，而强 相异犁的集装箱装载问题属于三维的单背包问题( 3 一d i m e n s i o n a ls i n g l ek n a p s a c k p r o b l e m ，3 ds k p ) 。 对丁现实世界中的大多数集装箱装载问题，集装箱的空间使用率是一个主要 的优化目标。一个密集的装载方案能够节省集装箱和货车的使用，这问接的减少 了氧化碳的排放量，从而使得生态环境受益。具体对于不同的应用场景，集装 箱装载问题还可能会有一些附件的约束，比如： 稳定性约束( 1 0 a ds t a b i l i t yc o n s t r a i n t ，l s c ) ： 货物摆放的稳定性是集装箱装载问题在多数实际应用中的一个重要约束。在 集装箱静i i ：的情况下( 仓库货物存储的场景) ，稳定性约束要求内部装载的货物 能够平稳放置，而不会山现倾斜或者倒塌的情况。通常来说，这种场景下的货物 稳定性可以通过货物的底面支撑面积来衡量，比如要求货物的支撑面积不低于底 面积的某个比率r ( 可能足5 5 ，7 5 或者1 0 0 ) 。事实上只有要求货物被完伞支 撑( 比率r 为1 0 0 ，即支撑面积等于底面积) 的情况下，才能够真正保证到货物 稳定。图1 - 1 为货物满足支撑面积不低于7 5 的条件下，装载方案仍不平稳的 例子：箱子构成的系统不满足力矩平衡。对于货车装载货物的场景，还需要考虑 运输过程中，货物在水平方向上的稳定性。这种场景下，是水平方向上的稳定性 信息可以通过货物的表币f 与其他货物或集装箱接触的情况来衡量。比如货物的前 后左右4 个垂直表面都有物体接触时，运输过程比较稳定。 二 三尹 图卜l 接触面积为7 5 仍不平稳例子( 图为横截面) 货物承重能力约束( 1 0 a db e a r i n gs t r e n g t hc o n s t r a i n t , l b s c ) ： 由丁1 i 同货物的重餐和承重能力1 i 同，为了避免货物存装载时被压坏，货物 承重能力约束要求合法的装箱方案满足各个货物上方承载的其他货物的重量总 集装箱装载闻题的分析及其有效算法的研，究第1 章绪论 和不超过其承重能力。此外，集装箱本身也可能有承重限制，要求内部装载的货 物重量总和4 超过其最大承重能力。文献 3 4 针对该约束进行了研究。 货物重量分布约束( w e i g h td i s t r i b u t i o nc o n s t r a i n t ，w d c ) ： 集装箱的重心位置如果偏离中心太多，在运输的过程中很容易导致交通事故 的发生。另外，港口使用龙门吊车将集装箱运送到轮船的过程，也要求集装箱的 重心尽量，f 稳。集装箱的重心主要由其内部装载的货物的重量分布情况所决定， 货物重量分布约束要求合法的装箱方案的重心偏离集装箱i h 心不超过某个阈值。 文献 5 研究的c l p 问题考虑了x 方向上的货物重鞋分布约束，它通过将集装箱 在x 方向上分成多个子空间来调整该方向上的货物重量分布。 多卸货点约束( m u l t i d r o pc o n s t r a i n ) ： 当货车运送的货物不止一个目的地时，会有取货次序的约束。具体来说，该 约束要求在同一目的地卸货的货物尽量排放在一起，并且不同目的地的货物之间， 按照到达的次序进行排放，先卸货的货物应尽量靠近车门。这样可以避免凶为卸 货而引起的重新装载。文献 4 提出了针对该约束的一个启发式的树搜索算法， 并在丹麦一个公司提供的真实数据上进行测试。 集装箱装载问题是一个n p - 难的问题 6 ：它是背包问题( k n a p s a c kp r o b l e m ) ， 在三维卒问上的一个扩展：由于背包问题本身足一个n p 完拿问题，因此集装箱 装载问题也不存在有多项式时间复杂度的算法。出于问题本身搜索空间的庞大， 求解精确解的集装箱装载算法通常只能求解小规模的问题 7 。现实世：界中的多 数装箱应用，货物的数量比较多，囚此求解问题的最优解是很困难的，这种情况 下，如何能在短时问内求解出一个近似解( 较优解) ，是该问题近期形f 究的主要 方向。 1 3 研究现状 现有文献中，求解集装箱装载问题最优解的精确算法并不多。p a d b e r g 等人 于2 0 0 0 年提m 了集装箱装载问题的一个o 一1 混合整数规划模型 8 。该模型通过引 入箱子之间的前后，左右和上下关系变量，米约束箱子使装箱方案中不存在柑交。 另外为了支持箍了旋转摆放，模型中也引入了棚应的变量。通过整数规划求解器， 该模型可以求解到问题的精确解。然而由于问题解空间过于庞大，文献 8 给出 4 集装箱装载n d 题的分析及其有效算法的研究第1 章绪论 的实验结果表明该模型仅可以解决较小规模的问题( 少于1 0 个箱子且集装箱尺寸 较小) 。该模型将所有合法的装箱方案一一对应到混合整数规划的可行解中，这 是使得可行解空间庞大的主要原因。比如个装箱方案的某个箱子坐标上的。点 微移，就对应了另一个4 i 同的解，而实际上这些解的目标函数值是相同的，我们 并不关心这类解之问的区别。冈此如果能够把等价的解合并考虑，将大大缩小模 犁的解空间。针对这个问题，f e k e t e ，s p 和s c h e p e r s ，j 等人提出了装箱问题的一 个新颖的图论模型【9 】。该模型将具有相同组合结构特征的类裟箱方案对应为 模酗的一个解而小是单独处理每个装箱方案，这大大缩小了模型解空问的大小。 具体该模型通过将合法的装箱方案中的箱子，在x y z 这3 个坐标轴上分别进行的投 影。每个箱子在一个坐标轴上的投影是一个区间，于是包含n 个箱子的装箱方案 在一个坐标轴上的投影是一个包含n 个区l h j 的集合。按照区i 日j 之问的重叠关系， 这些区间构成一个区间图( i n t e r v a lg r a p h ) ：陶中的每个顶点表示一个问，而任 何两个存在重叠区域的区l 日j 对应的顶点在图上都有一条边。于是每一个装箱方案 对应着二二个区间图( 每个维度的投影各有一个图) 。关于该模型，文献f 9 】汪明了 定理1 - l 。 定理1 1 - 箱了的集合v 能被装载进集装箱，当且仅当存在二个图g x = ( v ，e x ) ， g y = ( v ，e y ) ，g z = ( v ，e z ) ，满足属性p 1 - p 3 ： p i ：图g 褂g 。和g ：都足区间图： p 2 ：区间图g t ，i = x ，y , z 中的每个稳定集s 都是对应维度上。n j 放置的： p 3 ：e xne vne z = 移 其中p 2 提到的稳定集也称为独立集，是指图巾的一个顶点集合，满足集合中 的任意两个顶点不相邻( 之间没有边相连) 。而”埘应维度上可放置”是指，独立 集中所有顶点代表的箱子，在该维度上的长度之和不大于集装箱该维度的k 度。 属性p 2 保证了装箱方案不与集装箱相交。由于e 。t i 的边( u ，v ) 表示装箱方案i i 的箱 子u 和v 在x 维度上有重叠( 相交) ，对于y 轴和z 轴同理。p 3 要求：1 i 存存一条边( u ，v ) 同时在三个区间图的边集i 存在，这本质上保证了箱子之间不会存在相交的情况。 根据定理1 1 ，可以通过求解区间图来求解最优的装箱方案。f i 丁r f f l j 图代 表了类具有同样组合特征的裟箱方案，洲此该杉! 型可以有效的减少解伞1 1 i j 的大 小。基于该图论模型，f e k e t e ，s p 和s c h e p e r s ，j 等人提出了求解c l p i a i 题的几个 s 集装箱装载b d 题的分析及其有效算法的研究第1 章绪论 有效上下界估算方法【1 0 】，并利用这些界结合启发式算法设计了水解c l p i 口1 题最 优解的分支定界算法【7 】。f e k e t e ，s p 并f f s c h e p e r s ，j 等人的图论模型相对于c h e n ，c s 等人的混合0 - 1 整数规划模型来说，能够解决规模更大的c l p l 舀 题( 2 0 e 类型的 箱子，3 f 均每种箱子有2 0 个) 。另外，存新的图论模型中集装箱的大小小再是问 题求解能力的一个影响冈子。 由于实际应用中c l p 问题的规模较大，比如快递等应用，箱子的数最通常达 到几百的规模，这利，情况下求解问题最优解的精确算法往往无法胜任。冈此近年 来，学术上对c l p 问题的研究更多的集中存近似算法方面。现有的求解c l p 的近 似算法主要可以分为分治算法，邻域搜索算法和构造性算法等三大类。这三类算 法并非完全分离，现有算法中存在结合了两类算法的方法。 分治算法的思想在于不断地将集装箱划分成小的子集装箱，然后递归的求解 规模更小的问题，最终方案由所有的小集装箱的装箱方案合并产生。这类技术本 质上将货物装载问题转化成集装箱空刚分解分配的问题来解决，属于一种逆向 求解技术。完全的枚举所有可能的划分方案能够求解问题的最优解，然而这需要 指数级别的计算量。通常来说，分治算法通过限制递归的深度来求解问题的近似 解。另外其他被用于减小分治算法计算量的常见的技术还包括：非线性组合划分 方案的消除，即每一维上划分的位置必须- 毡箱子在对应维度上可以达到的线性组 合数：镜面对称方案的消除，即满足镜面对称的两个划分方案只需要考虑其中一 个；旋转等价方案的消除，即可以旋转后一致的两个划分方案只需要考虑一个。 文献 1 1 - 1 2 提出的算法属于分治算法。 基于邻域搜索的算法通过搜索当i ；i 装箱方案的邻域，使f ； 不州的邻域弹子对 当前解进行调整从而产生新的装箱方案。b o r t f e l d t ，g e h r i n g 和m a c k 等人基于元 启发工搜索算法发表了一系列集装箱装载算法，包括遗传算法 1 3 ，禁忌搜索 1 4 ，和混合算法 1 5 等，另外也包括这些算法的并行计算版本 1 6 - 1 8 。元启 发式算法定义了可行解之问的邻域结构，通过邻域变换多次迭代来产生优秀的解。 在这些算法l i i ，问题的解被表示为个代表着装箱次序的序列( 箱子的序列或者 是箱子组合体，墙或层的序列) ，邻域变换被定义为序列中元素的次序交换。本 文伤：这种采j | j 序列来表彳：问题的解的方法为垫j 二睁列编码的j a k i 发式算法。根据 解的序列将箱子使用某个确定的启发式算法进行装载，可以得到该序列对应的一 6 集装箱装载b q 题的分析及其有效算法的研究第1 章绪论 个装箱方案。一个解的评估值是其对应装箱方案的空间利用率。基于序列编码的 方法，对解( 序列) 进行解码的过程需要通过一个确定性的启发式算法来完成( 比 如最左下装箱法，最大接触面积法等) 。解码的速度在很大程度上影响了限定时 | 日j 内元启发式算法可以迭代的次数，间接影响了解的质量。目前已知的三维装箱 问题l - 效果较好的启发式算法都不低于规模平方的时间复杂度。综合文献 1 3 - 1 8 汇报的实验结果，可以发现串行版本的元启发式算法在这个问题上的应用结果并 不理想，尽管并行版本的算法会相对好些，但这本质上是以加大计算量为代价 的。为了避免解码造成的瓶颈问题，f p a r r e s o 等人在文献 1 9 中介绍了一种商接 在装箱方案的物理布局上进行邻域变换的算法，实验结果表明该方法相对于基于 序列编码的方法能够获得更好的解。总的来说，基于邻域搜索的算法是以较高的 复杂度和大量的计算时间来换取不错的空间使用率。 构造性的装箱算法通过一序列的箱子摆放步骤来构造产生完整的装箱方案。 基于块构造的方法属于一类构造性的装箱算法。区别于原始的构造性算法，基于 块构造的方法每一步同时解决多个箱子的摆放。该类方法是本文研究的重点。 定义1 1 ： 块( b l o c k ) 是箱子的一个子集紧凑放置在一起形成的一个组合体， 由它内部所有箱了的最小外包长方体所界定。 在基于块构造的方法中，集装箱内可行的放置位置被表示为一个可用卒间的 列表，装箱过程的每一步将一个块放置到集装箱内的某个可用空间中，然后更新 审问列表，迭代直至集装箱无法再放入更多的块( 如算法1 - i ) 。 根据集装箱装载问题的基准测试数据，当前最成功的几个算法 1 9 - 2 1 都属 于毖于块构造的装箱算法。其它基于块构造的算法还包括文献 1 8 ，2 2 。在文献 6 ，1 5 中，提出了一种基于墙构造的方法( w a l l b u i l d i n g ) 。这类算法首先将货物 在垂直方向上堆放成一堵墙，然后以墙为单位来装载集装箱。类似的还有基于层 构造的方法( 1 a y e r - b u i l d i n g ) ：以水平方向的层为单位，从下剑上一层层装载集装 箱 2 3 2 4 。本质上，垂直方向的墙和水i l 方向的层都是一类特殊的块，因此这 些方法可以看成是基于块构造的方法的早期形式。般来说，基于块构造的方法 存组合生成块时，井4 i 会生成所有可能的块。因为块的数骨= 是箱子个数的指数倍， i f i jj ：生块的过程本身等价，：求解。个小脱模的狄箱问题。通常束晚。基j 二块构造 的算法只保留高质毓的块作为装箱的候选块。1 i 同的块生成和保留策略将导致4 i 7 集装箱装载问题的分析及其有效算法的研究第1 章绪论 同效果的装箱算法。 算法1 1 基于块构造的装箱方法的基本框架 1 ：t h el i s to f f r e es p a c es4 - t h ec o n t a i n e r 2 ：w h i l e s 仍d o 3 ：p l a c eav a l i db l o c kbi n t oaf r e es p a c es ： 4 ： u p d a t et h el i s to ff r e es p a c es ： 5 ：e n d w h i l e 1 4 本文贡献及创新点 近期集装箱装载问题的一些成功的算法本质上都是一类荩，】：块构造途径的 算法。然而这些具体的算法各自包含了许多看似区别很大的模块，这使得对该问 题及其有效算法做一个系统的分析显得非常困难。针对该情况，本文标识出设汁 基于块构造的集装箱装载算法需要解决的6 个关键决策要素：所有基于块构造的 算法本质上只区别于各自对这些决策要素所采取的策略不同。提出该分析框架的 主要意义在于，它标记出了研究集装箱装载问题最为重要的几个方面，这使得后 续的研究可以专注于当前尚未被很好解决的方而，忽略一些次要的方而，从而在 根本上改进集装箱装载算法。 基于该分析框架，本文对该问题两个当前最优秀的算法进行了分析。这一方 面，验证了该分析框架的合理性：另一方面，也使得这些优秀算法内部的工作原 理可以被更好的理解。继而，本文对6 个决策要素分别对应的有效策略进行了深 入的分析，通过理论和实验结合的方法来解释怎样的策略足有效的。 基于策略有效性的分析结论，本文提出了集装箱装载问题的一个新算法 g 2 l a 及其解决完伞支撑约束的版本g 2 l a f s 。g 2 l a 算法使用长方体覆盖法来表 示剩余空间，根据箱子平均h j 用个数决策构造块的类型，使用两步前瞻的搜索结 合一个改进的评估函数f ( s ，b ) 来决策块的选择。对于装箱过程中剩余卒间的管理， g 2 l a 算法使用了个3 维的r - t r e e 数据结构来维护，使得长方体覆盖法所带来 的空间维护复杂等问题能够被高效的解决。g 2 l a 算法具有简单易于实现的特点， 然而在基准数据的实验- ，卜其表现不俗：这说明抓住问题本质决策要素( 6 要素) 有助丁- 设计出优秀月简单的算法。 此外，本文钳对装箱方案的货物稳定性方面进行了讨论，包括静态稳定性( 货 物存储) 及动态稳定性( 集装箱运输) 。货物稳定性涉及到货物的安全，是集装 8 集装箱装载n u 题的分析及其有效笄= 法的研究第1 章绪论 箱装载问题的另一个重要的考虑因素。 1 5 论文内容安排 本文后续的章节内容安排如下： 第2 章提出一个包含6 个决策要素的分析框架，并基于该框架对当d 订两个 成功的c l p 算法进行深入的分析，它们是基于划分控制树搜索的算法和笨于极大 化空间表示的算法； 随后，本文在第3 章对这6 个决策要素分别进行了深入的分析，讨论了各 自的晕要性及其对问题求解的影响。为了辅助分析，这一章介绍了一个俩步前瞻 的搜索策略，并给出其与划分控制树搜索算法的一个对比实验的结果。 第4 章将介绍本文提出的新的基于块构造的g 2 l a 算法，并介绍该算法如 何进行扩展以使得其能够求解带完伞支撑而积约束问题，从而产生g 2 l a f s 算法。 对于g 2 l a 算法及g 2 l a f s 算法需要苁同面对的町用空问管理问题，本章介绍了 女l i 何应用3 维的r - t r e e 数据结构进行高效的维护。 第5 章对本文提出的算法进行了计算实验，并与近几年的一些算法进行了 对比。此外，为了对g 2 l a 算法进行更深入的分析，本文进行了一些策略替换对 比实验，并分析了g 2 l a 采h j 的这些策略对算法的影响程度。装箱问题除空间利 用率外，货物稳定性是最重要的约束之一，第5 章对g 2 l a 算法产生的装箱方 案关于稳定性进行了- 定的分析。 最后，第6 章总结了本文的研究并存大的方向上对该问题的后续研究给 出了一。些建议。 9 集装箱装载 d 题的分析及其有效算法的研究第2 章基于块构造的c l p 算法的分析框架 第2 章基于块构造的g l p 算法的分析框架 c l p 问题现有的许多研究都趋向于使用高级的搜索技术，构造一个复杂的算 法来解决该问题。这导致了各种各样的差别较大的算法的产生。不同算法之间很 难进行优劣性的理论比较，最终只能通过实验结果来说明一些观点。对于所有情 况的测试数据下都能取得很好结果的算法，我们有理由相信它总体上优于其他算 法。然而事实上更常见的情况是，对于某些数据算法a 的表现比较i i j 色，而对于 另外些数据则算法b 表现更为出色。对于这样的例子，我们不能否定其一 某个 算法的作用。即使它仅在很少的情况下能够取得比其他算法优的结果，它也为问 题的求解带来了定的贡献。基于这利- 现状，为了更深入的挖掘出些优秀算法 之所以成功的原因，本章针对基丁块构造途径的集装箱装载算法提出了一个包含 6 个决策要素的分析框架。基于该框架，本章继而埘当前两个成功的c l p 算法进 行深入的分析，分解出其复杂的算法框架内部有效的工作部件。 2 1 基于块构造途径的6 个决策要素 在基于块构造途径的算法中，有6 个关键的决策子问题需要解决，本文将其 标记为k 1 到k 6 ，它们分别是： k 1 ) 如何表示集装箱中的可用空间； k 2 ) 如何构造候选块； k 3 ) 如何选取可月j 空间； k 4 ) 如何选取装载块： k 5 ) 如f l 叮将选取的块放置在所选的空间中并更新空间列表； k 6 ) 总体上使用怎样的搜索策略。 所有基于块构造途径的算法之间的区别仪在于它们对这6 个决策要素使用 的启发策略不同。一般来说，一个算法对这6 个决策要素所采用的启发策略并不 一定是在整个过程中保持不变的，比如口j 以存构造解的不同阶段中采取不同的启 发策略。此外，所有这6 个决策要素相互之问足完伞独、z 的，每。一个要素都可以 尝试使用不同的方法和技术去做决策。 1 0 集装箱装载问题的分析及其有效算法的研究第2 章基于块构造的c l p 算法的分析框架 第一个要素k l ，在于决策如何表示装箱过程中，任一时刻集装箱内部的可 行放置区域，即可用空间。一般来说，集装箱中的可用空间可以被表示为一个由 长方体构成的列表。比如当没有箱子被装载的时候，集装箱本身是+ 个长方体的 可用空间。图2 1 为个块( 黑色的长方体) 被放置存空间的一个角落。可以看 到，当一个块被装载进。一个可用空间时，米被占用的空间( 剩余空间) 构成一个 多面体的形状。这个多面体空间可以通过一i 同的方法表示为几个长方体空间的并。 图2 - 1 装载一个块后的空间 剩余空间可以被表示为三个不相交k 方体的并，这三个长方体构成多面体的 一个划分。如图2 - 2 所示，这样的划分总共有6 种。这种表示剩余空问的方式 被大多数基于块构造的集装箱算法所使用，本文称这种可用空i 日j 表示方式为长方 体划分法。 一一 ( b )c ) 一一一 图9 - 2 剩余空问的6 种可行划分 另一种将剩余空间表示成长方体的方式，是使用三个极大长方体来形成多面 体的个覆盖。其i l i ，极大长方体是指在空问内部的个与所放置的块不相交的， 并f 自身 i 可徘增人的长方体。剩余空问中小同的极大k 方体最多只有三个( 如 图2 - ：3 所示) ，这三个长方体相互之问存住重叠区域。本文称这利- 可，f j 空间表乃i 】1 粜# 葙# # 目爵分折a # # 教# * 研究# 2 章# r 块构c l p # 丹析担女 方式为长方体覆盖法。l i ma 等人在文献【2 s l 提出的多面构造算法及fp a r r e f i o 等 人在 1 9 - 2 0 】中提出的基于极大化空间表示的算i 圭采用了这种可用空间的表示方 式。 啕崤固 ( a ) ( b )( c ) i 叫2 - 3 _ 二个极大长a 体形成剩余空间的一个覆盅 剩余审问也可以使用已装载的筘子列表米隐式袭示，在每浪选定一个靠置装 载新的箱子时才与已装载的箱子进行判变潮4 试。这种表示方法可以完美的描述i l j 剩亲空间的准确形状，然而这需要以较大的计算量为附加代价，对于规模较大的 问题，该方法并不寅_ l j 。在后续的讨论中，奉文假定可用空删被显式的表示为一 个由长方体宅m 构成的列表。 第二个要素k 2 ，在于如何构造候选块。块从其构成来分可以分为简单块 ( s i m p l eb l o c k ) 和复合块( g e n e r a lb l o c k ) 两类。这两种类型的块都在现有文献中被 采用。简单良内部只包含一种类型的箱子，并且所有的箱子都以同个方向摆放 ( 如图2 - 4 ( a 1 ) 。相对而占复合块则允许多种不同类型的箱f 或同种箱子l l 不 同方向的摆破方式进行组合，构成一个块( 蓟旧2 - 4 ( b ) ) 。显然单个箱子组成 的块也是一个简单块，而任何简单块同时也是一种复合块。另外，纵向的瑞( w a l l l 剃横向的膳( l a y e r ) 也是一种特殊的简单块。 ( a ) 简单块( b ) 复合块 圈24 两种类型的块 巷j 块构造帕c l p 算法，装箱过程的每个i - 问状态叫以川三个) l 桑( s ，c ，b ) 来表示，其中s 为个妊方体的刘袭，表示当前容器中的卅州空间；c 为个箱 1 2 集装箱装载n 根匾的分析及其有效算法的研究第2 章基于块构造的c l p 筇法的分析框架 子的列表，表示当前还未装载的箱子；b 是一个由c 中的箱子组成的候选块的列 表。k 1 和k 2 策略的选择决定了搜索空间中的状态集合，而这些状态之间的转移， 则由k 3 k 5 所使h j 的策略所决定。基于这个状态表示，k 3 一k 5 分别对应着： k 3 ) 使用怎样的策略从可用空间列表s 中选出一个长方体s ； k 4 ) 使用怎样的策略从候选块列表b i 选出一个块b ； k 5 ) 将选出的块b 放置在选定的长方体s 内部的哪个位置： 所有基于块构造的方法都需要对k 3 一k 5i i 的每个决策分别设计出好的策略。 根据我们对文献的掌握情况，现有的方法在处理k 3 和k 5 这两个决策要素时，都 不约而i 列的采用了确定性的启发规则，而k 4 则通过搜索的方法来做决策。采取 这种做法的文献包括自适应随机贪心搜索算法【2 0 ，2 6 ，树搜索算法 2 2 1 和1 基于划 分控制树搜索的算法【2 1 1 。一般来说，用于决策k 4 的搜索策略是一类优先度优 先搜索，它们会借助一个评估函数f ( s b ) 用于评估候选解的质量。通过f 的反馈， 候选解被按照评估值从大n d , t 非序，从而引导搜索过程优先尝试质量较l 岛的解。 最后，搜索过程在其限定的搜索能力范围内找剑一个最好的块b 作为决策的结果。 k 3 一k 5 三个决策要素被确定后，块b 被放置于可用空甘js 内，而s 则从可用 空间列表s 中删除。用于表示s 的剩余空间的新长方体被插入到s 中。块b 中包 含的箱子将从可用箱子列表c 中删除。与此同时，候选块列表b 中会有一部分块， 因为其包含的某种箱子的数量超过其可用数量而从列表b 中被删除。于是，当 k 3 k s 三个决策被确定后，当前状态( s ，c ，b ) 将转移到下一个新的状态( s ，c 7 ，b 7 。 因此我们说k 3 k 5 决定了状态间的转移。 所有基于块构造的方法其构造解的过程都足住搜索空f u j t l - 探索一条从衲始 状态剑某个终i i ：状态的路径。将搜索空问中的每一个状态用一个顶点表示。而状 态之间的转移表示为顶点之间的一条有向边，那么搜索空间可以被表示为一个有 向图。 定理2 - 1 表示c l p 问题搜索空间的有向图是一个有向无环图( d i r e c t e d a c