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

由于蚁群算法具有正反馈并行自催化机制和较强的鲁棒性等优点,逐渐成为一种应用广泛的元启发式算法。针对矩形毛坯在定宽无限长的板材上排样这个NP难问题,提出采用蚁群算法进行求解。采用1种2步法:第1步利用蚁群算法寻找最优底部毛坯排放顺序得到条形料排放顺序,第2步采用一种宽度方向最大填充排放算法来排放每个条形料。并将得到的结果与以往算法的结果进行比较,进一步验证了蚁群算法的优越性及处理矩形件排样问题的有效性。

Optimization of Rectangle Packing Problems Based on Ant Colony Algorithm

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.