PDF全文下载：2011010090
冯琳， 史俊友*
(青岛科技大学 机电工程学院，山东 青岛 266061)
摘要： 由于蚁群算法具有正反馈并行自催化机制和较强的鲁棒性等优点，逐渐成为一种应用广泛的元启发式算法。针对矩形毛坯在定宽无限长的板材上排样这个NP难问题，提出采用蚁群算法进行求解。采用1种2步法：第1步利用蚁群算法寻找最优底部毛坯排放顺序得到条形料排放顺序，第2步采用一种宽度方向最大填充排放算法来排放每个条形料。并将得到的结果与以往算法的结果进行比较，进一步验证了蚁群算法的优越性及处理矩形件排样问题的有效性。
关键词： 蚁群算法； 矩形件排样； 剪切下料； 条形料排样
中图分类号： TP 391.7 文献标志码: A
Optimization of Rectangle Packing Problems Based on Ant Colony Algorithm
FENG Lin， SHI Jun-you
(College of Electromechanical Engineering，Qingdao University of Science and Technology，Qingdao 266061，China)
Abstract: Since the ant colony algorithm’s autocatalytic, positive feedback, parallel mechanism and the strong robustness, it has become a widely used meta-heuristic algorithm. In the work presented here, we used an ant colony optimization (ACO) approach to solve the two-dimensional strip packing problem (2D-SPP), which consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the layout is minimized. One additional constraint the guillotine constraint can be taken into account. In this paper, a two-step method was used, the first step is using the ant colony algorithm to find the optimal order of every strip’s bottom rectangular piece, and the second step is using a least waste at width methods to fill each strip. The ant colony algorithm is subjected to a comprehensive test using benchmark instances. Compared to Genetic Simulated Annealing algorithm and Knapsack algorithm methods from the literature the ant colony algorithm performs best.
Key words: ant algorithm; rectangle packing; guillotine cutting; strip packing
收稿日期: 2010-09-20
作者简介: 冯琳(1986—)，女，硕士研究生. *通信联系人.
