Intelligent Optimization Nesting Method

Given a set of irregular shapes, the two-dimensional irregular nesting problem is a problem of packing the shapes within a sheet and trying to find the best arrangement that could maximize the utilization of materials, and minimize the wastage of raw materials. The problem is NP-hard even when the shapes and the material involved are rectangles. It impacts upon a wide variety of industrial applications and motivates many areas of research.This paper gives a general view of the irregular nesting procedure by dividing it into several layers. The top-level is the intelligent optimal algorithms. They are in charge of the overall effect of the nesting procedure by ways of generating the best nesting order, rotating angle and mirroring way of every irregular shape. The next one would be the Bottom-Left-Fill heuristic algorithm which organizes the nesting procedure, putting the shapes onto the sheet one by one using BLF strategy. What comes next are the algorithm for judging whether the shapes intersect with each other, and the computational geometry methods for irregular polygons such as calculating area, rotating, mirroring, and shifting. The bottom layer is the geometric representation method for irregular shapes, approximating the irregular shapes by horizontal scan-lines, and representing them by sets of intervals.With regard to the intelligent optimal algorithms in charge of the overall nesting process, this paper selects the genetic algorithm, simulated annealing algorithm, genetic simulated annealing algorithm and particle swarm optimization algorithm to generate the best nesting order, rotating angle and mirroring way for every irregular shapes. Besides, the paper introduces a two-dimensional irregular shapes nesting process based on a concave function strategy for decreasing inertia weight swarm optimization algorithm. To avoid the problem of trapping into local optimum at the end of the iterative process, this paper proposes an improved swarm optimization algorithm based on a kind of swarm position neighborhood mutation, and applies it to the nesting field with the combination of the decreasing inertia weight strategy. Compare with the other two decreasing inertia weight swarm optimization algorithms, this one brings out a higher material utilization rate.Finally experiments are made to compare and quantitatively analyze the different results of these intelligent optimal algorithms, and the corresponding conclusion is drawn as following: (1) The nesting results of intelligent optimal algorithms are all better than those of traditional heuristic algorithm; (2) Among the intelligent optimal algorithms, both the particle swarm optimization algorithm and simulated annealing algorithm could give a satisfying nesting result. For the simulated annealing algorithm, perfect results happen occasionally, and so do bad ones. Nevertheless, the results will generally get better when iteration increases. As for the particle swarm optimization algorithms, they perform stably each time after the iterations, with remarkably good effects; (3) All in all, the particle swarm optimization algorithm based on the concave function strategy for decreasing inertia weight with swarm position neighborhood mutation has the best nesting performance.