Two-Dimensional Irregular Packing Algorithm Based On HAPE And Its Performance Study

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.