Research On Irregular Polygon Nesting Algorithm And Its Application

The irregular polygon nesting problem is to place a number of various objects on big sheet with reasonable layout. Its goal is to maximize the utilization efficiency of raw material and to increase the economic efficiency. The nesting problem of irregular polygon is involved in many industrial domains. For irregular polygon nesting problem is a NP problem, it revives much attention from both academic and industry. The dissertation focuses on two key points of irregular polygon nesting problem:irregular polygon position algorithm and nesting order algorithm. The dissertation’s main contents is as the following:(1) Rapid scanning region position algorithm:The scanning region position algorithm has advantages of robustness and easy to implement, but it suffers from intensive computing. Firstly, the presented algorithm place irregular polygon rapidly based on largest span comparison; then covert position problem to one-dimension sorting problem by using adaptive translate matrix.(2) Heuristic rule of maximum dual-direction fitness:BL and BFL algorithm is based on heuristic rule of "most bottom and most left", which may lead to unreasonable result. The dissertation presents "Heuristic rule of maximum dual-direction fitness", which considers fitness in both horizontal and vertical direction. Both computing dual-direction fitness computing algorithm and dual-direction fitness based position algorithm are implemented.(3) Algorithm of nesting order based on generic algorithm and grouping:Direct application of genetic algorithm for generating nesting order may leads to random and unpredictable result. The dissertation improves generic algorithm based nesting order algorithm by combine grouping strategy. The presented algorithm firstly divided all polygons into several groups according to scale based on heuristic rules, and then take group as gene for optimization with generic algorithm.