锻压技术

基于复合评价因子的改进遗传算法求解矩形件排样问题

英文标题：Rectangular workpiece nesting based on an improved genetic algorithm of composite evaluation factor

作者：罗强李世红袁跃兰饶运清刘泉辉

分类号：TP391

出版年,卷(期):页码：2018,43(2):0-0

摘要：

矩形件排样问题是NP-Hard的组合优化问题，计算复杂度随矩形件的规模急剧增加，难以在可接受的时间内获得精确解。在最低水平线算法的基础上，综合考虑矩形件的高度、宽度和面积这3个影响排样效果的因素，提出复合评价因子对矩形进行评价，从中选择较优的矩形排入相应的位置。通过合理的使用遗传算子，改善遗传算法的局部搜索能力，提高矩形件排样问题解的质量。实验结果表明，在广泛使用的算例N和算例C中，本文算法求得的平均最佳相对距离比GA+BLF和SA+BLF算法分别降低约70%和55%，说明了本文算法的有效性、实用性和稳定性。

The rectangular workpiece nesting is a combinational optimization problem of NP-Hard. Because its computation complexity is increased with the number of rectangles sharply, it is difficult to obtain an exact solution within an acceptable time. Based on the lowest horizontal algorithm , considering the effect factors of height, width and area of rectangular，a composite evaluation factor was presented to evaluate the rectangle，and the superior rectangle was opted to be nested. Then, the local searching capability of genetic algorithm was improved by reasonable genetic operators，and the nesting quality of rectangle was improved. Being widely used in the example N and C, the experiment result shows that the average best relative distance is lower than that of GA+BLF and SA+BLF algorithm by 70% and 55% respectively. Thus, the approach is effective, efficient and stable.

基金项目：

国家重点基础研究发展计划(2014CB046705)

作者简介：罗强（1994-），男，硕士研究生 E-mail：luoqiang0002@163.com 通讯作者：饶运清（1968-），男，博士，教授 E-mail：ryq@hust.edu.cn

参考文献：

［1］Baker B S, Coffman E G J, Rivest R L. Orthogonal packings in two dimensions
［J］. Siam Journal on Computing, 1980,9(4):846-855.

［2］Hopper E, Turton B. A genetic algorithm for a 2D industrial packing problem
［J］. Computers and Industrial Engineering, 1999, 37(1-2):375-378.

［3］刘德全，滕弘飞. 矩形件排样问题的遗传算法求解
［J］. 小型微型计算机系统，1998，19(12)：20-25.

Liu D Q, Teng H F.On gnentic algorithm for the orthogonal packing of rectangles
［J］. Journal of Chinese Computer Systems, 1998, 19(12): 20-25.

［4］贾志欣，殷国富，罗阳. 二维不规则零件排样问题的遗传算法求解
［J］. 计算机辅助设计与图形学学报，2002，14(5)：467-470.

Jia Z X, Yin G F, Luo Y. Two-dimensional irregular parts packing with genetic algorithm
［ J］ .Journal of Computer-Aided Design & Computer Graphics, 2002, 14(5):467-470.

［5］Christoforos C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts
［J］. Computers & Operations Research, 2011, 38(10): 1443-1451.

［6］贾志欣，殷国富，罗阳，等. 矩形件排样的模拟退火算法求解
［J］. 四川大学学报：自然科学版，2001，33(5)：35-38.

Jia Z X, Yin G H, Luo Y, et al. Application of simulated annealing to the rectangular packing problem
［J］ Journal of Sichuan University：Engineering Science Edition, 2001, 33(35): 35-38.

［7］Chiong R, Dhakal S. Natural Intelligence for Scheduling, Planning and Packing Problems
［M］. Heidelberg: Springer Berlin Heidelberg, 2009.

［8］Babaog⌒lu I. Solving 2D strip packing problem using fruit fly optimization algorithm
［J］.Procedia Computer Science, 2017,111: 52-57.

［9］Wei L J, Hu Q, Leung S C H, et al. An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation
［J］. Computers & Operations Research, 2017, 80(Supplement C): 113-127.

［10］Liu H, Zhou J, Wu X, et al. Optimization algorithm for rectangle packing problem based on varied-factor genetic algorithm and lowest front-line strategy
［A］.2014 IEEE Congress on Evolutionary Computation (CEC)
［C］. Beijing, 2014.

［11］龚志辉. 基于遗传算法的矩形件优化排样系统研究
［D］.长沙：湖南大学，2003.

Gong Z H. Research On the Genetic Algorithm for the Rectangular Optimal Packing System
［D］. Changsha： Hunan University, 2003.

［12］赵新芳，崔耀东，杨莹,等. 矩形件带排样的一种遗传算法
［J］. 计算机辅助设计与图形学学报，2008，20(4)：540-544.

Zhao X F, Cui Y D, Yang Y, et al. A genetic algorithm for rectangle strip packing problem
［J］. Journal of Computer-Aided Design & Computer Graphics, 2008,20 (4):540-544.

［13］刘海明，周炯，吴忻生,等. 基于改进最低水平线方法与遗传算法的矩形件排样优化算法
［J］. 图学学报，2015，36(4)：526-531.

Liu H M, Zhou J, Wu X S, et al. Optimization algorithm for rectangle packing based on improved lowest horizontal line method and genetic algorithm
［J］. Journal of Graphics, 2012, 36(4):526-531.

［14］孙佳正，郭骏. 改进的双种群遗传算法在矩形件排样中的应用
［J］. 计算机工程与应用，http://kns.cnki.net/ KCMS/detail/11.2127.TP.20170824.0954.034.html.

Sun J Z, Guo J. Improved dual population genetic algorithm for rectangle packing
［J］. Computer Engineering and Applications, http://kns.cnki.net/KCMS/detail/11.2127.TP.20170824.0954. 034.html.

［15］Wscher G, Schumann H. An improved typology of cutting and packing problems
［J］.European Journal of Operational Research,2007, 183(3):1109-1130.

［16］Burke E K, Kendall G, Whitwell G. A new placement heuristic for the orthogonal stock-cutting problem
［J］. Operations Research, 2004,52(4):655-671.

［17］赵晓东，米小珍. 遗传算法模型在矩形件排样优化中的应用
［J］. 锻压技术，2007，32(6)：153-156.

Zhao X D, Mi X Z. Application of genetic algorithm model in optimal layout of rectangular part
［J］. Forging ＆ Stamping Technology, 2007, 32(6):153-156.

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

［19］Wei L, Lim A, Zhu W. A skyline-based heuristic for the 2D rectangular strip packing problem
［J］. Modern Approaches in Applied Intelligence, 2011, 6704: 286-295.

［20］Alvarez R. Reactive GRASP for the strip-packing problem
［J］. Computers & Operations Research, 2008, 35(4): 1065-1083.

［21］Wei L, Qin H, Cheang B, et al. An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem
［J］. International Transactions in Operational Research, 2014, 23(1-2): 65-92.

［22］Leung S C H, Zhang D, Sim K M. A two-stage intelligent search algorithm for the two-dimensional strip packing problem
［J］. European Journal of Operational Research, 2011, 215(1): 57-69.

［23］Yang S, Han S, Ye W. A simple randomized algorithm for two-dimensional strip packing
［J］. Computers & Operations Research,2013, 40(1): 1-8.

服务与反馈：

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