【作者】 刘虓；

【导师】 叶家玮；

【作者基本信息】 华南理工大学 ， 船舶与海洋结构物设计制造， 2011， 博士

【摘要】 二维排样问题在许多工业领域均有应用,比如:冲裁件加工、造船、服装、皮革切割等。排样效率的微小提升可为这些行业带来巨大的经济效益。另外排样算法属于一类组合优化问题,具有极高的计算复杂度,国内外学者对此进行了几十年持续不断的研究。二维不规则零件排样问题存在两大瓶颈:临界多边形(NFP)和计算机速度。多数排样算法都是基于NFP的,但其计算时间与零件类型数(N)和转角个数(RN)成平方关系,因此当零件数量很大或旋转角数目很多时,NFP的计算时间将成为一个巨大障碍。另外排样优化算法历来是一个需要多次迭代的耗时算法,排样优化问题为了得到一个较为理想的结果,往往需要几个小时的时间。针对以上问题,本文主要做了如下几个方面的工作。(1)提出了一种基于矢量格式的零件靠接算法,突破了“矢量图形靠接速度慢”的论断。该靠接算法包含两部分内容:多边形分离判据和进退法。多边形分离判据将多边形之间的相对关系归结为点与多边形的包含关系以及直线段之间相交关系。至于进退法,其思路如下:如果零件分离,则进;如果零件重叠,则退;直至靠接误差满足精度要求。本文通过一个算例证明了该算法的高效性。(2)提出了基于最小势能原理的不规则零件排样算法(HAPE),揭示了零件排样问题的物理意义:零件总是试图通过平移和旋转运动尽量降低零件的重心高度,从而得到更加紧密的排列。为了寻找最优排样姿态使零件重心最低,需要在母材上均匀布置一些点,让零件在每个点间隔一定的角度进行旋转。算例表明HAPE是可靠的,且物理意义明确,不需要计算临界多边形,可以处理任意不规则形状零件。(3)将HAPE与爬山算法(HC)和模拟退火算法(SA)结合产生了两种混合排样算法。通过大量测试和对比分析,研究了这两种混合算法的性能,尤其是RN以及PPD (排样点间距)对于排样密度的影响。对混合算法表现出来的“甜蜜”RN现象进行了初步的研究。(4)排样问题并行化在国内外尚处于前沿研究阶段。本文成功地将并行计算应用于不规则排样算法。测试结果表明并行技术能够大幅度提高排样的计算速度,但考虑到通信开销,并行计算更适合求解大规模排样问题。更多还原

【Abstract】 The two-dimensional packing problem arises in several industries: die cutting, shipbuilding, garment, leather cutting, etc. The slight improvement in packing efficiency can make great economic profits for these industries. On the other hand, the packing problem belongs to a class of combinatorial of optimization problems with high complexity. The scientists around the world have kept working on it for decades of years. There are two bottle-necks in the two-dimensional irregular packing problem: no-fit polygon (NFP) and computer speed. Most of the packing algorithms are based on NFP. But the NFP computing time is proportional to the square of type quantity (N) and rotation number (RN). Therefore the NFP will be a tremendous obstacle for large quantity of parts with many rotation angles. The optimation packing problem always needs a lot of iterations, which always needs several hours to reach a comparatively ideal packing result. In view of the above problems, the main works proposed in this dissertation are listed as follows:(1)A polygon contacting algorithm based on the vector graphics was proposed, which breaks the declaration that vector-polygon-contacting is slow. This contacting algorithm includes two parts: one is the polygon separation test and the other is the method of advance or retreat. The polygon separation test can be deduced to the point-in-polygon test and the intersection test of line segments. The method of advance or retreat can be described as follows: if one part is separated from the other, then it slides one step forward; else it slides backward; it keeps doing so until the contacting error satisfies the required accuracy. An example was provided to verify the highspeed of the contacting algorithm.(2)An irregular packing algorithm(HAPE) based on the principle of minimum potential energy was proposed, which reveals the physical meaning of packing problems: the part always tends to keep its center of gravity as low as possible by means of translation and rotation, thus a more compact layout being obtained. In the investigation, in order to find the optimal packing attitude with the lowest center of gravity, some equally spaced points need to be located on the sheet, and around each point, the part is rotated in a certain angle interval. Computational experiments show that HAPE is credible and is of a clear physical meaning, and that it needs no calculation of NFPs and is capable of dealing with arbitrary irregular parts.(3)HAPE is combined with hill-climbing (HC) and simulated annealing (SA), thus two hybrid algorithms being proposed. By lots of tests and comparison, the performance of these two hybrid algorithms was studied especially how the RN and PPD (packing point distance) affect the packing density. The phenomenon of Sweet RN was found in hyrid algorithm and its behaviour was studied.(4)The study on parallelization of packing algorithm belongs to the frontiers study of packing optimization. The parallel computing was successfully employed in the irregular packing algorithm. The computational experiments show that the parallel computing can greatly improve the packing speed. But the parallelization of packing algorithm is more suitable for large-scale packing problems considering the time-consuming of communication.更多还原