多面体Packing问题的并行启发式蚁群算法研究

发布时间：2018-03-06 06:53

本文选题：三维布局　切入点：多面体布局　出处：《湘潭大学》2017年硕士论文　论文类型：学位论文

【摘要】：装箱问题(Container Loading Problem,CLP)在物流、多处理器调度、资源分配和包装等方面有着广泛的应用。本文研究多面体的装箱问题,该问题可描述为将若干不同形状的多面体放入固定矩形底的集装箱容器内,要求箱体高度尽可能小。从本质上看,集装箱装载问题为NP难问题。由于解空间为高维实数空间,且多面体的不相交判断计算量相当巨大,比其它Packing问题更难求解,甚至于一般的串行计算机无法在多项式时间内找到可行解。到目前为止,启发式、演化算法是解决这类组合优化问题的有效方法。但解决本文问题相关文献比较少,求解精度和计算效率仍然有待提高,且都具有一定的局限性,如限制物体形状和物体放置方向,需要计算临界多面体等。本文在湖南省自然科学基金(项目:三维静动态平衡约束多形状布局问题的全局协同优化机理与方法研究,编号:2017JJ2250)的资助下,展开对该问题的研究,主要工作和创新描述如下:1、本文提出了一种改进的HAPE3D(IHAPE3D)算法。(1)在重力势能的基础上,引入了另外两个方向的引力势能,进而基于最小势能原理重新定义了系统的势能表达式;(2)利用“平面分离定理”进行多面体干涉判断,采用GPU多线程并行计算物体的最优放置状态,减少计算时间。实验结果表明:提出的方法提升了容器的空间利用率、减少了求解时间。2、本文提出一种多面体Packing问题的并行启发式蚁群算法。设计蚁群算法的动态信息素自适应更新规则,能避免蚁群迭代陷入于局部最优和提高大规模问题的搜索速度,GPU多线程计算提高了求解效率。通过实验对比,表明IHAPE3D算法与蚁群算法结合可以有效优化多面体装填顺序,相比已有的实验成果,进一步的提升了容器的空间利用率。本文以集装箱装载问题为背景,深入探究了三维空间中多面体Packing问题。首先提出了一种基于最小势能原理的Packing启发式算法,可以根据给定条件高效地计算出Packing方案,再针对具体问题,混合了动态蚁群算法以进行优化,比较高效地解决了三维中多面体的Packing问题。希望本文能作为三维多面体Packing问题求解的阶段性成果,将来为更多类似的布局问题研究提供思路和参考。
[Abstract]:Container Loading problem has been widely used in logistics, multiprocessor scheduling, resource allocation and packaging. This problem can be described as putting several polyhedrons of different shapes into container containers with fixed rectangular bottoms and requiring that the height of containers be as small as possible. In essence, the container loading problem is NP-hard. Because the solution space is a high-dimensional real number space, Moreover, the computation of disjoint judgment of polyhedron is very large, which is more difficult to solve than other Packing problems. Even ordinary serial computers can not find feasible solutions in polynomial time. Evolutionary algorithm is an effective method to solve this kind of combinatorial optimization problem. However, there are few related documents to solve the problem in this paper, and the accuracy and efficiency of solving the problem still need to be improved, and all of them have some limitations. For example, it is necessary to calculate the critical polyhedron in order to limit the shape and orientation of objects. In this paper, the mechanism and method of global cooperative optimization for three-dimensional static and dynamic equilibrium constrained multi-shape layout problems are studied in Hunan Provincial Natural Science Foundation. The main work and innovation description are as follows: 1. This paper presents an improved HAPE3D / IHAPE3D algorithm. Based on the gravitational potential energy, two other directions of gravitational potential energy are introduced. Then, based on the principle of minimum potential energy, the potential energy expression of the system is redefined. "plane separation theorem" is used to judge the interference of polyhedron, and GPU multithreading is used to calculate the optimal placement state of the object. The experimental results show that the proposed method can improve the space utilization rate of the container. In this paper, a parallel heuristic ant colony algorithm for polyhedron Packing problem is proposed. The dynamic pheromone updating rules of ant colony algorithm are designed. It can avoid ant colony iteration falling into local optimum and improve the search speed of large scale problem. The results of experiment show that IHAPE3D algorithm combined with ant colony algorithm can effectively optimize the loading sequence of polyhedron. Compared with the existing experimental results, the space utilization rate of the container is further improved. This paper takes the container loading problem as the background. In this paper, the problem of polyhedron Packing in three dimensional space is deeply explored. Firstly, a Packing heuristic algorithm based on the principle of minimum potential energy is proposed, which can efficiently calculate the Packing scheme according to the given conditions, and then aim at specific problems. The dynamic ant colony algorithm is mixed to solve the Packing problem of three dimensional polyhedron efficiently. It is hoped that this paper can be used as the stage achievement of solving the three dimensional polyhedron Packing problem. In the future for more similar layout problems to provide ideas and references.
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】