摘 要

二维下料问题是下料问题的一个分支，通常是在宽度一定的矩形板材上不重叠的排布一些矩形工件，目标是使矩形板材的利用率达到最高。该问题已被证明属于NP-hard问题，并广泛存在于国民经济的各行各业中。国内外许多学者对其进行了深入的讨论并提出了一系列行之有效的算法，如整数规划算法、遗传算法、人工粒子群算法。

本文根据二维下料问题的特点，提出了两步走算法，即第一步通过蚁群算法生成工件序列，第二步通过剩余矩形算法生成具体的排布图，以测评第一步生成的解的质量。主要工作如下：

1) 重点研究了蚁群算法的具体机理以及数学模型，并通过变异蚂蚁、精英升级策略、最大——最小蚂蚁系统对蚁群算法进行变异，使其更加适应下料问题。

2) 介绍了各种定序启发式算法，并对剩余举行算法在下料问题中的算法机理进行了详细的讲解。

3) 通过运行Hopper amp; Turton提出的21个著名算例，并与其他算法进行仿真比较，本文算法在较短时间内取得了两组简单问题的最优解以及三组困难问题的较优解，证明了算法的优秀性能。

关键词：二维下料问题，蚁群算法，剩余矩形算法

Abstract

Two dimensional cutting stock problem which is a branch of cutting stock problem is concerned with placing a set of items in a non-overlapping fashion on a strip of given width and of infinite height, and the aim is to place the items such that the height of the strip is minimized. This problem is known to be NP-complete existing widely in all walks of life in the national economy. Many scholars at home and abroad have conducted in-depth discussions and put forward a series of effective algorithms, such as integer programming algorithm, genetic algorithm, particle swarm optimization algorithm, and so on.

According to the two-dimensional cutting stock problem characteristics, this paper puts forward a two-step algorithm, that is the first step in using ant colony algorithm to generate sequence of item, the second step by rectangle fill algorithm generate specific arrangement drawings, to evaluation the quality of the solution of first step. The main work is as follows:

1) We focus on studying the specific mechanism and mathematical model of ant colony algorithm, and mutate standard ant colony algorithm through the variation of ants, elite upgrade strategy, the maximum-minimum ant system of ant colony, to make it more adaptable to the cutting stock problem.

2) We introduced a variety of sequencing heuristic algorithm, furthermore, explain mechanism of rectangle fill algorithm in two-dimensional cutting stock problem in detail.

3) Through running 21 famous problems proposed by Hopper and Turton and comparing with other algorithms, the algorithm in a short time obtains optimal solution of two simple problems and optimal solution of three difficult problems, which proved outstanding performance of algorithm.

Key words: two dimensional cutting stock problem, ant colony algorithm, rectangle fill algorithm

目 录

第1章 绪论 1

1.1 排样问题的分类 1

1.2 二维下料问题的研究背景和意义 2

1.3 二维下料问题的研究现状 2

1.4 论文的研究目的及内容 3

第2章 蚁群算法 4

2.1 蚁群算法原理分析 4

2.2 蚁群算法的数学模型 5

2.3 蚁群算法流程 6

2.4 本文蚁群算法的改进 8

第3章 改进的蚁群算法求解矩形件下料问题 9

3.1 矩形件下料问题的描述 9

3.2矩形件排样启发式排布算法 9

3.2.1 BL算法 10

3.2.2 BLF算法 10

3.2.3 下台阶算法 11

3.2.4 最低水平线算法 12

3.2.4 剩余矩形算法 13

3.3 基于剩余矩形算法的蚁群算法求解 17

3.31改进的蚁群算法思路 17

3.32 算法设计 19

3.3 仿真实验 20

3.3.1仿真实验算例设计 20

3.3.2实验结果及分析 21

第4章 结论与展望 23

4.1结论 23

4.2展望 23

致 谢 25

参考文献 26

附录 29

绪论

随着中国节能减排政策的提出，以及当前工业原材料特别是钢材等重工业原料的短缺，制造行业面临着更为激烈的竞争。众所周知，在售价不变的情况下，节约成本就是增加利润，由此企业越发注重提高原料的利用率。排样问题也就这样受到了广泛的关注，因为它直接关系到企业的综合竞争力。

计算机辅助排样，或称为CAN(Computer Aided Nesting)，是一种广泛应用的计算机辅助技术，用于辅助生成工业生产所要求的材料分割排样方案，以达到提高利用率，降低产品成本的目的。^[1]

1.1 排样问题的分类

排样问题的分类多种多样，单从空间角度狭义上来讲，排样问题可以根据工件空间维数的不同，分为一维下料，二位排样和三维装箱问题^[2]，如图1.1所示。