一种求解直角边零件下料问题的启发式方法

发布时间：2018-12-09 17:18

【摘要】：切割与布局问题是一种极具代表性的组合优化问题,在求解的复杂性上属于典型的NP难问题。布局问题具有很强的实用性,在实际生活、生产中经常遇到,它的求解对理论研究和实际应用都有着重要的价值,因此布局问题是计算机领域、运筹学领域和组合数学领域中的重要话题。对于二维下料布局,目前在学术界主要侧重对规则零件和完全不规则零件的研究,然而在实际工业生产中存在一种介于二者之间的直角边零件,它的轮廓是由直角边组成,并且任意相连两边的夹角都是直角。对于这种零件的布局研究称为直角边零件下料问题。本文对直角边零件下料问题进行深入的研究,目的是寻求最优化的下料方案以提高板材利用率。本文的主要内容归纳如下：首先,总结归纳了布局问题的分类和国内外研究现状,提出了本课题的研究内容。然后,通过对直角边零件下料问题的分析及其常见求解方法的研究,本文提出了利用启发式方法对直角边零件进行下料规划的求解方案,即：首先建立用于规划直角边零件下料问题的混合整数规划模型(mixed integer programming model,简称MIP模型),并求出其松弛问题的解；而后将其解建模为最小顶点覆盖问题(minimum vertex cover problem,简称MVC问题)；最后使用基因遗传算法求解MVC问题并将其解还原成为直角边零件下料问题的解。最后本文对上述求解方案给予了实现,其过程是：(1)利用C++语言与IBM公司开发的CPLEX软件相结合,生成带有干涉区域的排样方案,将此方案作为初始模型,再通过C++语言将模型转化为MVC问题。(2)利用基因遗传算法求解MVC问题,根据变量个数等已知条件,选取最优的种群大小、最大迭代数、变异率等参数数值,利用MATLAB软件中的遗传算法工具箱进行优化,求得MVC问题的可行解。(3)利用C++语言编写程序,将求得的MVC问题的可行解还原为下料问题的优化排样方案,利用计算机辅助绘图软件输出求解图形,从而得到了本文所要求得的直角边零件下料问题的可行解。与以往文献中纯粹基于混合整数规划的求解方法相比,本文的方法扩大了直角边零件下料问题的可求解规模,缩短了计算时间。与现行人工布排相比,本文提出的方法能够平均提高待布局板材的利用率约15%左右,增加了板材使用价值,提高了企业的经济效益。
[Abstract]:The problem of cutting and layout is a kind of representative combinatorial optimization problem, which belongs to the typical NP problem in the complexity of its solution. Layout problem has strong practicability and is often encountered in real life and production. Its solution is of great value to both theoretical research and practical application, so the layout problem is a computer field. An important topic in the field of operational research and combinatorial mathematics. For the layout of two-dimensional blanking, at present, the academic circles mainly focus on the research of regular parts and completely irregular parts. However, in the actual industrial production, there is a kind of right-sided part between the two parts, whose outline is composed of right-angled edges. And the angles on either side are right angles. The research on the layout of this kind of parts is called the cutting problem of right side parts. In this paper, the cutting problem of right side parts is studied in order to find the optimal cutting scheme to improve the utilization ratio of sheet metal. The main contents of this paper are summarized as follows: firstly, the classification of layout problems and the current research situation at home and abroad are summarized, and the research content of this subject is put forward. Then, based on the analysis of the right edge part cutting problem and the research of its common solving methods, this paper puts forward a method to solve the right edge part cutting planning by using the heuristic method. That is to say, the mixed integer programming model (mixed integer programming model, for short MIP model), which is used to plan the right side part blanking problem, is first established, and the solution of its relaxation problem is obtained. Then the solution is modeled as the minimum vertex covering problem (minimum vertex cover problem,), and the genetic algorithm is used to solve the MVC problem and the solution is reduced to the solution of the right edge part blanking problem. Finally, the above solution is implemented in this paper. The process is as follows: (1) using C language and CPLEX software developed by IBM company, the layout scheme with interference region is generated, and this scheme is regarded as the initial model. Then the model is transformed into MVC problem by C language. (2) the genetic algorithm is used to solve the MVC problem. According to the known conditions such as the number of variables, the optimal population size, maximum iteration number, variation rate and other parameters are selected. The feasible solution of the MVC problem is obtained by using the genetic algorithm toolbox in MATLAB software. (3) the feasible solution of the MVC problem is reduced to the optimal layout scheme of the feedstock problem by programming in C language. The computer aided drawing software is used to output and solve the graph, and the feasible solution of the right side part feeding problem is obtained. Compared with the previous methods based on mixed integer programming, this method expands the solvable scale and shortens the calculation time. Compared with the current artificial layout, the method proposed in this paper can increase the utilization ratio of the plate to be laid out by about 15%, increase the use value of the plate and increase the economic benefit of the enterprise.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18;TH16

【参考文献】