锻压技术

矩形件二维正交排样的一种混合遗传算法

英文标题：A hybrid genetic algorithm on two-dimensional orthogonal layout for rectangular parts

作者：唐伟萍1 王坤2 黄欣3

单位：1.广西电力职业技术学院 2. 四川信息职业技术学院 3. 广西农业职业技术大学

分类号：TP391

出版年,卷(期):页码：2021,46(10):106-111

摘要：

讨论矩形件二维正交排样问题，即将一组已知尺寸的小矩形件正交地排放到一张大矩形板材中，寻找一个排样方式使得板材的利用率最高。将基于随机键值的遗传算法与布局策略相结合，提出一种混合遗传算法。用混合遗传算法确定矩形件的排样序列。按照排样序列，将矩形件按顺序逐个排放至板材中，每次排放矩形件时，在空闲矩形空间集合中选择一个最佳空闲矩形空间来排放当前待排矩形件，沿着该矩形件的上边和右边分别将多余空闲空间划分为两个子空闲空间，将子空闲空间添加至空闲矩形空间集合，按照上述规则继续下一个待排矩形件的布局操作，直至板材无法再排入矩形件为止。采用文献中的基准例题来测试本文算法，并与文献算法进行比较。实验结果表明，本文算法优于两种典型的文献算法。

The two-dimensional orthogonal layout problem of rectangular parts was discussed, namely, a group of small rectangular parts with known sizes were orthogonally arranged into a large rectangular plate, and a layout method was found to maximize the utilization rate of plate. A hybrid genetic algorithm was proposed by combining the genetic algorithm based on random key values with the layout strategy. Then, the layout sequence of rectangular parts was determined by hybrid genetic algorithm. According to the layout sequence, the rectangular parts were arranged into the plate one by one. When each time the rectangular parts were arranged, a best free rectangular space was selected from the set of free rectangular space to layout the current rectangular parts to be arranged, and the extra free space was divided into two sub-free spaces along the upper and right sides of the rectangular part. Furthermore, the sub-free space was added to the set of free rectangular space, and the layout operation of the next rectangular part to be arranged was continued according to the above rules until the plate could no longer be arranged into the rectangular part. Finally, the algorithm was tested by benchmark examples in the literature and compared with the literature algorithm. Experimental results show that this algorithm is better than two typical literature algorithms.

基金项目：

广西2020年度中青年教师基础能力提升项目(2020KY41016)；广西农业职业技术大学2021年科学研究与技术开发计划课题（YKJ2124）

作者简介：唐伟萍（1983-），女，硕士，副教授 E-mail：hxnz2002@126.com 通信作者：王坤（1985-），男，硕士，副教授 E-mail：wkscgy01@163.com

参考文献：

[1]Gonalves J F, Resende M G C. A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem[J]. Journal of Combinatorial Optimization, 2011, 22(2): 180-201.

[2]Ayadi O, Masmoudi M, Ben Ameur M, et al. A new PSO-based algorithm for two-dimensional non-guillotine non-oriented cutting stock problem[J]. Applied Artificial Intelligence, 2017, 31(4): 376-393.

[3]Ma N, Zhou Z. Mixed-integer programming model for two dimensional non-guillotine bin packing problem with free rotation[A]. 2017 4th International Conference on Information Science and Control Engineering (ICISCE) [C]. IEEE, 2017.

[4]Alvarez-Valdés R, Parajón A. A tabu search algorithm for large-scale guillotine (un) constrained two-dimensional cutting problems[J]. Computers & Operations Research, 2002, 29(7): 925-947.

[5]Hadjiconstantinou E, Iori M. A hybrid genetic algorithm for the two-dimensional single large object placement problem[J]. European Journal of Operational Research, 2007, 183(3): 1150-1166.

[6]Russo M, Sforza A, Sterle C. An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems[J]. Computers & Operations Research, 2014, 50: 97-114.

[7]Wei L, Lim A. A bidirectional building approach for the 2D constrained guillotine knapsack packing problem[J]. European Journal of Operational Research, 2015, 242(1): 63-71.

[8]Martin M, Birgin E G, Lobato R D, et al. Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern[J]. International Transactions in Operational Research, 2020, 27(2): 767-793.

[9]刘小可, 扈少华, 邓国斌. 基于普通块的四块排样方式及其生成算法[J]. 锻压技术, 2019, 44(11): 51-56.

Liu X K, Hu S H, Deng G B. Four-ordinary-block cutting pattern and its generation algorithmg[J]. Forging & Stamping Technology, 2019, 44(11): 51-56.

[10]Birgin E G, Lobato R D, Morabito R. Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm[J]. Journal of the Operational Research Society, 2012, 63(2): 183-200.

[11]Shiangjen K, Chaijaruwanich J, Srisujjalertwaja W, et al. An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem[J]. Engineering Optimization, 2018, 50(2): 347-365.

[12]Wscher G, Hauβner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3):1109-1130.

[13]Mellouli A, Mellouli R, Masmoudi F. An innovative genetic algorithm for a multi-objective optimization of two-dimensional cutting-stock problem[J]. Applied Artificial Intelligence, 2019, 33(6): 531-547.

[14]Laabadi S, Naimi M, El Amri H, et al. A crow search-based genetic algorithm for solving two-dimensional bin packing problem[A]. Joint German/Austrian Conference on Artificial Intelligence (Künstliche Intelligenz) [C]. Springer, Cham, 2019.

[15]Lai K K, Chan W M. An evolutionary algorithm for the rectangular cutting stock problem[J]. International Journal of Industrial Engineering: Theory Applications and Practice, 1997, 4(2): 130-139.

服务与反馈：

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