关键词: 矩形优化排样, 蚁群优化算法, 排样方案, 组合优化

Abstract:

The rectangular packing problem comes from the actual production, it is important for industries to save raw material utilization, reduce costs, improve economic efficiency. Ant Colony System is the abstract simulation of ants group behaviors. ACS has the advantages of distributed computing, information feedback and heuristic search.The optimal layout for rectangles is a NPcomplete combinatorial optimization problem. The ant colony system algorithm and the surplus rectangle algorithm are used for solving the packing problem of rectangles in this paper. First，the rectangles packing problem is turned into a permutation problem．Second，a surplus rectangle algorithm is introduced to decode the permutation of rectangles to the corresponding packing pattern uniquely． At the end of this paper, the new ant colony system is validated by two examples，and the facts show that the new algorithm presented by this paper is efficient．

Key words: rectangle packing;ant colony system algorithm;packing pattern;combinatorial optimization