没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
求解矩形件下料问题的顺序启发式算法
学生:黄少丽 指导老师:崔耀东
专业:计算机应用技术
研究方向:优化计算技术与 CAD 年级:2007
中文摘要
计算机辅助排样,又称为 CAN(Computer Aided Nesting),是广泛应用的计算机辅助技
术之一,用于指导各行业处理各种下料问题,以达到节约材料、降低产品成本的目的。
下料问题存在于国民经济许多行业中,其中二维下料的应用面较广,而矩形件下料是
二维下料的基础,因此,对矩形件的优化下料进行研究是一个具有重大意义的课题。矩形
件下料问题是指在板材足够的情况下,确定一个排样方案,用尽可能少的板材排出所需全
部矩形毛坯。国内外学者对该问题进行了深入和广泛的研究,并提出了多种算法,如:线
性规划算法、模拟退火算法、遗传算法等。本文采用一种启发式算法对下料问题进行求解。
下料问题的解是一个排样方案,该方案由一个或多个排样方式组成,并指明每一个排样方
式对应的原材料的使用次数。排样方式必须是可行的,即排入板材的毛坯互不重叠且不超
出板材边界,使用合适的矩形排样算法生成排样方式对获得好的排样方案至关重要。排样
方式生成算法的主要功能是确定一个毛坯的集合以及该集合中的毛坯在板材中的排列方
式。排样算法按毛坯在板材中出现的次数是否有限制分为有约束排样算法和无约束排样算
法,无约束算法对毛坯的数量无约束,而有约束算法要求排入板材的各毛坯的数量不超过
它允许出现的上限值。另外,按是否允许在同一张板材中排入多种尺寸的毛坯,把相应的
排样方式称为单一排样方式和套裁排样方式,二者相比较,套裁下料虽然切割工艺较为复
杂,但能明显的提高材料利用率。本文主要研究采用有约束排样算法生成套裁排样方式。
本文采用一种改进的顺序启发式算法确定一个最优排样方案,主要工作是把求解排样
方式的拟人算法与基于价值修正的顺序启发式算法相结合,具体包括以下几个方面:
首先,基于最优排样方式模型,采用拟人算法按单位面积价值最大生成排样方式。拟
人算法在排入矩形毛坯时,总是使它占据一个角,并且尽量占穴。拟人算法由贪心算法和
回溯算法组成,贪心算法每次都做穴度最大的占角动作;在贪心算法的基础上使用回溯的
策略,板材中每排入一块矩形,都运用回溯法确定一个分值最高的占角动作并做这个占角
动作。在拟人算法的基础上,通过减少角的个数以及增加占角动作选择策略对算法进行改
进。
其次,将用于一维排样的顺序价值修正法中的价值修正公式加以扩展,运用到矩形件
下料问题中。排样方案中的排样方式顺序生成,每调用拟人算法生成一个排样方式,对方
式中各毛坯在板材中排布情况进行一次评价,根据评价结果再结合毛坯先前的信息来修改
毛坯的价值,重复该过程多次,使得毛坯的价值不断趋于合理。传统的顺序启发式法生成
排样方案容易导致局部最优的情况,将价值修正法融入其中,可有效地避免这种情况,使
其达到全局最优。多次迭代执行基于价值修正的顺序启发式算法生成多个排样方案,优先
I
选择材料利用率最高的排样方案,另外,最后一张板余料长以及排样方式数少也是本文的
优化目标。
最后,设计开发矩形件下料系统。通过对大量的实验进行测试,并将实验结果与相关
文献以及商业软件的计算结果进行比较和分析,结果表明,本文算法具有较高的材料利用
率。因此,本文所提的矩形件下料算法是一种有效的算法。
关键词:矩形件下料;非剪切割下料;占角动作;顺序价值修正;顺序启发式算法
II
A Sequential Heuristics Procedure for Rectangle Packing Problems
Student: Huang Shaoli Tutor: Cui Yaodong Major: Computer Application and Technique
Research Area: Optimization and Computation Technology; Computer Aided Design
Grade: 2007
Abstract
Computer aided Nesting (CAN) is one of the widely used computer aided technique, which
is used to instruct industries to deal with the cutting stock problem in order to achieve the
objectives of saving raw material and reducing the cost of product.
The cutting stock problem exists in many industries of the national economy, in which the
two-dimension cutting stock problem is applied widely. The rectangle packing problem is the
base of the two-dimension cutting stock problem, so doing the research on it is a significant issue
to find out the optimal layout of rectangular blanks. Rectangle packing problem refers to
determine a cutting solution which is to satisfy the demand of all blanks by using plates as few as
possible, on condition that there are enough plates. Scholars in and abroad have done extensive
research on this problem, and proposed a variety of algorithms such as: linear programming
algorithm,simulated annealing algorithm, genetic algorithm. This paper adopts a heuristic
algorithm to solve the rectangle packing problem. The answer to the packing problem is a cutting
solution which consists of one or more cutting patterns, and demonstrates the number of raw
material used by every pattern. The cutting pattern must be feasible, it means that the blanks
packed in the plate can’t overlap with each other and anyone of them can’t exceed the border of
the plate. It is crucial to acquire a good cutting solution that adopts suitable rectangle packing
algorithm to generate cutting patterns. The main function of the algorithm which generates the
cutting pattern is to confirm a set of blanks and determine the arrangement of the set’s blanks on
the plate. The cutting algorithm can be sorted into unconstrained algorithm and constrained
algorithm according to whether there is a limit of the times that the blank appears in the plate.
The unconstrained one doesn’t restrict the amount of blanks, but the constrained one restricts that
the number of every blank can’t exceed its permitted upper bound. In addition, according to
whether to allow packing variety sizes of blanks in a plate, the corresponding cutting pattern is
called unit-cutting patterns and multi-cutting pattern, comparatively, though the cutting process
of multi-cutting pattern is more complex, it can improve material utilization significantly. This
paper mainly does research on using constrained algorithm to generate the multi-cutting pattern.
In this paper, an improved sequential heuristics procedure is adopted to confirm an optimal
cutting solution, the main work is to combine the quasi-human algorithm which generates the
cutting pattern with the sequential heuristics procedure based on value correction, and the details
III
of this paper are as follows:
Firstly, a quasi-human algorithm is introduced to generate cutting pattern which has the
maximum value per unit area on basis of the optimal packing model. While using quasi-human
algorithm to pack a rectangle blank, the blank always occupies a corner, and a hole as possible as
it can. The quasi-human algorithm consists of greedy-algorithm and backtrack-algorithm.
Greedy-algorithm always does the corner-occupying action with maximal caving degree. The
backtrack-algorithm is used on the basis of greedy algorithm, once a blank is packed into the
plate, the backtrack-algorithm is applied to confirm a corner-occupying action which has the
maximal grade and then to do this action. On the basis of quasi-human algorithm, we improve
the algorithm by reducing the number of corners and increasing the amount of strategy for
selecting a corner-occupying action.
Secondly, a value correction formula from the one-dimension packing problem is extended
to solve the rectangle packing problem. The cutting patterns in the cutting solution are generated
sequentially, when a pattern is generated by the quasi-human algorithm, every blanks in the plate
of this pattern must be evaluating by the status of layout. The blank’s value is corrected by using
the evaluation’s result combine with the prior information, and to get more reasonable by doing
value correction repeatedly. Using traditional sequential heuristics procedure to generate cutting
solution easily lead to local optimum situation, but combining with value correction can
effectively avoid this situation and reach the global optimum. Several solutions are generated
iteratively by implementing the sequential heuristics procedure based on value correction, and
the solution with highest material utilization will be chosen. In addition, making the remaining
material as long as possible and the patterns as few as possible are also the optimization goal of
this paper.
Finally, designing and developing the rectangle packing system. The presented algorithm in
this paper is tested by using a large number of experiments, and the results are compared with
interrelated literatures as well as commercial software, the results show that the algorithm
presented in this paper can lead to high material utilization. In a word, the rectangle packing
algorithm presented in this paper is efficient.
Keywords: Rectangle packing; Un-guillotine cutting; Corner-occupying action; Sequential value
correction; Sequential heuristics procedure
IV
目 录
中文摘要 ..........................................................................................................................................I
Abstract .........................................................................................................................................III
第 1 章 绪论 ...................................................................................................................................1
1.1 问题的概述 ..........................................................................................................................1
1.2 矩形件下料问题的研究概况 ..............................................................................................1
1.3 研究方法 ..............................................................................................................................2
1.4 论文的主要工作 ..................................................................................................................2
1.5 论文的组织结构 ..................................................................................................................3
第 2 章 矩形件下料问题的数学模型以及求解模式 ...................................................................5
2.1 矩形件下料问题的数学描述 ..............................................................................................5
2.2 线性规划模型 ......................................................................................................................5
2.3 顺序启发式算法 ..................................................................................................................6
2.4 有约束排样算法生成排样方式 ..........................................................................................7
2.4.1 BL 算法(Bottom-Left) ...................................................................................................7
2.4.2 BLF 算法(BL_Fill) ........................................................................................................7
2.4.3 基于最小自由度优先的算法 .......................................................................................8
第 3 章 解矩形背包问题的拟人算法 ...........................................................................................9
3.1 问题描述 ..............................................................................................................................9
3.2 算法思想 ..............................................................................................................................9
3.3 相关概念 ..............................................................................................................................9
3.4 算法的基本策略和基本框架 ............................................................................................12
3.4.1 矩形的选择策略 .........................................................................................................12
3.4.2 占角动作的选择策略 .................................................................................................12
3.4.3 算法的基本框架 .........................................................................................................12
3.4.4 算法的相关改进策略 .................................................................................................13
3.5 算法设计 ............................................................................................................................14
3.5.1 贪心算法 .....................................................................................................................14
3.5.2 回溯算法 .....................................................................................................................15
3.6 算法的复杂度 ....................................................................................................................16
第 4 章 基于价值修正的顺序启发式算法 .................................................................................17
4.1 算法原理 ............................................................................................................................17
4.2 余料控制 ............................................................................................................................18
4.3 算法设计 ............................................................................................................................18
4.3.1 余料控制算法 .............................................................................................................18
V
剩余35页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 82
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功