【毕业学位论文】（Word原稿）矩形装箱问题的协同决策模型

目 录 矩形装箱问题的协同决策模型 .未定义书签。 中文摘要 .未定义书签。 .未定义书签。 目 录 . 1 图目录 . 4 第一章 绪论 . 1 究背景 .题的提出 .究意义 .究现状 .章结构 .二章 矩形洞 . 9 义及表示 .号约定 . 10 空四元组 . 10 行四元组 . 11 大四元组 . 11 于 . 11 含 . 11 点 . 12 界点 . 12 集 . 12 集 . 13 集 . 13 置关系 . 13 同 . 14 含 . 14 邻 . 16 离 . 18 交 . 20 结 . 21 关定理 . 21 本运算及其实现 . 24 R ） . 24 R ， r ） . 25 R ， r ） . 25 R，2R） . 28 结 . 30 第三章 矩形装箱问题容器格局 . 32 则描述 . 32 示方式 . 34 关定理 . 35 本运算及其实现 . 36 C， r ） . 37 C， r ） . 37 C， r ） . 38 C， R ） . 38 C， r ） . 39 C， r ） . 40 行策略 . 41 态模式 . 41 态模式 . 42 结 . 44 据大小 . 44 结 . 44 第四章 基于矩形洞的算法实现 . 45 排放算法 . 45 法 . 47 法 . 48 法 . 49 结 . 50 层排放算法 . 51 法 . 53 法 . 54 法 . 55 结 . 57 面排放算法 . 57 法 . 58 F（ 法 . 60 法 . 64 结 . 68 结 . 68 第五章 协同决策模型 . 69 题定义 . 69 型结构 . 70 器格局 . 71 价标准 . 71 度变化量 . 72 局变化量 . 72 间浪费量 . 73 配变化量 . 74 结 . 75 策模式 . 76 同类型的装箱算法之间的决策 . 77 同类型的装箱算法之间的决策 . 81 结 . 83 杂度分析 . 84 结 . 85 第六章 实验与分析 . 86 器格局规模 . 86 放高度 . 89 结 . 92 第七章 结论与展 望 . 94 文工作总结 . 94 续工作展望 . 95 参考文献 . 96 在学期间的研究成果 . 103 致 谢 . 104 图目录 图 1箱问题的早期应用 . 1 图 1箱问题的现代应用 . 2 图 1于 优化下料模型 . 2 图 1口直角容器矩形装箱问题实例 . 3 图 1解图 1示问题的 法示例 . 4 图 1 及 法的比较 . 5 图 1 1实例的一个最优 解 . 5 图 2形洞示例 . 9 图 2形块的集合表示 . 9 图 2形洞的四元组表示 . 10 图 2形洞 R 与待放矩形块 r 的四元组解释 . 10 图 2行四元组之间的位置关系：内含 . 14 图 2行四元组之间的位置关系：边内含 . 15 图 2行四元组之间的位置关系：角内含 . 16 图 2行四元组之间的位置关系：相邻 . 17 图 2行四元组之间的位置关系：相离 . 19 图 2行四元组之间的位置关系：相交 . 21 图 2元组 r 与 R 在 时的位置关系 . 26 图 2交可行四元组之间的位置关系 . 28 图 2行四元组的合并 . 29 图 3角容器矩形装箱问题示例 . 32 图 3角容器中的空白部分示例 . 33 图 3两矩形块同时相邻的矩形洞个数示例 . 36 图 3同装箱算法的静态工作区域 . 41 图 3同算法的动态工作区域 . 42 图 4排放装箱算法示例 . 45 图 4层排放算法示例 . 51 图 4面排放算法示例 . 57 图 4 区别 . 58 图 4略示例 . 61 图 4F 策略中左对齐放置对空间造成的浪费 . 62 图 4F 策略中右对齐放置时对空间造成的浪费 . 62 图 4略下的可行点 . 64 图 4略下的不能放置任何待放矩形块的可行点 . 65 图 4意图 . 66 图 5形装箱问题协同决策模型 . 70 图 5箱算法之间的共同决策模型 . 76 图 5箱算法之间的并行决策 . 77 图 5面算法之间的决策 . 80 图 5排放算法与平面算法之间的决策示例 . 82 图 5层排放算法与平面算法之间的决策示例 . 83 图 6A 求解 时的容器格局的规模 . 87 图 6-2 1,2,3j ）协同求解 时的容器格局规模 . 87 图 6-3 13 ）协同 求解 时的容器格局规模 . 88 图 6A 求解 时的排放高度 . 89 图 6-5 1,2,3j ）协同求解 时的排放高度 . 90 图 6-6 13 ）协同求解 时的排放高度 . 91 图 6类型装箱算法与不同类型装箱算法决策效果比较 . 92 图 6间排放场景个数对求解结果的影响 . 93 兰州大学博士学位论文 矩形装箱问题的协同决策模型 1 第一章 绪论 究背景 装箱问题（ 有悠久的 历史 。早在一千年前，它就以骆驼、马、驴子等家畜驮运货物（如 图 1a）所示），抑或马车运货（如 图 1 1b）所示）的形式呈现 在现实生活中 了 。这类早期的装箱问题 大 都局限于较小的规模， 排放者一般可以依照自己的经验或者直觉找到一个足够好、甚至是最优的排放方案。 （ a） （ b） 图 1箱问题的早期应用 虽然 于 1939 年就从线性规划的数学角度 给出了一维装箱问题的求解思路，但是这并不能给早期的排放者带来太大 的实惠。 因为 这些出身于农民抑或工人的 排放者 并不擅于求解抽象的数学问题。 他们 更喜欢具体的、实实在在的、逐步完成的排放方案。通过世代的积累与沉淀， 人们总结出了一系列的经典排放策略 ，如“ 金角银边草肚皮 ，价值最高钻石穴 ” 2、“物以类聚” 3、 、 、 ， 以及 等等。 随着现代工业与运输的发展，装箱问题广泛应用于机械工程、航空航天、造船、钣金、制衣、玻璃切割、出版印刷 6、交通运输、大规模集成电路设计 7, 8、城市规划和建筑设计等诸多行业 9, 10。与早期的应用不同，这些应用中的装箱问题往往都具有较大的规模 7, 11如 图 1示）。传统的个人经验与直觉式的求解模式面临极大的挑战。 装箱问题是 14随着规模的增大，寻求该问题最优解的时间将以指数速度增加。从实用性角度来看，最优解算法 18适用于规模较小的装箱实例；而在规模较大时，启发式算法 25往成为 最佳 选择。 兰州大学博士学位论文 矩形装箱问题的协同决策模型 2 与最优解算法不同，启发式算法虽然并不能保证最优解的获取，但是却能在较短的时间内寻找到“较好”的可行解 29, 39这里所谓的“较好”是相对于大量测试实例而言的。从统计意义上来说，这足以说明一个算法的优 越性；但是 就具体 的装箱问题来说 ，这样的结果可能有明显的缺憾。 （ a） （ b） 图 1箱问题的现代应用 为了避免这种缺憾的产生，阎春平 教授 于 2001 提出了基于 二维优化下料方法 43。 如 图 1示 ， 这种方式虽然说能够在不增加优化时间的前提下获取比单一软件更好的结果，但是由于缺乏优 化软件间的互动而无法 组合各个优化软件的优势 ， 进而 获取优于所有参与优化的单一软件所得最好结果的结果 。 因而我们需要寻求一种能够实现不同装箱算法之间互动的 求解 模型。 下 料 数 据前 处 理 前 处 理 前 处 理优 化 软 件 1 优 化 软 件 2 优 化 软 件 理 后 处 理 后 处 理结 果 评 判优 化 结 果 图 1于 优化下料模型 兰州大学博士学位论文 矩形装箱问题的协同决策模型 3 题的提出 古语有云：“尺有所短，寸有所长，物有所不足。”装箱算法也不例外。从统计学角度来看，现存的每一个装箱算法都是比较优秀的，但是 就 具体的装箱实例而言 ，任何一个装箱算法都有表现不佳的时候。也就是说，任何一个装箱 算法都不是十全十美的，它都有一定的优点，也 有一定的不足。为了使 每一个装箱实例都有最好的排放效果，我们需要各个不同的装箱算法之间的 协同决策 。 为了便于描述，本文只考虑矩形装箱问题。通常来说，矩形装箱问题又可以分为直角容器矩形装箱问题 44 敞口直角容器矩形装箱问题 49 敞开相邻两边的直角容器矩形装箱问题 53 严格来说，在允许容器的高 度 或者宽度为 时，这三类矩形装箱问题可以相互转化，因而本文仅仅以 例来介绍如何实现装箱算法之间的 协同决策 。 究意义 112233554466待 放 矩 形 块待 放 矩 形 块敞 口 直 角 容 器敞 口 直 角 容 器图 1口直角容器矩形装箱问题实例 1980 年证明了 （ 法的近似率为 1710； 1983 年指出 （ 法一般都会优于 且其近似率不超过 3。 这两个算法都是十分优秀的，但是 在求解 图 1 矩形装箱问题的协同决策模型 4 所示的实例时， 它们 却有明显的不足。 如 图 1示，这两个算法都有 明显 的空间浪费情况： 法造成了 下部空间 的浪费，而 法 则 造成了上部空间的浪费；而且 造成空间浪费的罪魁祸首就是矩形块 4。此外 浪费空间 出现 的位置 与 矩形块 4 的 排放次序 和 排放 策略有直接的关系 。 F F D F D 123546图 1解 图 1示问题的 法示例 从优势互补的角度来考虑， 法能够有效消除瘦长矩形块 4 对排放结果的影响，却不能有效避免下部空间的浪费； 而 法 能 够有效 避免下部空间的浪费，却不能 消除 瘦长矩形块 4 对上部空间的浪费。 这足以说明 但是如何才能将这两个算法有机地结合起来 ，以充分发挥各自的长处而避免相应的缺陷 呢？ 一个简单的方法就是 采用 排放次序、 法的排放策略 ，这称为 法。 图 1明 法 能够 比较 完美地避免瘦长矩形块 4 对空间造成的浪费， 但是 这并不能说明 法 的优越性。 因为这仅仅是一个实例的比较，而非统计意义上的 分 析 。 如 图 1示 ， 及 法 虽然 都没有明显的空间浪费，但是 法 却 有更高的空间利用率 。 之所以出现如此尴尬的境地，是因为 法不能很好地解决矮宽型矩形块 3 的排放。 值得注意的是， 优先解决矮宽型矩形块正是 法的 精华所在 。这说明， 单纯地 将两个算法结合起来 并不一定能取得较好的排放方案。 兰州大学博士学位论文 矩形装箱问题的协同决策模型 5 从最优解的角度来看， 法就是 图 1示问题的一个最优解 算法 。 事实上，该最优解方案还可以看成是 依次运行 法三次、 法一次的结果。 对于 图 1的实例来说， 它的一个最优解方案可以通过依次运行 法两次、 法三次 得来 ，如 图 1示 。 F F D H B F D 及 法的比较 123546图 1 1实例的一个最优解 以上分析说明，不同的装箱算法可以通过某种特定的沟通与交流达到更优的排放 结果。 这正应了一句古话， “人多力量大” 。 亦即， 装箱 算法之间通过某种合作可以获取更优的 排放 结果 。 兰州大学博士学位论文 矩形装箱问题的协同决策模型 6 究现状 装箱问题具有悠久的历史。起初，受到生产力发展的限制，装箱实例往往规模较小。排放者完全可以根据自身的生活经历找到一个比较满意、甚至是最优的排放 方案 1859, 60