本文選題：三維布局　切入點(diǎn)：多面體布局　出處：《湘潭大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：裝箱問(wèn)題(Container Loading Problem,CLP)在物流、多處理器調(diào)度、資源分配和包裝等方面有著廣泛的應(yīng)用。本文研究多面體的裝箱問(wèn)題,該問(wèn)題可描述為將若干不同形狀的多面體放入固定矩形底的集裝箱容器內(nèi),要求箱體高度盡可能小。從本質(zhì)上看,集裝箱裝載問(wèn)題為NP難問(wèn)題。由于解空間為高維實(shí)數(shù)空間,且多面體的不相交判斷計(jì)算量相當(dāng)巨大,比其它Packing問(wèn)題更難求解,甚至于一般的串行計(jì)算機(jī)無(wú)法在多項(xiàng)式時(shí)間內(nèi)找到可行解。到目前為止,啟發(fā)式、演化算法是解決這類組合優(yōu)化問(wèn)題的有效方法。但解決本文問(wèn)題相關(guān)文獻(xiàn)比較少,求解精度和計(jì)算效率仍然有待提高,且都具有一定的局限性,如限制物體形狀和物體放置方向,需要計(jì)算臨界多面體等。本文在湖南省自然科學(xué)基金(項(xiàng)目:三維靜動(dòng)態(tài)平衡約束多形狀布局問(wèn)題的全局協(xié)同優(yōu)化機(jī)理與方法研究,編號(hào):2017JJ2250)的資助下,展開對(duì)該問(wèn)題的研究,主要工作和創(chuàng)新描述如下:1、本文提出了一種改進(jìn)的HAPE3D(IHAPE3D)算法。(1)在重力勢(shì)能的基礎(chǔ)上,引入了另外兩個(gè)方向的引力勢(shì)能,進(jìn)而基于最小勢(shì)能原理重新定義了系統(tǒng)的勢(shì)能表達(dá)式;(2)利用“平面分離定理”進(jìn)行多面體干涉判斷,采用GPU多線程并行計(jì)算物體的最優(yōu)放置狀態(tài),減少計(jì)算時(shí)間。實(shí)驗(yàn)結(jié)果表明:提出的方法提升了容器的空間利用率、減少了求解時(shí)間。2、本文提出一種多面體Packing問(wèn)題的并行啟發(fā)式蟻群算法。設(shè)計(jì)蟻群算法的動(dòng)態(tài)信息素自適應(yīng)更新規(guī)則,能避免蟻群迭代陷入于局部最優(yōu)和提高大規(guī)模問(wèn)題的搜索速度,GPU多線程計(jì)算提高了求解效率。通過(guò)實(shí)驗(yàn)對(duì)比,表明IHAPE3D算法與蟻群算法結(jié)合可以有效優(yōu)化多面體裝填順序,相比已有的實(shí)驗(yàn)成果,進(jìn)一步的提升了容器的空間利用率。本文以集裝箱裝載問(wèn)題為背景,深入探究了三維空間中多面體Packing問(wèn)題。首先提出了一種基于最小勢(shì)能原理的Packing啟發(fā)式算法,可以根據(jù)給定條件高效地計(jì)算出Packing方案,再針對(duì)具體問(wèn)題,混合了動(dòng)態(tài)蟻群算法以進(jìn)行優(yōu)化,比較高效地解決了三維中多面體的Packing問(wèn)題。希望本文能作為三維多面體Packing問(wèn)題求解的階段性成果,將來(lái)為更多類似的布局問(wèn)題研究提供思路和參考。
[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.
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前5條

1 Xiao LIU;Jia-min LIU;An-xi CAO;Zhuang-le YAO;;HAPE3D—a new constructive algorithm for the 3D irregular packing problem[J];Frontiers of Information Technology & Electronic Engineering;2015年05期

2 張衛(wèi)紅;高瑜;方亮;陳裕澤;;三維組件布局建模與優(yōu)化設(shè)計(jì)[J];航空學(xué)報(bào);2008年06期

3 薛迎春;須文波;孫俊;;基于遺傳模擬退火混合算法的矩形包絡(luò)求解[J];計(jì)算機(jī)工程與設(shè)計(jì);2007年22期

4 ;Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle[J];Journal of Zhejiang University Science A(Science in Engineering);2006年04期

5 黃宜軍,施德恒,許啟富;鈑金CAD中一個(gè)較優(yōu)的排料算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2000年05期

，

本文編號(hào)：1573774