Optimization algorithm for rectangle packing problem based on varied-factor genetic algorithm and lowest front-line strategy

摘要

Rectangle packing problem exists widely in manufacturing processes of modern industry, such as cutting of wood, leather, metal and paper, etc. It is also known as a typical NP-Complete combinatorial optimization problem with geometric nature, which contains two sub-problems, parking problem and sequencing problem of rectangles. Considering the features of the problem, this paper proposes an optimization algorithm based on an improved genetic algorithm (GA), combined with a lowest front-line strategy for parking rectangles on the sheet. The genetic algorithm is introduced to determine packing sequence of rectangles. To avoid premature convergence or falling into local optima, the traditional GA is improved by changing genetic factors according to quality of solutions obtained during evolution. Numerical experiments were conducted to take an evaluation for the proposed algorithm, along with a comparison with another algorithm. The simulation results show that the proposed algorithm has better performance in optimization results and can improve utilization rate of material effectively.