Two-dimensional Nesting problem is one of Hilbert's twenty-three problems of 1900, which belongs to Nondeterministic Polynomial Completeness (NPC) problem, it is also the complicated nonlinear restricted optimization problem, so far it has not been solved. But nesting problem is applied in many fields such as mechanical processing, garment cutting, makeup of the press and VLSI design and so on. The common target of nesting problem in different fields is in order to achieve good divisible scheme for high material utilization and reduce cost of the production. People grope for the answers using Computer Aided Nesting (CAN), and find many methods from traditional mathematics methods to modern heuristic strategies, which have their limitations. Thus, the exploration of the excellent optimization algorithms for nesting problem has important application value.The Heuristic Bottom-Left Searching (HBLS) Algorithm based on graphic scan conversion method is introduced in the paper, which serves as the bottom Algorithm to receive the optimization parameters from the upper optimization Algorithms. The graphic scan conversion technique can transforms the two-dimensional irregular polygons into the discretizing geometrical information, which solves the problems caused by the complex profiles of polygons, then the irregularity of parts does not affect the computational complexity of nesting problem.The thesis emphasizes on two improved Algorithms about particle swarm optimization (PSO), which are applied to the nesting of two-dimensional irregular parts. One is the Quantum-Behaved Particle Swarm Optimization (QPSO), the other is the particle swarm optimization with maximal velocity contractile strategy (MVCS-PSO). The experimental results show that QPSO and MVCS-PSO are superior to simulated annealing genetic Algorithm (SAGA) in terms of both the material utilization and the execution time. QPSO is superior to MVCS-PSO in the execution time, but QPSO is a little inferior to MVCS-PSO in material utilization. Finally QPSO, MVCS-PSO and SAGA are applied to the packing optimization on garment CAD. QPSO and MVCS-PSO have the excellent characteristic about the non-linear dynamic search, which is proved by comparing them to SAGA on garment packing. The experimental results show that QPSO and MVCS-PSO are the kind of efficient optimization Algorithm for nesting problem.
|