1、I 学校代码 学 号 分 类 号 密 级 硕 士 学 位 论 文 多面体 Packing 问题 的 并行 启发式蚁群 算法研究 学 位 申 请 人 指 导 教 师 学 院 名 称 信息工程学院 学 科 专 业 软件工程 研 究 方 向 软件开发 与 项目管理 年 月 日II 摘要 装箱 问题 (Container Loading Problem, CLP) 在 物流、 多处理器调度、资源分配和 包装 等 方面 有着广泛的应用 。 本文研究多面体的 装箱 问题， 该问题可描述为 将 若干不同形状 的 多面体 放 入 固定 矩形底 的 集装箱 容器内 ， 要求箱 体 高 度 尽可能 小 。 从 本
2、质上看 ，集装箱装载 问题 为 NP 难 问题 。 由于解空间为高维实数空间，且 多面体的不相交判断计算量相当巨大， 比其它 Packing 问题更难求解，甚至于一般 的 串行计算机 无法 在 多项 式 时间内 找到可行 解 。 到目前为止， 启发 式 、演化算法 是 解决这类 组合 优化 问题 的 有效方法。但解决本文 问题相关 文献 比较少 ， 求解精度和计算效率仍然有待提高， 且都 具 有 一定的局限性 ， 如 限制 物体 形状 和 物体放置方向 ， 需要 计算 临界多面体 等 。 本文 在湖南省 自然科学基金 项目 “ 三维静动态平衡约束多形状布局问题的全局协同优化机理与方法研究 ”
3、的资助下，展开对该问题的研究， 主要工作 和 创新描述如下： 1、 本 文 提出了 一种 新的 IHAPE3D (Improved-HAPE3D)算法 。 （ 1） 在重力势能的基础上，引入了另外两个方向的 引力势能 ， 进而 基于 最 小势能原理 重新定义了系统的势能表达式； (2) 利用 “平面分离定理” 进行 多面体干涉判断 ，采用GPU 多 线程并行计算 物体的最优放置状态，减少计算时间 。 实验结果表明：提出的方法 提升了 容器 的 空间利用率 、 减少了 求解时间。 2、 本 文 提出一种 多面体 Packing 问题的启发式蚁群算法 。设计 蚁群算法 的动态信息素 自适应 更新
4、规则， 能避免 蚁群 迭代陷入 于 局部最优 和 提高 大 规模 问题的 搜索 速度 。 通过 实验对比， 表明改进 后 的 IHAPE3D 算法 与蚁群算法结合 可以有效 优化多面体 装填 顺序， 相比 已有 的实验成果 ， 进一步 的 提升了 容器 的 空间利用率。 本文 以 现 实生活中 的 集装箱 装载 问题为背景 ， 深入 探究了三维空间中 多面体Packing 问题。 首先 提出 了一种基于最小势能原理 的 Packing 启发式算法 ，可以根据 给定条件高效 地 计算出 Packing 方案， 再 针对具体问题， 混合 了 动态 蚁群算法 以 进行优化， 比较 高效 地 解决了三
5、维 中 多面体 的 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 o
6、n 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-
7、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
8、 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
9、 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 pr
10、oblem 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, theref
11、ore 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 paral
12、lel, 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 avoidi
13、ng 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. I
14、V 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
15、, 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
16、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 问题的提出
17、 . 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 章 求解三维 PACKI
18、NG 问题的动态启发式蚁群算法 . 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)为研究背景，主要研究三维空间中 ， 多面
19、体的 Packing 问题 。 Packing 问题经常出现 在 工业 领域 中 ，或者属于 其他问题的子问题 。质量高的 Packing 方案 可以显著 的减少 工业中 的运输成本和生产成本 ，甚至 可以减小二氧化碳的排放 ， 因此 Packing 问题数百年来都是使数学界十分感 兴趣 的研究领域。 Packing 问题 可以 大概表述为 将 给定 的 待布物装入 一个或多个容器中 ， 待布物不能超出容器范围之外放置，而且待布物之前不能发生重叠情况 。 待布物和容器可以 是规则 或不规则的形状 (多边形 或多面体 )。 基于 Wscher 等 50提出 的分类 方法 ， 可以根据装载容器和
20、待布物的类型 来对集装箱问题进行分类 。 形状和维数相 同 的 装载容器 (待布物 )可以看作 为 同一类型 ， 如果 在 一个 集装箱 装载 问题中， 装载 容器 (待布物 )可以 按照类型分 组， 而且每个组 中 有一定数量的装载容器 (待布物 )， 则 此 问题属于 弱 异类集装箱 装载 问题 ； 若 没有或 只有少数 几 个 装载容器 (待布物 )属于 同一类型 ，那么 此问题属于 强异类集装箱装载 问题 。 集装箱 装载问题还可以 分为： 1、 提供足够的 装载容器 ，可以 装载所有待布物 ； 2、 没有 足够的装载容器，只能选择待布物的子集进行装载。 这 两类问题的优化 目标 不同
21、有 所区别，第一 种 问题 属于 输入值 (装载 容器 的 个数 )最小化 类 ，第二类问题属于 输出 值 (装载 待布物 的个数 )最大化类 。 Packing 问题 根据空间 维数的不同 通常可以分为一维 Packing 问题 、二维Packing 问题、三维 Packing 问题， 随着 空间 维 数的增加，解决问题的难度 和 计算复杂度也 随之 增大 。 而 集装箱装载问题属于三维 Packing 问题 ， 三维 Packing问题通常存在以下难点： 1、 计算 量繁重 且 复杂， 尤其是 计算物体之间的 重叠 干涉情况时， 要考虑 到点 ， 线 ， 面 各个 方面的干涉情况 。 2、
22、 从 本质上看 ，三维 Packing 问题 为 NP 完全问题 ， 以至于在 普通 的 串行计算机上无法在 多项式 时间 之 内 解决 。 3、 组合优化问题经常 发 生 组合爆炸的 情况 ， 寻满足约束条件的最优解 变得十分困难 。 4、 对 于 Packing 问题 的优化 易进入 局部最优 的陷阱 ， 从而 无法寻找到全局范围内 的最 佳 Packing 方案 。 2 本文以集装箱 装载 问题为 研究背景， 结合图形 学 ，几何学，算法设计 为 理论依据，基于现有 算法 ，提 出 了一种更加 行之有效 的混合启发式 算法， 通过研 究实验对比 ， 该算法 相较 以 往 同类型的算法 ，
23、 在 性能与 效率 上 有明显的 优势。 1.2 三维 多面体 PACKING 问题 1.2.1 三维 多面体 PACKING 问题的描述 将 一组形状不规则的多面体 装入容器内并 最小化 未利用 空间或最大化 空间利用 属于三维 多面体 Packing 问题 中 的组合优化类问题 。此类问题 经常 出现 在现实生活 中 ，比如 集装箱 装载与卫星舱的布局， 设计 Packing 方案是普遍 存在 的一个 关键 环节，一个合理 的 Packing 方案 可以提高空间利用率 ， 减少生产 和运输 成本，从而带来巨大的经济 效应 。从理论上角度来看，三维 多面体 Packing 问题 属于 NP
24、完全 问题 ，确定最优解非常 困难 。 图 1.1 集装箱 装载 问题 图 1.2 卫星舱 布局 问题 1.2.2 三维 多面体 PACKING 问题的约束 类型 在 三维 Packing 问题中存在 着 许多约束， 按照 被 约束 物 的不同 ，区 分为 容器约束和待布物约束 。 这些约束有可能与容器与待布物之间的关系有关，也有可能与 装载 的过程有关。 约束 的强制性分为 硬性和 非硬性，其中硬性约束是一定要被满足的，一个违反了硬性约束的 Packing 方案 被将被 作为 禁止方案，而 一定 限度下违反 非硬性约束，是可以允许并 接受 的。 在 三维 Packing 问题中，常见的约束有
25、以下几种： 1、 重量 约束 (容器约束 )： 大多数 问题中 ，容器只能 装载 有限 重量 的待布物。 少数 情况下 可以 忽略重量约束 的 影响，比如 待布物 的材质为橡胶泡沫类时 。 2、 重量 分布约束 (容器约束 )：在 某些 情况下， 要求 待布物 的重量被 均匀 的 分布在 容器 底的 平面上， 这样能增加装载的稳定性。 3 3、 Packing 优先级约束 (待布物 约束 )： 这类约束经常出现在输出值最大化类装载问题中 ， 因为容器的 装载 量有限 ， 所以通常 要 决定哪些待布物 优先 装载，而哪些 待布物将被舍弃。 在现实场景中 ，优先级 一般根据 运送截止日期、 待布物
26、的 保质期 来 制定 。 4、 旋转 约束 (待布物 约束 )： 为了减小问题的复杂性，通常会限制待布物放置方向上的改变。 5、 堆叠约束 (待布物 约束 )：这类 约束考虑到了待布物的承重问题， 如果 某个待布物上堆叠 的 其他待布物的重量超过了此待布物的承重限度 ， 将会造成 待布物 的 损坏。 6、 分配 约束 (待布物 约束 )：在 某些情况下， 某种 类型的待布物 会 被要求装载在同一个容器内，比如 运输 目的地相同的待布物 ； 而 有些 类型的待布物不允许被装载在同一个容器内，比如食 物 类和 毒性化学物品 类的待布物 通常 不允许装载在一个容器内。 1.2.3 三维 多面体 PA
27、CKING 问题 研究现状 上个世纪 50 年代 末 ，当时 印刷 工业 和 造纸 工业 的 材料利用成本都非常高，因此 Paul1提 出 了用线性规划 的 方法来求解 工业 中长方形 的 Packing 问题 ，这是最早 用来寻找 Packing 问题 的最优解 的 方法 。 当涉及 到不规则的形状 时 ， 研究者 们渐渐开始采用 一些 近似 方法 来 求解Packing 问题 ， 比如 计算 物体的 最小包络矩形 。 Huang 等 2使用枚举 法来 搜索 金属 板块 的最小包络矩形。 Xue 等 3采用 遗传模拟退火混合算法来搜索 非凹多边形的最小包络 矩形 。 Chaudhuri 和
28、Samal4采用最小 二乘法来 决定 物体 长轴与 短轴 的方向 ，以此来获取最小包络矩形 。 但是，最小包络矩形只是一个近似值，所以并不能 充分有效 的利用材料 。 为了 提高解的质量 ，许多 启发式 被应 用到了 Packing 问题中。 启发式算法不依赖理论依据， 完全基于经验提出 。 虽然这种以直观感受以及相关经验为 基础的算法，只有 一定几率 获得全局最优解，但可以 在能够 接受的时间以及空间 范围内，得到一个有效 可行的方案 。 Packing 问题 由于其超复杂性和自身 的 组合 爆炸性质，属于 NP 完全问题 ， 以至于 在 普通 计算机上， 不可能 在 多项式时间内得到 最优
29、解。所以 通常， 一般 用动态规划或者启发式 ，有时候 用两者的结合来求解该类问题。这 些 方法 不能保证 求出最优解， 但 为了保持 较高 的求解效率，必然 要在 解 的质量与 求解时间 之间 的 寻找 一个 最佳 平衡点 ，而 利用该类 算法 可以很好地解决 这个问题 ，因此在求解 Packing 问题 时 ， 动态规划 和 启发式 算法被 应用 得 十分广泛 。 在三维 Packing 问题 研究 中， 大多数 已发表的 文献都 只涉及到 规则形状的 多4 面体，比如 Wu 等 5和 Allen 等 6提出 的立方体 布局 研究， Stoyan 和 Chugay7提出 的圆柱体 布局 研
30、究 , Al-Raoush 和 Alsaleh8提出 的球体布局研究 ， 以及一些特殊的形状比如 Song 等 9提出 的 药片 状 的 微粒 布局 研究 。 Bortfeldt 和 Wscher9统计到 只有 1.8% 的 Packing 问题 领域 的文献涉及到了不规则 的 形状 。 George 和 Robinson27首先 介绍 了一种启发式 思想 将 20种 不同类 型的 盒子装入 集装箱中 。先将 这些 盒子按照一些 关键因素 确定放置 优先级 ， 然后对这些待 布物使用 围墙 法 ，即将 先 装入的盒子 贴 着容器的 某 一个 垂直 内壁 作为 初始 墙面 放置 ，形成一 层 放
31、置层， 再 将 此放置层 作为 墙面 ，形成下一层放置层， 以此 方法 循环 ， 当 所有 的 放置层 铺满容器 底面后， 再 从 余下的盒子中，选择尺寸合适的盒子，填满放置层 内 的空隙 ， 以提高空间的利用率 。 Kovel28开发了一种自动机器人系统 来 帮助邮局将包裹 装填 入 运输箱 内 。 但受限于 包裹 传送带的 物理条件，机器人 每次只能选择 35 个 包裹 。 在每一次循环迭代中， 评估 每一个包裹的可能 放置 方 案 的 优劣，从中选择 最优 方案。 已放置 的包裹 形成一片禁放区域， 即它们的垂直投影。 现实情况中 ，包裹是从上到下进行放置， 在该 算法中 ， 横向 放置
32、取代 了竖向放置， 因为横向 放置可以增加 包裹 堆放的稳定性，也可以为下一次放置 提供 更大的 放置基底 。 然而 ，传送带的 容量 限制会 造成 空间 利用不充分， 包裹 在运输箱 的 四个角落呈现金字塔式的堆叠状态 。 Gehring29等 而是 介绍 了一种 适用于 不同尺寸 盒状 物 的启发式装箱 思路 。 该算法 同样利用围墙 法， 将待装箱货物按体积 从大 到小确定放置优先级， 首先 会将货物 填满 集装箱的底面，再向上循环构造放置层 。 该算 法中不允许 跨层 放置， 只能移动 一整个放置层来 调整重量 分布，所以可能会造成空间利用率 的 减小 。 Loh 和 Nee30同样
33、利用围墙法，不同的是他们 用水平 造墙替代了垂直造墙 。盒状 物 的 高度成了确定放置优先级的唯一依据， 因为这样 能 形成较 平整的放置层 。 在该算法中， 实用 了动态移动 边界 技术来隔离已放置和 未 放置的 区域， 并且用一组结点来标记 盒装 物 之间 高度的差值 。 虽然这种方法一定程度上能改善空间利用率，但实际 情况中， 盒装 货物 的高度很难 形成 大面积的统一， 所以当放置 过程 接近 收尾阶段 时 ，最后几 层 的放置层 几乎 不可能形成 。 计算临界多边形 (no-fit polygon,NFP)法 一直 被 大多数研究者 用 来解决 二维 不规则形状 Packing问题 。 尽管 已经有数百种方 法被 提出 (Bennell等 10; Liu和 He11; Burke 等 12)， 但 NFP 的 计算 依然是 一 个十分 消耗时间的 过程。 以 SWIM 基准问题为例 ， Burke 等 12表明需要花费 1/66 秒 去 计算产生 一个 NFP。 所以在 问题 规模 为 10 个 物体 ， 每个物体有两种放置方向的情况下，只需要 1/66(102)2 = 6.06 s 的总体 执行时间 ，这看起来是一个 可接受的 运行 时间长度 。可 随着问题 规模增大到 50 个 物体，每个物体有 4 种放置 方向 的情况下 ，执行时间会骤 升 到
