多面体Packing问题的并行启发式蚁群算法研究——硕士论文

I 学校代码 学 号 分 类 号 密 级 硕硕 士士 学学 位位 论论 文文 多面体多面体 Packing 问题的并行启发式蚁问题的并行启发式蚁 群算法研究群算法研究 学学 位位 申申 请请 人人 指指 导导 教教 师师 学学 院院 名名 称称 信息工程学 院 学学 科科 专专 业业 软件工程 研研 究究 方方 向向 软件开发与项目 管理 年 月 日 II 摘要 装箱问题 (Container Loading Problem, CLP) 在物流、多处理器调度、资源 分配和包装等方面有着广泛的应用。本文研究多面体的装箱问题，该问题可描 述为将若干不同形状的多面体放入固定矩形底的集装箱容器内，要求箱体高度 尽可能小。 从本质上看，集装箱装载问题为 NP 难问题。由于解空间为高维实数空间， 且多面体的不相交判断计算量相当巨大，比其它 Packing 问题更难求解，甚至 于一般的串行计算机无法在多项式时间内找到可行解。到目前为止，启发式、 演化算法是解决这类组合优化问题的有效方法。但解决本文问题相关文献比较 少，求解精度和计算效率仍然有待提高，且都具有一定的局限性，如限制物体 形状和物体放置方向，需要计算临界多面体等。本文在湖南省自然科学基金项 目“三维静动态平衡约束多形状布局问题的全局协同优化机理与方法研究”的 资助下，展开对该问题的研究，主要工作和创新描述如下： 1、本文提出了一种新的 IHAPE3D (Improved-HAPE3D)算法。 （1）在重力 势能的基础上，引入了另外两个方向的引力势能，进而基于最小势能原理重新 定义了系统的势能表达式；(2) 利用“平面分离定理”进行多面体干涉判断， 采用 GPU 多线程并行计算物体的最优放置状态，减少计算时间。实验结果表明： 提出的方法提升了容器的空间利用率、减少了求解时间。 2、本文提出一种多面体 Packing 问题的启发式蚁群算法。设计蚁群算法的 动态信息素自适应更新规则，能避免蚁群迭代陷入于局部最优和提高大规模问 题的搜索速度。通过实验对比，表明改进后的 IHAPE3D 算法与蚁群算法结合 可以有效优化多面体装填顺序，相比已有的实验成果，进一步的提升了容器的 空间利用率。 本文以现实生活中的集装箱装载问题为背景，深入探究了三维空间中多面 体 Packing 问题。首先提出了一种基于最小势能原理的 Packing 启发式算法，可 以根据给定条件高效地计算出 Packing 方案，再针对具体问题，混合了动态蚁 群算法以进行优化，比较高效地解决了三维中多面体的 Packing 问题。希望本 文能作为三维多面体 Packing 问题求解的阶段性成果，将来为更多类似的布局 问题研究提供思路和参考。 关键词：关键词：三维布局；多面体布局；蚁群算法；集装箱装载 Abstract III The container loading problem has widely applied to various areas such as logistics, multi-processor scheduling, resource allocation, cutting and packing. This paper focuses on the problem of loading polyhedron in a container (CPLP). The problem might be described as follows: packing several different-sized and different- shaped polyhedra into a given box container with fixed rectangle base, the objective is to minimize the height of the container. CPLP is no doubt an NP-Hard problem, which cannot be solved within a polynomial time by a natural serial computer. Compared with other packing problems, it is more difficult to solve for CPLP, because of its high dimensional real solution space and a large amount of non-intersected calculation. So far, heuristic algorithm and evolution algorithm are feasible to solve CPLP, but literatures published are few and have respective restricted conditions (for example, only fitting to regular-shaped polyhedron, no rotating the polyhedron, computing the no-fit polyhedron). How to improve the solution accuracy and calculation efficiency has been the problem explored by scholars. This paper discusses the ant colony heuristic algorithm for CPLP and the work is supported by Natural Hunan Province Science Foundation Project “Study on the global cooperative optimization mechanism and approach for the 3D multi-shape packing problem with static and dynamic mass balance(Grant No.2017JJ2250)”.Major content and innovations are as follow: 1. An improved HAPE3D algorithm is proposed for CPLP. (1) Besides gravitational potential energy, brings in another two attractive force potential energy from two different directions, therefore IHAPE3D redefines the potential energy equation of the system based on the principle of minimum total potential energy; (2) Using “Plane Separation Theorem” to detect the penetration between two polyhedra and concurrent GPU threads to calculate the optimal packing attitude of a polyhedron in parallel, so it takes less time to calculate the optimal packing pattern. Experiment revealed that IHAPE3D improved the utilization of the container space and reduced the calculating time. 2. A heuristic ant colony algorithm is proposed for CPLP. A dynamic pheromone update strategy is designed for avoiding the ant colony algorithm being trapped into local optimum iterations and accelerating the searching speed when it comes to large scale problem. Experiment revealed that hybrid ACA with IHAPE3D to optimize the packing order can make a decent improvement on the utilization of the container space. IV Under the background of the Container Loading Problem in real life situation, this paper researches on the three-dimension multi-shape polyhedron packing problem in depth. First, proposed a heuristic packing algorithm based on the principle of minimum potential energy to decode given packing order, then hybrid it with an improved Ant Colony Algorithm to search for the optimal solution. Hopefully this study can be regarded as a periodical achievement in three-dimension packing problem and provide inspiration and approach for others in the future. Keywords: three-dimension packing; polyhedron packing; ant colony algorithm; container loading problem 目 录 V 第 1 章 绪论1 1.1 课题的背景.1 1.2 三维多面体 PACKING 问题2 1.2.1 三维多面体 PACKING 问题的描述2 1.2.2 三维多面体 PACKING 问题的约束类型2 1.2.3 三维多面体 PACKING 问题研究现状3 1.3 课题研究的内容和意义.8 1.4 研究的基础.9 1.5 论文的组织.10 第 2 章 基于最小势能原理的多面体 PACKING 方法11 2.1 问题的提出.11 2.2 问题的数学模型.11 2.3 IHAPE3D 构造性算法 12 2.3.1 最低势能原理12 2.3.2 BLF 条件.13 2.3.3 基于“平面分离定理”干涉检测法 13 2.3.4 IHAPE3D 算法实现流程.14 2.4 基于 CUDA 并行计算15 2.4.1 GPU 加速16 2.4.2 CUDA 并行计算技术.16 2.4.3 IHAPE3D 并行化算法.17 2.5 实验结果与分析.18 2.5.1 实验结果18 2.5.2 算法分析20 2.6 小结.20 第 3 章 求解三维 PACKING 问题的动态启发式蚁群算法22 3.1 问题的提出及相关知识.22 3.2 动态启发式蚁群算法概述.23 3.2.1 基本蚁群算法概述23 3.2.2 基于动态更新策略的蚁群算法23 3.3 实验结果与分析.26 3.4 小结.29 总结与展望30 VI 参考文献31 致 谢35 附录 A：实验算例输入数据36 附录 B：攻读硕士学位期间发表论文和参与的研究项目39 1 第 1 章 绪论 1.1 课题的背景 本文以集装箱装载问题(Container Loading Problem)为研究背景，主要研究 三维空间中，多面体的 Packing 问题。Packing 问题经常出现在工业领域中，或 者属于其他问题的子问题。质量高的 Packing 方案可以显著的减少工业中的运 输成本和生产成本，甚至可以减小二氧化碳的排放，因此 Packing 问题数百年 来都是使数学界十分感兴趣的研究领域。Packing 问题可以大概表述为将给定的 待布物装入一个或多个容器中，待布物不能超出容器范围之外放置，而且待布 物之前不能发生重叠情况。待布物和容器可以是规则或不规则的形状(多边形或 多面体)。 基于 Wscher 等50提出的分类方法，可以根据装载容器和待布物的类型来 对集装箱问题进行分类。形状和维数相同的装载容器(待布物)可以看作为同一 类型，如果在一个集装箱装载问题中，装载容器(待布物)可以按照类型分组， 而且每个组中有一定数量的装载容器(待布物)，则此问题属于弱异类集装箱装 载问题；若没有或只有少数几个装载容器(待布物)属于同一类型，那么此问题 属于强异类集装箱装载问题。 集装箱装载问题还可以分为：1、提供足够的装载容器，可以装载所有待布 物；2、没有足够的装载容器，只能选择待布物的子集进行装载。这两类问题的 优化目标不同有所区别，第一种问题属于输入值(装载容器的个数)最小化类， 第二类问题属于输出值(装载待布物的个数)最大化类。 Packing 问题根据空间维数的不同通常可以分为一维 Packing 问题、二维 Packing 问题、三维 Packing 问题，随着空间维数的增加，解决问题的难度和计 算复杂度也随之增大。而集装箱装载问题属于三维 Packing 问题，三维 Packing 问题通常存在以下难点： 1、计算量繁重且复杂，尤其是计算物体之间的重叠干涉情况时，要考虑到 点，线，面各个方面的干涉情况。 2、从本质上看，三维 Packing 问题为 NP 完全问题，以至于在普通的串行 计算机上无法在多项式时间之内解决。 3、组合优化问题经常发生组合爆炸的情况，寻满足约束条件的最优解变得 十分困难。 2 4、对于 Packing 问题的优化易进入局部最优的陷阱，从而无法寻找到全局 范围内的最佳 Packing 方案。 本文以集装箱装载问题为研究背景，结合图形学，几何学，算法设计为理 论依据，基于现有算法，提出了一种更加行之有效的混合启发式算法，通过研 究实验对比，该算法相较以往同类型的算法，在性能与效率上有明显的优势。 1.2 三维多面体 PACKING 问题 1.2.1 三维多面体 PACKING 问题的描述 将一组形状不规则的多面体装入容器内并最小化未利用空间或最大化空间 利用属于三维多面体 Packing 问题中的组合优化类问题。此类问题经常出现在 现实生活中，比如集装箱装载与卫星舱的布局，设计 Packing 方案是普遍存在 的一个关键环节，一个合理的 Packing 方案可以提高空间利用率，减少生产和 运输成本，从而带来巨大的经济效应。从理论上角度来看，三维多面体 Packing 问题属于 NP 完全问题，确定最优解非常困难。 图 1.1 集装箱装载问题 图 1.2 卫星舱布局问题 1.2.2 三维多面体 PACKING 问题的约束类型 在三维 Packing 问题中存在着许多约束，按照被约束物的不同，区分为容 器约束和待布物约束。这些约束有可能与容器与待布物之间的关系有关，也有 可能与装载的过程有关。约束的强制性分为硬性和非硬性，其中硬性约束是一 定要被满足的，一个违反了硬性约束的 Packing 方案被将被作为禁止方案，而 一定限度下违反非硬性约束，是可以允许并接受的。在三维 Packing 问题中， 常见的约束有以下几种： 1、 重量约束(容器约束)：大多数问题中，容器只能装载有限重量的待布物。 少数情况下可以忽略重量约束的影响，比如待布物的材质为橡胶泡沫类时。 3 2、 重量分布约束(容器约束)：在某些情况下，要求待布物的重量被均匀的分布 在容器底的平面上，这样能增加装载的稳定性。 3、 Packing 优先级约束(待布物约束)：这类约束经常出现在输出值最大化类装 载问题中，因为容器的装载量有限，所以通常要决定哪些待布物优先装载， 而哪些待布物将被舍弃。在现实场景中，优先级一般根据运送截止日期、待 布物的保质期来制定。 4、 旋转约束(待布物约束)：为了减小问题的复杂性，通常会限制待布物放置方 向上的改变。 5、 堆叠约束(待布物约束)：这类约束考虑到了待布物的承重问题，如果某个待 布物上堆叠的其他待布物的重量超过了此待布物的承重限度，将会造成待布 物的损坏。 6、 分配约束(待布物约束)：在某些情况下，某种类型的待布物会被要求装载在 同一个容器内，比如运输目的地相同的待布物；而有些类型的待布物不允许 被装载在同一个容器内，比如食物类和毒性化学物品类的待布物通常不允许 装载在一个容器内。 1.2.3 三维多面体 PACKING 问题研究现状 上个世纪 50 年代末，当时印刷工业和造纸工业的材料利用成本都非常高， 因此 Paul1提出了用线性规划的方法来求解工业中长方形的 Packing 问题，这 是最早用来寻找 Packing 问题的最优解的方法。 当涉及到不规则的形状时，研究者们渐渐开始采用一些近似方法来求解 Packing 问题，比如计算物体的最小包络矩形。Huang 等2使用枚举法来搜索金 属板块的最小包络矩形。Xue 等3采用遗传模拟退火混合算法来搜索非凹多边 形的最小包络矩形。Chaudhuri 和 Samal4采用最小二乘法来决定物体长轴与短 轴的方向，以此来获取最小包络矩形。但是，最小包络矩形只是一个近似值， 所以并不能充分有效的利用材料。 为了提高解的质量，许多启发式被应用到了 Packing 问题中。启发式算法 不依赖理论依据，完全基于经验提出。虽然这种以直观感受以及相关经验为基 础的算法，只有一定几率获得全局最优解，但可以在能够接受的时间以及空间 范围内，得到一个有效可行的方案。Packing 问题由于其超复杂性和自身的组合 爆炸性质，属于 NP 完全问题，以至于在普通计算机上，不可能在多项式时间 内得到最优解。所以通常，一般用动态规划或者启发式，有时候用两者的结合 来求解该类问题。这些方法不能保证求出最优解，但为了保持较高的求解效率， 必然要在解的质量与求解时间之间的寻找一个最佳平衡点，而利用该类算法可 4 以很好地解决这个问题，因此在求解 Packing 问题时，动态规划和启发式算法 被应用得十分广泛。 在三维 Packing 问题研究中，大多数已发表的文献都只涉及到规则形状的 多面体，比如 Wu 等5和 Allen 等6提出的立方体布局研究，Stoyan 和 Chugay7 提出的圆柱体布局研究, Al-Raoush 和 Alsaleh8提出的球体布局研究，以及一些 特殊的形状比如 Song 等9提出的药片状的微粒布局研究。Bortfeldt 和 Wscher9统 计到只有 1.8% 的 Packing 问题领域的文献涉及到了不规则的形状。 George 和 Robinson27首先介绍了一种启发式思想将 20 种不同类型的盒子 装入集装箱中。先将这些盒子按照一些关键因素确定放置优先级，然后对这些 待布物使用围墙法，即将先装入的盒子贴着容器的某一个垂直内壁作为初始墙 面放置，形成一层放置层，再将此放置层作为墙面，形成下一层放置层，以此 方法循环，当所有的放置层铺满容器底面后，再从余下的盒子中，选择尺寸合 适的盒子，填满放置层内的空隙，以提高空间的利用率。 Kovel28开发了一种自动机器人系统来帮助邮局将包裹装填入运输箱内。但 受限于包裹传送带的物理条件，机器人每次只能选择 35 个包裹。在每一次循环 迭代中，评估每一个包裹的可能放置方案的优劣，从中选择最优方案。已放置 的包裹形成一片禁放区域，即它们的垂直投影。现实情况中，包裹是从上到下 进行放置，在该算法中，横向放置取代了竖向放置，因为横向放置可以增加包 裹堆放的稳定性，也可以为下一次放置提供更大的放置基底。然而，传送带的 容量限制会造成空间利用不充分，包裹在运输箱的四个角落呈现金字塔式的堆 叠状态。 Gehring29等而是介绍了一种适用于不同尺寸盒状物的启发式装箱思路。该 算法同样利用围墙法，将待装箱货物按体积从大到小确定放置优先级，首先会 将货物填满集装箱的底面，再向上循环构造放置层。该算法中不允许跨层放置， 只能移动一整个放置层来调整重量分布，所以可能会造成空间利用率的减小。 Loh 和 Nee30同样利用围墙法，不同的是他们用水平造墙替代了垂直造墙。 盒状物的高度成了确定放置优先级的唯一依据，因为这样能形成较平整的放置 层。在该算法中，实用了动态移动边界技术来隔离已放置和未放置的区域，并 且用一组结点来标记盒装物之间高度的差值。虽然这种方法一定程度上能改善 空间利用率，但实际情况中，盒装货物的高度很难形成大面积的统一，所以当 放置过程接近收尾阶段时，最后几层的放置层几乎不可能形成。 计算临界多边形(no-fit polygon,NFP)法一直被大多数研究者用来解决二维不 规则形状 Packing 问题。尽管已经有数百种方法被提出 (Bennell 等10; Liu 和 He11; Burke 等12)，但 NFP 的计算依然是一个十分消耗时间的过程。以 SWIM 5 基准问题为例，Burke 等12表明需要花费 1/66 秒去计算产生一个 NFP。所以在 问题规模为 10 个物体，每个物体有两种放置方向的情况下，只需要 1/66(102)2 = 6.06 s 的总体执行时间，这看起来是一个可接受的运行时间长度。 可随着问题规模增大到 50 个物体，每个物体有 4 种放置方向的情况下，执行时 间会骤升到 1/66(504)2 = 606.06 s。至于在三维 Packing 问题中，计算 NFPs 的时间则是增长到了更加无法令人接受的地步：1/66(5043)2 = 5454.55 s(大 约 1.5 小时)。更坏的情况是，即使忽略计算时间过长的问题，在三维 packing 问题中，至今还没有研究者提出一种可靠有效地计算临界多面体的方法。 在计算 NFP 这道巨大的障碍面前，研究者不得不另辟蹊径。Stoyan 和 Chugay7将一个多面体拆分成了许多轴对齐的包围盒(axis-aligned bounding boxes, AABBs)，这样多面体之间重叠干涉检测的速度将会显著缩短。但是，如 果多面体进行了放置方向上的改变，AABB 将变换成方向包围盒(oriented bounding box, OBB), 重叠干涉检测将比 AABB 变得复杂许多。 Zhang 等13则将多面体拆分成球体。这样做的好处非常明显，第一球体之 间的重叠干涉检测非常简单，第二球体不用受到旋转的影响。 从以上的讨论中，我们可以观察到 Stoyan and Chugay7和 Zhang 等13的方 法都必须将多面体拆分成许多更小的组成部分。因此精确度与速度之间的权衡 选择，使研究者们感到十分为难。 所以研究者们开始寻找新的方法，Jens Egeblad 在自己的博士论文中提到了 一种基于松散放置原则的启发式思想。在初始时刻，随机放置各个物体，并且 允许物体与物体之间、物体与容器之间存在重叠干涉情况，之后经过循环迭代， 逐渐减小各物体之间的重叠区域。具体做法是，使物体沿着某一个坐标轴的方 向往可以减少最多重叠的位置移动，如此循环移动每一个物体直到容器中不存 在任何重叠情况为止。 而 Xiao LIU 和 Jia-min LIU 14基于最小势能原理，提出了一种更高效可行 的新的构造性算法HAPE3D。该算法最大的优势是不用计算临界多面体(NFP)， 而且适用于任意形状的有洞或无洞多面体 packing 问题，并且每个多面体都可 以绕任意坐标轴旋转不同的角度来改变放置方向。 虽然 HAPE3D 本身已经在解决三维 packing 问题上有很好的效果，但也有 必要混合启发式算法来搜索更好的解。许多基于 Szykman 和 Cagan15、Cagan 等16提出的模拟退火算法的优化方法被广泛应用到解决三维 packing 问题中。 原文中作者选择使用模拟退火算法与 HAPE3D 算法混合，以此来优化 Packing 序列。 除了 Packing 算法，部分针对三维 Packing 领域的评论文献也指明了目前的 6 研究现状。Dowland33在测试了一系列的三维 Pakcing 启发式算法后指出，针对 Packing 问题的算法应该是通用并且可以应用于多种情境，而且不能过度依赖计 算机的计算性能。一些改进策略比如分析现有算法中各种参数因子影响作用、 重新审查已有文献、从真实用户群中获取使用反馈。Bischoff 和 Marriott34分析 了十四种不同的启发式装箱算法。这十四种启发式算法都是由27,37中算法的 变体。这些算法共同特征是，一开始就规定了货物的装箱顺序列，而且都是从 容器最远的一角开始放置货物，一般按照规定的方向来延伸货物的放置区域。 严格的按照既定的放置序列、放置位置来排放待布物，这样一些其他更优潜在 放置位置就得不到利用，明显增加了放置的限制性。 实际生活中，除了 Packing 问题以外经常可能遇到其他难以求解的问题。 比如是旅行商问题或背包问题，或者是根据现实意义的财务应用问题，比如投 资组合选择，破产预测，信用评分，数据挖掘等。解决这些问题的算法一般是 专门为这个问题设计，只能小范围地应用于这类问题，或者是比较适用性比较 普遍，但是效率低下的算法。一些普通的搜索启发式算法，如简单枚举算法需 要大量的计算时间，而且如果问题维度的增加，算法的基本会趋于无效。像另 外一种爬山算法则很容易受困于问题解空间的多个峰值之间，陷入一些局部最 优的陷阱。 过去几十年，受到大自然的启发，研究者们为解决这类难以求解的问题引 入了若干相关概念。大部分概念来自于人工智能或人工生命研究领域，一些更 受欢迎和成功的例子是神经网络，模糊算法和进化算法。 而进化算法在 Packing 问题研究上应用得十分广泛，与其他方法相比，进 化方法的主要优点是，它们只需要利用到很少的关于问题本身的具体知识，并 且可以广泛地应用于的各种问题。进化方法只需要给定一个关于该问题的适宜 度函数，它就能针对该适宜度函数对问题进行优化。属于该问题额外的特定知 识也可以很轻易地被带入进化算法的启发式，以其提高性能。进化方法对问题 空间的性质没有任何特别的限制，进化算法甚至可以应用到一些具有不连续， 不可微分和带嘈杂性质的目标函数的复杂问题上。更重要的是，进化算法对外 部进化参数因子的反应表现出较强的鲁棒性，因此进化算法不需要特殊调整或 者专家知识就可以适用到截然不同的问题上。由于进化算法的多样性，对于给 定的问题，可以很容易地就找到适用的进化方法，不论处理的数据类型，或者 解空间的表示和搜索空间拓扑形式。 从运算研究的角度来看，进化算法属于元启发式类41,42,43。 “元启发式”这 个术语首先出现在44, 源于两个希腊词的组成。 “元”意味着“超越，更高级别”。 在这个术语被广泛采用之前，元启发式通常被称为“现代启发式”45。遗传算法、 7 模拟退火算法和蚁群优化算法，也通常被归类于元启发式，广泛应用于 Packing 问题的优化。 遗传算法是被广泛认可的有效搜索模式，应用于图像处理，作业调度，模 式识别等许多有关人工智能的领域，尤其适用一些需要获取相对较好的解决方 案的 NP 难高纬度优化问题。遗传算法保留候选解的编码，这些编码的原型是 自然界中个体的染色体的，在自然进化中，染色体将不断进行变异和重组，使 生物进化为更加优质的个体，遗传算法的提出正是受到了生物个体择优进化的 现象。像上文提到，进化算法需要定义一个适宜度函数来定义每个解决方案的 质量。在遗传算法中，适宜度越高的父代种群更有可能被选择，再利用操作算 子从父代身上产生后代。操作算子大致模仿了生物遗传的过程，但它们只是非 常粗略的将自然进化中最重要的部分抽象出来。最常用的操作算子是变异算子， 变异算子随机地在染色体某一区段进行局部突变；还有交叉算子，它会结合两 个父代的遗传物质生成新的后代。还有很多其他的操作算子，如反演，易位， 隔离，复制等，但它们出现在遗传算法中的情况并不多见。在对所有个体使用 这些操作算子后，遗传算法会将当前种群中，适宜值较低的个体，用后代所替 代。随着父代的适宜度越来越高，繁衍产生的后代个体适宜度也会相应增加， 整个种群的适宜度逐渐提高，从而达到了进化算法的优化目的。 模拟退火模拟冶金退火工艺过程，可以用来求解大规模组合优化问题。该 算法首先由 Metroplis 等31在 1953 年提出。在 1983 年被 Kirkaptrick 等32进一 步扩展延伸。模拟退火算法是一种特殊的爬山搜索算法。爬山算法的思想是一 个登山者从当前地点开始，和周围的地点进行高度的比较，如果当前地点的高 度是最大的，那么返回当前地点，作为最高点，反之就就用最高的邻居地点来 替换当前节点，从而实现向高处攀爬的目的。模拟退火是玛尔柯夫连蒙特卡洛 方法。也就是说，从一个地点跳到的概率另一个只取决于最后一点，而不是基 于以前整个的搜索记录。在模拟退火算法中中，选择初始设计状态，并计算适 宜度函数的值作为该状态的评估。通过操作算子产生一个新的状态，再对这个 新的状态进行适宜度的评估。若该状态的适宜度值超过了当前状态，则新状态 被认可，成为当前的最好状态。如果这一步的操作产生了一个较差的状态，该 状态仍然可以以玻尔兹曼概率被接受。 模拟退火算法在电路布局设计中取得了巨大成功，一些在机械部件布局领 域的重要工作，也在电路布局设计的成功激励下，取得了显著的成果。将模拟 退火算法的性能与其他布局方法相比较，以经典问题为测试算例，结果显示出 模拟退火算法都能产生质量相等或质量更好的解。并且初始状态的设定并不会 对模拟退火算法的效率造成太大改变。Szykman 和 Cagan15将技术从 2D VLSI 8 扩展到 3D 机械机电布局。他们的方法可以处理块状和圆柱体状的部件，而且 可以将这些部件进行 90 度倍数的旋转。此算法中包含一种基于扰动的方法，即 允许组件重叠和违反约束，但同时会对这种违规状态进行惩罚。Szykman 等38 介绍了一种适用于三维布局和布线的综合模拟退火算法，实验表明并发布局和 布线的方法比传统方法中，先布局再布线的方式取得的结果更好。布线问题经 常出现在工程应用方面，例如管道，电线和风道的布线。在布局部件阶段同时 考虑路由成本问题，可以显著提高布局质量和降低布局的成本。Rao 和 Iyengar39将模拟退火算法运用到各种规则物体的装箱问题。经过一系列的模拟 实验表明，通过模拟退火算法获得的解方案的质量比其他大部分的同类启发式 算法获得的解方案的质量均略高一筹。Han 和 Na40提出了一个嵌套方法，分为 两个阶段：初始布局阶段和改进布局阶段。先通过 packing 算法生成一个可以 接受的初始方案，然后利用模拟退火算法用于改善初始方案。这种两阶段的求 解方法，后来被广泛应用在 Packing 问题中。已经有很多实验证明了，模拟退 火算法能够成功解决规则待布物的 Packing 问题。但是，对于不同的应用场合， 模拟退火算法的效率和作用很大程度由解空间的大小，实施策略和目标函数共 同决定。 蚁群算法是新兴的进化算法，该算法的来源是真正的蚁群。 更具体地说， 蚁群优化算法的灵感来源于蚂蚁的觅食行为。这个行为的核心是蚂蚁们通过化 学信息素的踪迹，间接地进行沟通，这使它们能够找到它们的巢穴和食物来源 之间的最短路径。根据某些观点，蚁群算法可能属于不同类别的近似算法。从 人工智能的角度来看，蚁群算法是最出色的一种群体智能算法16,17。 一些版本的蚁群算法已经运用到 packing 问题。Levin 和 Ducatelle46第一次 将蚁群算法的应用到一维 Bin-Packing 问题中（1-BPP） 。作者使用蚁群算法根据 待布物的长度，来搜索哪些待布物适合被组合在一起。据他们报告，蚁群算法 胜过其他元启发式算法，比如遗传算法。Brugger 等47也针对 1-BPP 问题提出 了一种蚁群算法，并且在基准问题的测试上，他们的蚁群算法表现出来的性能 也超过了46。Thiruvady48等提出了一种解决二维 Packing 问题的蚁群算法， 他们的算法中是包含了一种下台阶式的构造性启发式，并且用蚁群算法来优化 Packing 序列。Burke 和 Kendall49将蚂蚁系统应用到二维不规则形状 Packing 问 题中，他们使用“临界多边形”作为构造性的启发式，同样蚁群算法也被用来优 化 Packing 序列。 9 1.3 课题研究的内容和意义 由于三维 Packing 问题的 NP 难性质，至今仍未有一种十分可靠的算法能求 解出多面体 Packing 问题的最优解。不仅因为三维中，物体任何的移动和旋转 都会改变系统内的平衡状态，而且在三维的几何问题中，大量浮点数的计算增 大了求解问题的复杂度。许多来自不同领域的学者与专家都在研究更精确且快 速的求解三维多面体 Packing 问题的可行算法。本文旨在提出计算精准且高效 的启发式 Packing 算法来解决三维 Packing 问题，本文的研究内容如下： （1）总结国内外针对三维 Packing 问题已有的理论知识和相关思路，分析以 往提出的算法中存在的漏洞，找到突破口并加以改进。 （2）力求摆脱三维 Packing 算法中必须计算临界多面体的限制，改变以往的 启发式算法不允许待布物体之间产生任何干涉的情况，提出了一种新的可接受 待布物暂时发生干涉的启发式思路，并且适用于各种形状的多面体 Packing 问 题。 （3）进一步分析了三维多面体 Packing 问题的数学模型，并根据最小势能原 理，重新定义求解公式，提高了待布物体之间的紧密程度。 （4）基本的蚁群算法容易受困于局部最优，而且随着问题规模的增大，搜索 速度也会有所下降，所以本文对蚁群算法进行了分析，并设计了基于动态信息 素更新策略的蚁群算法。 意义：三维多面体 Packing 问题在实际生活有着巨大的应用空间，尤其是 在工业领域。本文以集装箱装载问题为背景，在前人的研究基础上，进一步改 进现有算法，提高对三维多面体 Packing 问题求解的质量与效率，这不仅对节 省工业成本存在十分大效益，而且可以增加对材料的使用率，避免产生过多的 废弃能源，这对保护生态环境有着积极的影响。 1.4 研究的基础 在以往的三维多面体 Packing 问题研究中，为了计算出待排放多面体可能 的放置位置，都要先计算临界多面体，并且每当多面体进行旋转时，都要重新 计算一次临界多面体，这在计算时间上占用了很大的开销。而 Xiao LIU 和 Jia- min LIU 14基于最小势能原理，提出了一种更高效可行的新的构造性算法 HAPE3D。该算法最大的优势是不用计算临界多面体(NFP)，而且适用于任意形 状的有洞或无洞多面体 packing 问题，并且每个多面体都可以绕任意坐标轴旋 转不同的角度来改变放置方向。 虽然 HAPE3D 本身已经在解决三维 packing 问题上有很好的效果，但也有 10 必要混合启发式算法来搜索更好的解。许多基于 Szykman 和 Cagan15、Cagan 等16提出的模拟退火算法的优化方法被广泛应用到解决三维 packing 问题中。 原文中作者选择使用模拟退火算法与 HAPE3D 算法混合，以此来优化 Packing 序列。 HAPE3D+SA 混合算法解决了以往三维 Packing 问题算法的痛点，并有着 不错的排样效率，但经过本文研究发现，不仅是在 HAPE3D 算法中对容器空间 的利用程度上，还是在启发式算法对解空间的搜索过程上，都有可以改进的不 足之处。所以本文提出了 IHAPE3D 算法(Improved-HAPE3D)，并且与蚁群算法 (ACA)相混合，经实验证明 IHAPE3D+ACA 混合算法比原文的 HAPE3D+SA 混 合算法有着更好的排样效率。 1.5 论文的组织 本文针对三维多面体 Packing 问题进行研究。本文中围绕此主题的研究背 景、研究重点、研究内容展开讨论，并给出一种新的混合启发式算法。本文将 具体研究分成了三个部分进行详细阐述，论文结构组织如下： 第 1 章 绪论 本章描述了三维 Packing 问题的课题背景及其研究意义，并描述了前人针 对多面体 Packing 问题的研究成果，概略地介绍了本文的主要研究内容以及论 文的组织结构。 第 2 章 基于最小势能原理的多面体 Packing 方法 介绍一种新的构造性 HAPE3D 算法的思路，并继续依据最小势能原理，对 该算法进行进一步完善。并通过引入新的 Packing 规则，使多面体之间能排列 得更加紧密。经实验证明，通过改进后的算法计算得出的 Packing 方案比原算 法得出的方案具有更高的空间利用率。 第 3 章 求解三维 Packing 问题的动态启发式蚁群算法 本章简单介绍了利用蚁群算法优化 Packing 序列的思想，并分析蚁群算法 中存在的不足之处，根据具体需求在蚁群算法中加入动态因素。克服了蚁群算 法容易趋向早熟收敛的缺点，经实验表明，加入了动态因素的蚁群算法的工作 效率明显提升。 总结与展望 11 第 2 章 基于最小势能原理的多面体 Packing 方法 2.1 问题的提出 三维 Packing 优化问题出现在粉末冶金学(3D 激光切割)、各种运输工具的 空间舱布局、钻石切割等很多工业领域的分支当中。关于此问题的研究，大部 分都围绕在将大小不一的平行六面体装入容器中,比如17,18,19，只有极少数的 研究与将多面体装填入三维空间中的容器有关。 在 20,21,22中提到了一种利用遗传算法解决三维多面体 Packing 问题的思 路，它利用以下三个信息: 待布物的移动的方向、放置方向和待布物的切点。 待布物可以绕每支坐标轴进行不同角度的旋转(每个角度必须为 45的倍数)。 研究中的目标函数值为装入容器内多面体的个数，或者是每个多面体的包络平 行六面体的中心与容器中心之间的距离总和。 而在23,24,25中提出了几种采用模拟退火算法解决三维 Packing 问题的思 路。这些方法可以适用于平行六面体和圆柱体，而且待布物可以绕每支坐标轴 进行不同角度的旋转(每个角度必须为 90的倍数)，在之后的26中，同样的方 法被用来布局不规则待布物体。 在23,26中每个待布物按照一定的顺序依次排放入容器内，而且不受旋转 方向上的限制，并使用模拟退火算法优化目标函数值。 本章提出了一种基于最小势能原理的三维 Packing 算法，该算法不仅适用 于各种形状、有洞或无洞的多面体待布物，而且多面体可以进行多种放置方向 上的改变。 2.2 问题的数学模型 令 Pi (i = 1,2,.,n) 为 n 个给定的多面体待布物，P 为三维空间中给定的一 个长方体容器， P = (x , y , z) R3: 0xl, 0xw, 0xh (2.1) 其中，容器 P 的长度 l 与宽度 w 都为常量，但高度 h 为变量。 多面体 Pi由组成它的各个顶点表示 vik = (xik, yik, zik), k =1,.,ni，ni为 Pi的 顶点个数。 12 Pi = v R3: v = ，k = 1,.,ni (2.2) = 1 设 ui和 ri分别为 Pi的位置向量和旋转向量， ui = (xi, yi, zi)，ri = (ai, bi, ci, wi) , i = 1,.,n (2.3) 当多面体 Pi以 si = (ui , ri) 为放置状态， Pi (si) = v R3: v = (ui + )ri , Pi , i = 1,.,n (2.4) 问题可表述为为每个多面体 Pi找到适合的放置状态 si，使每个多面体都能 放置在容器 P 内，而且使容器 P 被占用的部分的高度 h 最小。 2.3 IHAPE3D 构造性算法 Xiao LIU和Jia-min LIU14基于最小势能原理，提出了一种关于三维Packing 问题的构造性算法HAPE3D。该算法最大的优势是不用计算临界多面体，而 且适用于任意形状的有洞或无洞多面体Packing问题，并且每个多面体都可以绕 任意坐标轴旋转不同的角度来改变放置方向。本文基于该算法，提出了改进后 的IHAPE3D算法(Improved-HAPE3D)。 2.3.1 最低势能原理 最低势能原理指的是一个物体或者结构都会向系统中势能最小的位置进行 变换或者运动。一个物体的总势能()为此物体中存储的弹性势能(U)和作用在 此物体上的外力所产生的的势能(V)的总和，以上表述可以由式(2.5)表示： = U + V (2.5) 本研究中的多面体都是无弹性物体，因此物体中存储的弹性势能为0，所以 式(2.5)可简化为： = V = Gz (2.6) 其中G是重力，z则是多面体重心的z坐标。 根据最低势能原理当一个体系的势能处于最低时，该体系会达到一种稳固 均衡的形态，基于式(2.6)，多面体总是会选择向重心更低的位置移动，所以在 旧的HAPE3D算法中，只选择使多面体重心z坐标越小的可放置点作为多面体的 最佳放置位置。 但在具体的装填问题中，为了缩小多面体之间的间隙，并使多面体放置的 更加紧凑，为待放置的多面体留出更多完整的可利用的空间，我们可以假设多 面体在基于式(2.6)找到最佳放置位置后，继续受到z坐标轴反方向上重力的影响， 13 并且同时也受到来自x坐标轴反方向与y坐标轴反方向上的吸引力的影响，据此 可以将式(2.6)扩展为, = V = Gz + Fx + Fy (2.7) 其中F是吸引力, x为多面体重心在x轴上坐标，y为多面体重心在y轴上坐标， 我们将原点设成零势能点，根据势能最低