（计算机软件与理论专业论文）求解三维装箱问题的启发式分层搜索算法.pdf

摘要 装箱问题广泛存在于工业领域，尤其是对于物流运输业和材料制造业，解 决装箱问题的效率和效果直接影响到行业成本和收益。随着我国市场经济的发 展，工业规模越来越大，装箱问题在商业活动中的作用将越来越受重视。解决 装箱问题的算法作为一项提高资源利用率的关键性技术，在充分利用运输能 力、减少材料损耗、保护自然资源等方面都有非常重要的意义。 尽管物流业务和材料制造业都发展很快，但装箱软件的数量和质量却没有 很大提高。至今为止，国内外许多学者对装箱问题已经进行了大量的研究，发 表了各种解决该问题的方法。本文在前人研究的基础上，提出一种新的装箱算 法，期望能够用新的方法，以更高的效率求解装箱问题。 本文提出了一个高效求解三维装箱问题的启发式分层搜索算法。本文的工作 包括：第一，基于块装载提出基础启发式算法，按照块选择算法确定每个阶段采 用的块，以一种固定的放置方式装载块，直到无法继续放置物品；第二，提出了 复合块的概念，与传统算法不同的是本文提出的复合块不只包含单一种类的物 品，而是可以在一定的限制条件下包含任意种类任意数目的物品；第三，以深度 优先搜索为基础进一步发展出分层搜索算法，在基础启发式的每一个装载阶段以 分层搜索确定当前阶段的选择，使得搜索结果更接近最优解。 本文采用了b i s c h o f f 和r a t c l i f f 的1 6 0 0 个三维装箱问题测试数据对算法进 行测试。实验结果表明，分层启发式搜索算法几乎在所有的测试数据上填充率都 超过了目前已知的优秀算法。 关键词三维装箱：启发式算法：搜索 a b s t r a c t c o n t a i n e rl o a d i n gp r o b l e me x i s t si naw i d er a n g eo fi s s u e si nt h ei n d u s t r i a lf i e l d ， e s p e c i a l l y f o rt r a n s p o r t i n ga n dm a t e r i a l sm a n u f a c t u r i n g t h ee f f i c i e n c ya n d e f f e c t i v e n e s so ft h es o l u t i o nt ot h i sp r o b l e mh a sad i r e c ti m p a c to nt h ec o s t sa n d b e n e f i t so ft h ei n d u s t r y a st h ed e v e l o p m e n to fc h i n a se c o n o m y ，t h es c a l eo f i n d u s t r i a la n dc o m m e r c i a la c t i v i t i e si n c r e a s e sq u i c k l y h o wt os o l v ec o n t a i n e r l o a d i n gp r o b l e mw i l lb e c o m em o r ea n dm o r ei m p o r t a n t a sak e ym e t h o dt oi n c r e a s e t h eu t i l i z a t i o nr a t eo fr e s o u r c e s ，p a c k i n ga l g o r i t h r n sh a v eag r e a ti n f l u e n c eo nm a k i n g f u l lu s eo f t r a n s p o r tc a p a c i t y , r e d u c i n gm a t e r i a l sa n ds a v i n gn a t u r a lr e s o u r c e s a l t h o u g ht h et r a n s p o r t i n gb u s i n e s sa n dm a t e r i a l si n d u s t r yd e v e l o pq u i c k l y , t h e q u a n t i t ya n dq u a l i t yo ft h es o f t w a r ef o rc o n t a i n e rl o a d i n gp r o b l e mh a v en o tb e e n g r e a t l yi m p r o v e d s of a r , s c h o l a r sh a v ed o n ep l e n t yo fr e s e a r c hi n t h i sf i e l da n d p r e s e n t e dav a r i e t yo fw a y st os o l v et h i sp r o b l e m i nt h i sp a p e r ，b a s e do np r e v i o u s s t u d i e s ，w ep r o p o s e dan e wp a c k i n ga l g o r i t h mt os o l v ec o n t a i n e rl o a d i n gp r o b l e mi n am o r ee f f i c i e n tw a y t h i sp a p e rp r e s e n t sa l le f f i c i e n th e u r i s t i c sm u l t i l a y e rs e a r c ha l g o r i t h mf o r t h r e e - d i m e n s i o n a lc o n t a i n e rl o a d i n gp r o b l e m i ti n c l u d e st h ef o l l o w i n gp a r t s ：f i r s t , w ei n t r o d u c et h eb a s i cb l o c k - b a s e dh e u r i s t i ca l g o r i t h m ，t h i sa l g o r i t h ml o a d so n e b l o c k ，w h i c hi sd e t e r m i n e db yb l o c ks e l e c t i n ga l g o r i t h m , i no n ep a c k i n gp h a s e a c c o r d i n gt oaf i x e ds t r a t e g yu n t i lr i ob l o c k sa r ea v a i l a b l e ；s e c o n d ，w ep r o p o s e dt h e c o n c e p to fc o m p l e xb l o c k ，t h ed i f f e r e n c eb e t w e e n t r a d i t i o n a lb l o c ka n dt h i sc o n c e p t i st h a ti tc a nc o n t a i nm u l t i p l et y p e so fo b j e c t si no n eb l o c ku n d e rs o m er e s t r i c t i o n s i n s t e a do f j u s ts i n g l et y p ep e rb l o c k ；t h i r d ，b a s e do nt h ed e p t h - f i r s ts e a r c ha l g o r i t h m , w ed e v e l o p e dam u l t i - l a y e rs e a r c ha l g o r i t h mf o rd e t e r m i n i n gt h es e l e c t e db l o c ki n e a c hp a c k i n gp h a s e , a n dm a k i n gt h i sr e s u l ta sc l o s et ot h eo p t i m a ls o l u t i o na s p o s s i b l e i nt h i sp a p e r , t h eb i s c h o f fa n dr a t c l i f f s16 0 0t e s td a t ao ft h r e e d i m e n s i o n a l c o n t a i n e rp r o b l e ma r et e s t e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t o u rh e u r i s t i c m u l t i - l a y e rs e a r c ha l g o r i t h mo u t p e r f o r m st h eb e s tk n o w na l g o r i t h mi na l m o s ta l lt h e t e s td a t a k e yw o r d s ：t h r e e - d i m e n s i o n a lc 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 ； s e a r c h ； 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) 彩趣 川年月箩e l 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () i 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) 玄逆乏 矿7 年月广日 求解三维装箱问题的启发式分层搜索算法硕士学位论文 1 1 研究背景 第一章绪论 装箱问题广泛存在于工业领域，涉及到工业生产的方方面面，包括运输业 的集装箱业务，材料制作业的切割业务，印刷行业的排版，工厂的设施规划等 等。尤其是对于物流运输业和材料制造业，解决装箱问题的效率和效果直接影 响到行业成本和收益。 随着我国市场经济的发展，工业规模越来越大，装箱问题在商业活动中的 作用越来越受重视。解决装箱问题的算法作为一项提高资源利用率的关键性技 术，对充分利用运输能力、减少材料损耗等方面都有重要意义。本文就是在这 样的背景下产生的。 1 2 研究意义 在我国，物流业尚处于产品生命周期的发展期，全社会的运输与物流成本 随着我国的物流业的发展节节攀升。由于社会工业的经济总量巨大，资源利用 率微小的提升就能节约大量资源。而如何提高材料或空间利用率、降低成本成 为一个很重要的问题。因此，采用更好的方式解决装箱问题，有着非常积极的 现实意义。更好的算法，意味着更高的材料和空间利用率、更低的成本、更高 利润，从而提高企业的盈利能力，并获得更多的经济和社会效益。 尽管物流业务和材料制造业都发展迅速，装箱软件的使用数量和质量却没 有很大的提高。至今为止，过国内外许多学者对装箱问题已经进行了大量的研 究，发表了各种解决该问题的方法。本文的研究，试图通过启发式分层搜索有 效寻求三维装箱问题的近似解，并为以后装箱问题和其他相关问题的研究以及 装箱应用软件的开发提供一个很好的借鉴经验和参考依据。 1 3 研究的内容 经典的装箱问题的描述是：将一定数量的物品放入有一定容量的容器中， 使得每个容器中的物品之和不超过容器容量并获得某种最佳的效益。待放入的 求解三维装箱问题的启发式分层搜索算法硕士学位论文 物品和使用的箱子均为长方体，这是因为一般产品在生产结束后为了运输搬运 的方便都用长方体包装，而运输容器一般也都是长方体的。 由于装箱问题涉及的领域多、应用背景广，不同情况的解决方法差异很大。 实际应用中的装箱问题有不同的优化目标和装载约束，为了更好地理解装箱问 题、设计算法，必须先按照一定的标准，将装箱问题划分成不同的装箱问题。 d y c k h o f fa n df i n k e 1 概述了不同类型的装箱问题及相关的切割问题。 按照在进行装箱操作的过程中，事先是否知道所有物品的信息，可划分为 在线问题和离线问题。在实际应用中，大多数问题是离线形式的。在最近的研 究中，尤其是针对三维装箱问题的算法设计中，大多研究的也是离线问题。 按照容器空间的维度可分为一维、二维和三维装箱问题。三维装箱问题是 一维、二维装箱问题的泛化。这类问题在集装箱装载、飞机装仓、码头装货、 托盘装载以及建筑、造船、电子等诸多领域有广泛的应用。 按照使用的容器数量可分为单容器和多容器问题，单容器装箱问题与背包 问题相似，目标是使所使用的容器空间利用率最高或装载的总价值最大。多容 器装箱问题又可分为单一种类容器和多种类容器两个自问题，目标是在装完所 有物品和满足约束条件的前提下，容器总使用成本最低，且均匀地使用每个容 器。单一种类容器问题的目标可以简化为使用的容器数量最少。 按照物品的种类数目可分为同构装箱问题和异构装箱问题。只有一种物品 类型的装箱问题被称为同构装箱问题。有少数几种物品类型且每种类型数量较 多的装箱问题被称为弱异构装箱问题。强异构装箱问题则有许多物品类型且每 种类型数量较少。 除了以上提到的分类，针对特定需求的装箱问题有很多约束，例如重心约 束，承重能力约束等。本文主要考虑的是离线的单容器异构三维装箱问题，可 以形式化定义如下： 给定一个容器( 其体积为v ) 和一系列待装载的物品，容器和物品的形状 都是长方体。问题的目标是要确定一个可行的物品放置方案使得在满足给定装 载约束的情况下，容器中包含的物品总体积s 尽可能的大，即填充率尽可能的 大，这里填充率指的是s v * 1 0 0 。可行放置方案要求放置满足如下三个条件： 2 求解三维装箱问题的启发式分层搜索算法 硕士学位论文 1 ) 被装载的物品必须完全被包含在容器中。 2 ) 任何两个被装载的物品不能互相重叠。 3 ) 所有被装载的物品以与容器平行的方式放置，即不能斜放。 除了以上的基本约束以外，针对实际问题，本文还考虑以下两个约束。其 中稳定性约束是可选，本文针对是否包含稳定性约束的情况设计不同的算法。 ( c 1 ) 方向约束 在许多应用中，物品的装载有方向约束。也就是说，每个物品只有它的一 条或几条边可以竖直放置作为高度。没有此约束的问题可以被简单的视为所有 物品的三条边都可以作为高度。 ( c 2 ) 稳定性约束( 可选) 在许多应用中，特别是在交通运输业中，装载必须满足稳定性约束。这意 味着每个被装载的物品必须得到容器底部或者其他物品的支撑。也就是说，禁 止被装载的物品悬空。 1 4 三维装箱问题启发式算法研究现状综述 目前对三维装箱问题算法的研究，多集中在异构装箱问题上。一方面是因 为多数实际应用中，都涉及到种类繁多的物品；另一方面是因为在解决单一种 类的三维装箱问题时，二维问题的算法也对其提供了思路，如果待装物品完全 相同，那么在一个平面上求出面积利用率最大的布局模式后，只要在高度方向 上扩展该布局模式即可。 装箱问题是典型的n p - h a r d 问题 2 ，即不存在多项式时间复杂度的算法保 证能找到问题的最优解，用传统的精确搜索技术求解这类问题，会产生“组合爆 炸的现象。因此采用装箱问题的精确求解算法是不现实的，启发式求解方法 成为理论研究和实际应用的首选。 近年来，涌现出许多解决装箱问题的算法。对于二维装箱问题，历史上有 一些不错的启发式求解算法 3 ，4 ，5 ，6 。对于三维装箱问题，g e o r g e 和 r o b i n s o n 2 1 ，m i c h a e le l e y 2 3 ，n g o i 7 ，b i s c h o f f 8 以及b i s c h o f f 9 等提出了一些启发式算法。而基于图搜索的算法可以参考文献r m o r a b i t o 3 求解三维装箱问题的启发式分层搜索算法 硕十学位论文 1 0 。g e h r i n g 1 2 ，b o r t f e l d t 1 3 ，g e h r i n g 1 6 和s e i j ik o i d e 2 2 等 报告了遗传算法在装箱问题中的应用。s i x t 1 4 和b o r t f e l d t 1 5 等给出了 装箱问题的模拟退火算法和禁忌搜索求解算法。最近，l i m 1 7 ，j u r a i t i s 1 8 ， b i s c h o f f 1 9 ，2 0 ，m o u r a 2 5 等提出了一些新的有趣的启发式算法。 国内学者对三维装箱问题的研究，也取得了一些不错的结果 2 6 ，2 7 ，2 8 ， 2 9 ，3 0 ，特别是黄文奇教授等提出了一个有效的求解一类装箱问题的算法 3 0 。下面就对其中一些有代表性的算法做一个简单的综述。 一种在算法设计中应用较多的是垂直“层 ( 1 a y e r ) 或“墙 ( w a l l ) 的概 念。使用“层 来生成摆放模式的基本思路是：通过生成垂直的互不相关的包 含多种物品的层，由这些层来组成完整的放置方案，层内单个物品的放置方式 不同的算法有各自的规定。g e o r g e 和r o b i n s o n 2 1 首先提出了基于“层 的 启发式方法。b i s c h o f f 和m a r r i o t t 2 4 比较了1 4 种基于“层”的方法。因为 层与层之间互不关联，独立存在，所以一个完整的放置方案中，这些层的顺序 可以随意调整，使得一些约束更容易被满足，例如对重心的要求。 d a v i dp i s i n g e r 1 1 基于“层 设计了一种启发式算法。其基本思想是： 将整个容器空间分成若干垂直的层，再将层分成若干水平或垂直的带，装填带 的时候以容器的宽或者高为背包的容量、所有未装入物品为对象，按背包问题 填充这些带，并最终获得全局最优解。其中，合适的层的深度和带宽通过分支 定界法获得，在这个过程中包括了多种排序和选择的规则。这种方法容器的利 用率较高，但货物稳定性很差，上层货物经常得不到下面货物的完全支撑。 a n d r e a sb o r t f e l d t 和h e r m a n ng e h r i n g 1 3 在层概念的基础上，应用遗 传算法设计了一种混合遗传算法。这个算法使用复杂的数据结构以自然的方式 来表示解( 染色体) ，即装载计划，而不像一般的g a 对解进行编码。根据染色 体，算法能使用基本规则、最佳选择策略和启发式方法生成层以及层内物品的 放置方案。通过这种编码方式，算法可以考虑很多不同约束，适用于物品种类 很多、约束复杂的情况。但是，在空间利用率和稳定性方面，该算法存在一定 不足。由于这种垂直“层 及其摆放方式的特点，使用这一方法生成的布局模 式的稳定性不高。因此除“层以外，还出现了许多其他的装箱策略。 4 求解三维装箱问题的启发式分层搜索算法硕士学位论文 s e ij ik o i d e 2 2 等人将遗传算法和传统的桁条搜索算法( b e a ms e a r c h a l g o r i t h m ) 与装箱问题的启发式方法相结合，针对该问题开发了拼箱算法。 e e b i s c h o f f 等人 9 针对异构装箱问题，从由底向上的摆放方式出发， 提出了基于“平面 的算法。由底向上每次只放入一层最多由两种物品组成的 水平层，迭代填充和生成平面、水平层，获得有效且具有高稳定性的放置方案。 算法通过设定的规则选择合适的物品、平面、位置等放置参数，采用平面合并 等方法提高平面利用率，进而生成一个较好的完整放置方案。虽然放置稳定性 方面表现不错，但此算法所得解的平均填充率不高。 a g e h r i n g 和a b o r t f e l d t 1 2 引入了“塔 的概念，算法的基本思路是 先用待装物品生成许多塔，生成一个由互不关联的塔组成的集合。然后将这些 塔按设定的一系列规则放入目标容器，生成完整的放置方案。最后使用遗传算 法( g a ) 调整初始解以取得较好的近似解。该算法在放置稳定性方面表现不错， 对物品种类少或多的情况均适用。 与“塔 和“层”的概念不同，m i c h a e le l e y 2 3 设计了基于同类“块” ( b l o c k ) 的算法，完整的放置方案是由这些同类“块组成的，而“块则 是由完全相同的物品( 物品种类和放置方向均相同) 组成的没有空隙的长方体 结构。算法用贪婪算法生成初始解，然后用分支定界法改善初始解，在选择下 一个节点时采用最佳搜索策略，即只选择具有最佳评价值的节点作为下一步的 拓展节点。该算法在容器空间利用率和稳定性方面表现较好，并且由于块与块 之间不关联的特点，可以很好的满足重心约束。 b o r t f e l d t 1 5 进一步拓展了“块的概念，使其可以包含一到两种物品 并且容许包含空隙出现在“块”中。为防止“组合爆炸，“块 只能按照某种 特定的方式被生成，一个基础启发式算法被用来生成放置方案。该启发式算法 分阶段进行装载，在每个装载阶段，首先生成所有可能的“块”，并按照体积 从大到小排序，每个阶段选取的“块 由输入的放置序列决定。按照这种方式， 放置序列被作为放置方案的一种编码方式，算法采用禁忌搜索寻找最优的放置 序列作为问题的近似解。由于允许更多的组成块的方式，算法的结果得到了改 善。但是在一些情况下“块 中包含过多的空隙，算法的结果有可能变差。另 5 求解三维装箱问题的启发式分层搜索算法硕士学位论文 外，由于基础启发式中可以考虑各种约束，算法有很好的灵活性。 另一个被经常用到的概念是“剩余空间 。“剩余空间 是容器中一个未被 填充的长方体空间，它可以被某种方式填充，填充以后的未填充空间被切割成长 方体成为新的“剩余空间”。在初始状态下，容器是唯一的“剩余空间”，算法以 某种特定的启发式填充空间，生成新的装载空间，直至没有新的可用的“剩余空 间”生成。m o u r a e 2 5 基于此概念提出了一个贪心随机自适应搜索算法( g r a s p ) 。 p a r r e f i o 2 6 3 进一步发展和改进了该算法，取得了非常不错的结果。 t o b i a sf a n s l a u 和a n d r e a sb o r t f e l d t 2 7 基于“块的概念，提出了“复 合块”，允许“复合块 包含多种类型的物品，并且通过一些约束保证块中的物 品保持较高的填充率。该算法结合了“复合块”和“剩余空间 ，可选择通过限 制剩余空间的切割方式保证物品装载的稳定性，并在装载过程中采用基于整数拆 分的树状搜索寻找局部最优解作为算法选取的“块”。“复合块 的引入大大增加 了可用的块数量，而有效的启发式树状搜索也使得对解的评估更为精确，整个算 法的结果有了很大提升，是目前解决装箱问题最有效的算法。 随着研究的深入，研究人员在设计算法时开始重新考虑一些重要的实际约束 在装箱过程中的作用及其对放置方案的影响。一般装箱算法在处理约束时，只是 将它们简单地作为物品在放入容器空间时的限制规则。这样做对某些约束，比如 物品的方向约束，是合适的，但对有些约束，比如物品的承重约束，却不能如此 处理。以物品的承重约束为例，若仅以某个平面的承重能力来限制在这个平面上 摆放物品的可能性，那么不仅不会防止承重能力低的物品放在较低的位置，而且 会浪费这些物品上的空间，从而降低整体的空间利用率。处理这类约束更好的方 式是，建立能够使承重能力低的物品放在较高位置的机制。 1 5 本文的内容安排 本文研究了三维装箱问题，重点研究了离线的单容器异构三维装箱问题。 针对三维装箱问题的特点，提出了复合块的概念以及基于块装载的基础启发式算 法，接着采用分层搜索算法选择在每个阶段应选择的块，并取得了非常好的效果。 本文的内容安排如下： 第一章介绍了本文的研究背景、意义及国内外研究现状，并对本文的内容安 6 求解三维装箱问题的启发式分层搜索算法硕士学位论文 排进行了介绍。 第二章主要介绍了算法的整体架构和一些重要的概念和数据结构，其中包括 简单块、复合块、剩余空间、放置、放置方案等等；接着，详细描述了本文采用 的基础启发式算法，并针对带稳定性约束和不带稳定性约束的问题设计了不同的 放置方式和未填充空间的切割方式。 第三章详细介绍了简单块和复合块的概念和约束，并给出了相应的生成算 法。 第四章重点介绍了块选择算法，首先对块选择问题进行了概述，并介绍了基 于整数拆分的树状搜索算法，接着分析了三维装箱问题的一些特性，进而提出分 层搜索算法，最终给出了本文采用的块选择算法。 第五章给出了算法的实际运行结果，并且比较分析了本文算法与历史上其他 算法的计算结果。 第六章是对本文的总结，并指出了进一步的工作。 其中二、三、四章是本文的核心。 7 求解三维装箱问题的启发式分层搜索算法 硕士学位论文 第二章基于块装载的启发式算法 2 1 算法总体结构 因为装箱问题本身的复杂性和实际操作需要，必须使用启发式方法才能有效 的生成放置方案。一个良好的启发式算法不但应该能迅速找到解，而且应该尽可 能的接近最优解，同时算法还应该提供必要的灵活性使其能够适应不同的场合和 需求。本文提出的启发式算法，以一个设计良好的基于“块”装载的启发式方法 为基础，通过启发式搜索算法选择每个阶段采用的块。“块 装载方法决定了算 法的“骨架 ，搜索算法则决定了算法逼近最优解的速度和效果。算法总体框架 如图2 1 所示。 为方便下文描述，先介绍一下算法用到的一些基本概念和要素。 1 ) 三维装箱问题。如前所述，装箱问题研究的是在满足一定约束的情况 下往容器中放置尽可能多的物品。所以问题的描述由容器大小、物品 的类型以及物品数量三部分构成。 2 ) 块及可行块列表。本文研究的算法以块为基本单位，块是一种概念上 的长方体，包含一种或多种物品。块内的物品按照某种方式放置并保 证满足方向性约束c 1 以及可选择的稳定性约束c 2 ，块可以随意的被 放置到容器中某个剩余空间而不破坏其内部的约束c 1 或c 2 。对于一 个剩余空间，所有能放入它的块的集合按体积从大n d , 的排列的列表 被称作可行块列表。 3 ) 剩余空间及剩余空间堆栈。如前文所述，剩余空间是容器的一部分未 使用长方体空间。在启发式过程中，所有剩余空间被组织成一个堆栈， 每次只处理位于栈顶的剩余空间。另外，在本文中，当考虑稳定性约 束c 2 时，算法要求所有的剩余空间都被容器底部其他物品支撑。 4 ) 剩余物品向量。表示当前还未被装载的物品数量的向量。 5 ) 放置。将一个块放入一个剩余空间被称作一个放置。需要注意的是， 当考虑稳定性约束c 2 时，由于本文算法在生成块的时候保证其内部 物品受到其他物品的支撑满足稳定性约束c 2 ，同时我们也能通过约束 剩余空间的生成方式保证剩余空间的底部也受到支撑，所以此时每一 求解三维装箱问题的启发式分层搜索算法硕士学位论文 个合法的放置中的所有物品也必然是受到支撑满足稳定性约束c 2 的。 6 ) 放置方案。算法产生的所有放置的集合就是一个放置方案，其包含了 所有放入容器的物品的位置信息。 7 ) 基础启发式。本文算法的基础启发式运行如下：首先生成所有可能的 块列表，接着初始化剩余空间堆栈包含容器为唯一的剩余空间，开始 迭代；每次迭代从栈顶取出一个剩余空间，生成它的可行块列表；若 是列表不为空，则通过块选择算法确定一个近似最优块放入剩余空间 生成一个放置，并将未填充空间分割成新的剩余空间加入剩余空间堆 栈；否则，放弃当前剩余空间，并尝试将未使用空间中可重新利用的 部分并入堆栈中相应的剩余空间；算法不断重复此填充过程，直至堆 栈为空。需要强调的是，基础启发式与块是如何生成以及块选择算法 的选择完全无关，块生成算法和块评估算法可以被替换以生成更有针 对性的算法。 8 ) 部分放置方案和块选择算法。在基本启发式过程中的某一个时刻，剩 余空间堆栈和剩余物品构成了一个部分放置方案。块选择算法按照某 种方式评估当前可行块，并从中选择一个最优的块。 9 ) 搜索算法参数及时间上限。为保持搜索的灵活性，搜索算法的参数可 由输入参数调整以在计算时间和计算精度上做取舍。而时间上限则用 于防止算法使用过长的时间。 2 2 基本概念和数据结构 在装箱问题中，由于所有的物体都是与坐标轴平行的长方体，为方便描述 和计算，对它们引用都是通过参考点和其各个维度上的边长来指定。所谓参考 点定义为一个物体的左后下角，也就是其x 、y 、z 坐标均最小的点。同时为了 方便的进一步描述算法，我们简要的介绍一些主要的数据结构： 1 ) b o x 是物品的抽象表示。为了简化计算，本文算法将按照物品的可摆 放方向，在预处理过程中生成所有可能的b o x ，并通过t y p e 指定其真 实的物品类型。也就是说一种物品如果允许所有三条边竖直摆放的话， 将生成6 种b o x 。b o x 的定义如下： 9 求解三维装箱问题的启发式分层搜索算法 硕士学位论文 1 0 求解三维装箱问题的启发式分层搜索算法硕士学位论文 s t r u c tb o x i n tl x ，l y ，l z ： i n tt y p e ： 三边长度 物品类型，不同的b o x 可以有 相同的类型 ) ： 2 ) s p a c e 表示剩余空间，同样采用参考点的加三边长度的方法来表示。 s t r u c ts p a c e i n tx ，y ，z ： 参考点坐标 i n tl x ，l y ，l z ： 三边长度 ： 3 ) p r o b l e m 包含容器，b o x 列表以及可用物品向量，形式化描述了装箱问 题。 s t r u c tp r o b l e m s p a c ec o n t a in e r ：容器 b o xb o x 口： b o x 列表 i n tn u m ： 可用物品向量 ) ； 4 ) b l o c k 结构表示块。b l o c k 既可以表示简单块也可以表示复合块，它有 一个r e q u i r e 向量指出其包含的所有的物品的数量。按照本文算法对 块的定义，当考虑稳定性约束c 2 时，由于块中有空隙，块的顶部有一 部分可能由于失去支撑而不能继续放置其他块，顶部可放置矩形记录 了块的顶部可以继续放置其他块的矩形区域。这里，块顶部可放置矩 形以左后上角为参考点，块结构的域a x 、a y 表示其长宽。另外，尽管 本文算法约束了复合块生成的方式，但是复合块的数目可能产生“组 合爆炸，所以我们限制了块的最大复合次数，b l o c k 结构中的t i m e s 域用于记录复合次数。 求解三维装箱问题的启发式分层搜索算法硕士学位论文 s t r u c tb l o c k i n th ，l y ，l z ： i n tr e q u i r e ： b l o c kc h i l d s ： i n tv o l u m e ： i n ta x ，a y ： i n tt i m e s ： i n tf i t n e s s ： 块的三维大小 所包含物品向量 构成该复合块的子块， 若是简单块则为空 所包含物品的体积总量 顶部可放置矩形的长宽( 考虑c 2 ) 复合的次数 块的适应度，在进行块选择时使用 ) ： 5 ) p l a c e 表示放置，是一个包含剩余空间和块的二元组。 s t r u c tp l a c e s p a c es p a c e ：剩余空间 b l o c kb l o c k ： 块 ) ： 6 ) p a c k i n g s t a t e 表示部分放置方案，包含已生成放置、剩余空间堆栈、 剩余物品向量以及已装载物品总体积和最终总体积的评估值。 s t r u c tp a c k i n g s t a t e p l a c ep l a n ：已生成放置列表 s p a c es p a c e s t a c k ：剩余空间堆栈 i n ta v a i l ： 剩余物品向量 i n tv o l u m e ： 已装载物品的总体积 i n tv o l u m e c o m p l e t e ：最终装载物品的总体积的估计值 ) ： 7 ) 为避免重复计算，本文算法在算法开始时计算出所有可能的复合块， 存储在全局变量中b l o c k t a b l e 。这样，在某一时刻计算某一个剩余空 1 2 求解三维装箱问题的启发式分层搜索算法 硕士学位论文 间的可行块列表时，只要扫描b l o c k t a b l e 找出所有的所有能放入该剩 余空间且能被当前剩余物品满足的块即可。 2 3 基础启发式算法 2 3 1 基础启发式算法概览 启发式方法是人们在解决问题时所采取的一种根据经验规则来处理问题的 方法。其特点是在解决问题时，利用过去的经验，选择已经行之有效的方法，而 不是系统地、以确定的步骤去寻求答案。启发式方法解决问题的方式不同于穷举 算法。穷举算法是把各种可能性都一一进行尝试，最终找到问题的答案，但它需 要在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是 在有限的空间内搜索，大大减少尝试的数量，能迅速地给出问题的解。但由于这 种方法具有尝试错误的特点，所以也有失败的可能性。 启发式方法是非常有效的，是人类解决问题的重要方法，事实上，科学家的 许多重大发现，常常是利用极为简单的启发式规则。在人工智能中常用启发式方 法设计计算机程序，模拟人类解决问题的思维活动，已经证明，这是一条有效的 途径。 启发式方法的设计具有很大的随意性和创造性，而且一般缺少严格的理论推 导和数学证明，因此，一般也只能通过大量的试验数据来检验算法的性能好坏。 由于对于n p 完全类的组合优化问题，目前缺少一般的算法来求解，精确算法又 太耗时，因此启发式算法被越来越多的应用到这些问题的求解中。对于离线单容 器三维装箱问题亦是如此，自从该问题被提出以来，学者提出了很多启发式算法。 人们把日常生活中积累下来的经验转化为计算机搜索中的启发式策略从而引导 装载过程。 本文中提出的基于块装载三维装箱问题的求解算法，是受日常生活的启发而 提出的启发式算法。该算法的思想类似于二维装箱问题的递归启发式算法 3 ， 也是对b o r t f e l da n dg e h r i n g 1 5 中提到的基础启发式算法的改进。在算法的 开始，根据指定的输入，选择生成简单块列表或者复合块列表。启发式算法维护 个剩余空间堆栈，自顶向下地装载剩余空间。在算法开始时，容器是剩余空间 堆栈中唯一的剩余空间。在装载过程中，栈顶剩余空间被取出，在有可行块时采 求解三维装箱问题的启发式分层搜索算法 硕士学位论文 用块选择算法指定一个当前最优的块与剩余空间结合生成一个放置，并将未填充 空间切割成新的剩余空间加入堆栈；在无可行块的情况下则抛弃该空间并试图将 此空间中的可利用空间并入新的栈顶的其他剩余空间。上述过程将被不断重复， 直到堆栈为空。 1 4 求解三维装箱问题的启发式分层搜索算法硕士学位论文 算法2 - 1 给出了基础启发式的具体描述，首先算法根据输入参数指定的 i s c o m p l e x 生成所有可能的简单块或复合块；接着初始化当前部分放置方案，并 开始装载过程；每个装载阶段，算法从剩余堆栈栈顶取出一个空间s p a c e ，用 g e n b l o c k l i s t 生成它的可行块列表；当列表不为空时，f i n d n e x t b l o c k 算法选择 一个块进行放置并加入当前部分放置方案，接着采用g e n r e s i d u l s p a c e 切割未填 充的空间并将它们插入堆栈；当列表为空时，算法尝试重新利用s p a c e 中的可转 移空间，t r a n s f e r s p a c e 算法完成这个工作。 上面提到的算法将在后面的小节中详细描述，其中最关键也最复杂的块选择 算法由分层搜索算法实现，具体的算法将在第四章中描述。 2 3 2 可行块列表生成 可行块列表生成算法g e n b l o c k l i s t ( s p a c e ，a v a i l ) 用于从b l o c k t a b l e 中获 取适合当前剩余空间的可行块列表。其中，b l o c k t a b l e 是预先生成的所有可能 的块的列表。这种分离式的设计使得基础启发式算法与块生成算法完全无关，块 生成算法可以根据需要进行定制而不影响基础启发式算法。本文算法采用的块生 成算法将在第三章中详细讨论。 算法2 - 2 描述了上述可行块列表生成算法，该算法扫描b l o c k t a b l e ，返回所 有能放入剩余空间并且有足够剩余物品的块。由于b l o c k t a b l e 是按块中物品总 体积降序排列的，返回的可行块列表b l o c k l i s t 也是按物品总体积降序排列的。 1 5 求解三维装箱问题的启发式分层搜索算法 硕士学位论文 2 3 3 空间切割和空间转移 在每个装载阶段一个剩余空间被装载，装载分为两种情况：有可行块，无可 行块。在有可行块时，算法按照块选择算法选择可行块，然后将未填充空间切割 成新的剩余空间。在无可行块时，当前剩余空间被抛弃，若其中的一部分空间可 以被并入当前堆栈中的其他空间，则进行空间转移重新利用这些空间。 图2 2 、图2 3 分别显示了在不考虑稳定性约束与考虑稳定性约束剩余空间 与块结合成为放置以后的状态。未填充空间将被按照不同情况，沿着块的三个面 被分成三个剩余空间。需要注意的是，在考虑稳定性约束时，由于要保证所有剩 余空间受到足够的支撑，z 轴上的新剩余空间在切割的时候必须沿着所选块的顶 部可放置矩形进行。因此，块顶部的可放置矩形确定了一个新的剩余空间s p a c e z ， 其余的两个剩余空间为x 轴方向上的s p a c e x 和y 轴方向上的s p a c e y ，所以只有 两种切割方法。而在无需考虑稳定性的情况下，未填充空间的切割更加随意，一 共有六种切割方法。 如图2 - 4 所示，各种切割方式本质上的不同就在于可转移空间的归属。我们 希望在切割过程中尽量保证空间完整性，而衡量空间完整性的方法有很多，本文 选择的策略是另切割出的剩余空间尽可能的大。这里大小的判定以剩余空间在放 置块以后在x 轴、y 轴和z 轴上的剩余长度m x 、m y 、m z 作为度量，将可转移空 间分给剩余量较大的方向上的新空间。算法中g e n r e s i d u a l s p a c e ( s p a c e ，b l o c k ) 执行未填充空间的切割，其返回的剩余空间s p a c e x 、s p a c e y 、s p a c e z 按照m x 、 m y 、m z 的从小到大排列，并确保最后入栈的是包含可转移空间的剩余空间。表 2 1 、表2 - 2 分别列出了在考虑稳定性以及不考虑稳定性的情况下，剩余空间的 切割方式以及三个空间的入栈顺序。 1 6 求解三维装箱问题的启发式分层搜索算法硕士学位论文 y z y c ) z y e ) x x y y z b 、 z z 、 q 图2 2 剩余空间切割和转移( 无稳定性约束) 1 7 x x x 求解三维装箱问题的启发式分层搜索算法 硕士学位论文 z x z y a ) y b ) t r a n s f e 陷 图2 3 剩余空间切割和转移( 有稳定性约束) z s f e r a b l es p a c e x x y a ) t r a n s f e r a b l es p a c e y b ) x s p a c e x 图2 4 可转移空间 由于切割算法保证了包含可转移空间的剩余空间后入栈，所以其必然被先装 载，若在装载过程中可行块列表为空，栈顶空间中的可转移空间可以被转移给剩 余空间堆栈中来自同一次切割的其他空间以重新利用。观察图2 4 ，我们发现可 转移空间的重新分配实际上就是对未填充空间的重新切割。因此，我们可以通过 求解三维装箱问题的启发式分层搜索算法硕士学位论文 重新切割未填充空间来达到再次利用可转移空间的目的，算法中的 t r a n s f e r s p a c e ( s p a c e ，s p a c e s t a c k