基于蚁群优化算法求解矩形件排样问题

Solving Rectangular Packing Problems Based on the Ant Colony Optimization Algorithm

布局问题来源于生产实际,优秀的布局可以提高原料利用率,降低成本,提高经济效益,对许多行业有重要意义。矩形件优化排样是一类具有NP完全难度的组合优化问题。人工蚁群算法是对蚂蚁群体行为的模拟抽象,该算法具有分布计算、信息正反馈和启发式搜索等特点。本文将蚁群算法和剩余矩形法结合用于解决矩形排样问题,首先用蚁群算法将矩形件排样问题转化为一个排列问题;然后通过剩余矩形排样算法排出每一个排列所对应的排样图;最后用算法对文献[9]中的两个算例进行了验证,表明了其有效性。

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.