锻压技术

矩形件排样问题的遗传模拟退火混合求解算法

英文标题：Genetic simulated annealing hybrid algorithm on layout problem of rectangular part

作者：王莉

单位：泸州职业技术学院

分类号：TP391

出版年,卷(期):页码：2021,46(8):70-76

摘要：

为了提高矩形件排样问题的板材利用率，提出了基于匹配度的最低水平线定位方法和遗传模拟退火的排序方法。对于矩形件排样问题，建立了以提高板材利用率为目标的优化模型。在矩形件的定位方法中，为了提高最低水平线算法的板材利用率，提出了矩形件与板材匹配度的概念，实现了基于匹配度的最低水平线算法，此方法可以对排序结果进行微调和再优化。在排序方法中，给出了遗传模拟退火的混合算法，此算法依概率选择染色体，相比于贪婪准则可有效提高染色体的多样性。经Benchmark中的C算例进行验证，遗传模拟退火算法排样的板材利用率均高于遗传算法排样的板材利用率，验证了所提排样方法的优越性。

In order to improve the plate utilization rate of layout problem for rectangular part, the lowest horizontal line location method based on matching degree and the sorting method of genetic simulated annealing were proposed, and for the

layout problem of rectangular part, an optimization model was established to improve the plate utilization rate. In the location method of rectangular part, the concept of matching degree between rectangular part and plate was proposed in order to improve the plate utilization rate of the lowest horizontal line algorithm, and the lowest horizontal line algorithm based on matching degree was realized, which could fine-tune and re-optimize the sorting results. Furthermore, in the sorting method, a hybrid algorithm of genetic simulated annealing was given, which selected chromosomes according to probability, which could effectively improve the diversity of chromosomes compared with greedy criterion. The C example in Benchmark shows that the plate utilization rate of genetic simulated annealing algorithm layout is higher than that of genetic algorithm layout, which verifies the superiority of the proposed layout method.

基金项目：

四川省高等职业教育研究中心科研项目（GZY20B06）

王莉（1974-），女，硕士，副教授 E-mail：liwang197409@163.com

参考文献：

［1］曾晓亮, 吴琼,袁旭华. 二维矩形件排样问题的自适应多岛遗传算法优化
［J］.锻压技术,2020,45(12):53-58.

Zeng X L, Wu Q, Yuan X H. 2D rectangle packing optimization based on adaptive multi-island genetic algorithm
［J］. Forging & Stamping Technology, 2020,45(12):53-58.

［2］高勃, 张红艳,赵宏军,等. 面向智能工厂应用的启发式板材排样优化算法
［J］.北京交通大学学报,2020,44(5):98-103.

Gao B, Zhang H Y, Zhao H J, et al. A heuristic layout optimization algorithm for smart factory applications
［J］. Journal of Beijing Jiaotong University, 2020,44(5):98-103.

［3］罗强. 基于灰狼算法的矩形优化排样及其在板式家具开料中的应用
［D］. 武汉：华中科技大学,2019.

Luo Q. Research on Rectangular Packing Problem Based on the Grey Wolf Optimization Algorithm with Its Application in Plate Furniture Cutting
［D］. Wuhan: Huazhong University of Science and Technology, 2019.

［4］向文欣, 荀珂,冉翠翠. 基于两段排样方式的剪冲下料优化算法
［J］.锻压技术,2019,44(6):35-40.

Xiang W X, Xun K, Ran C C. An optimization algorithm for shearing and punching problem based on two-segment layout
［J］. Forging & Stamping Technology, 2019,44(6):35-40.

［5］刘少云. 基于组合包络的不规则件排样算法的研究与实现
［D］. 长沙：湖南大学,2019.

Liu S Y. A Research and Realization of Irregular-part Nesting Based on Combination Envelope
［D］. Changsha: Hunan University, 2019.

［6］Vanzela M, Melega G M, Rangel S, et al. The integrated lot sizing and cutting stock problem with saw cycle constraints applied to furniture production
［J］.Computers & Operations Research, 2017, 79(2): 148-160.

［7］Sanchez I A, Vargas J M, Santos C A, et al. Solving binary cutting stock with matheuristics using particle swarm optimization and simulated annealing
［J］. Soft Computing, 2017，(1): 1-9.

［8］罗强, 饶运清,刘泉辉,等. 求解矩形件排样问题的十进制狼群算法
［J］.计算机集成制造系统,2019,25(5):1169-1179.

Luo Q, Rao Y Q, Liu Q H, et al. Decimal wolf pack algorithm for rectangular packing problem
［J］. Computer Integrated Manufacturing Systems, 2019,25(5):1169-1179.

［9］单宇晗. 基于自适应遗传算法的矩形排样方法研究
［J］.计算机与数字工程,2020,48(10):2343-2347,2399.

Shan Y H. Research on rectangle nesting method based on adaptive genetic algorithm
［J］. Computer & Digital Engineering, 2020,48(10):2343-2347，2399.

［10］吕文新. 针对供需要求的区域集群企业板材订单匹配与排样算法研究
［D］. 杭州：中国计量大学,2019.

Lyu W X. Research on Boards Allocation and Layout Method of Regional Cluster for Supply and Demand
［D］. Hangzhou: China Jiliang University, 2019.

［11］蒋兴波, 吕肖庆,刘成城. 一种用于矩形排样优化的改进遗传算法
［J］.计算机工程与应用,2008，(22):244-248.

Jiang X B, Lyu X Q, Liu C C. Improved genetic algorithm for packing problem of rectangles
［J］. Computer Engineering and Applications, 2008，(22):244-248.

［12］Silva B H, Machado I M, Pereira F M, et al. Application of the simulated annealing algorithm to the correlated WMP radiation model for flames
［J］. Inverse Problems in Science and Engineering, 2020, 28(9):1-16.

［13］Hopper E, Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem
［J］. European Journal of Operational Research, 2007, 128(1):34-57.

服务与反馈：

【文章下载】【加入收藏】