锻压技术

圆形件卷材排样问题的启发式优化算法

英文标题：Heuristic optimization algorithms of coiled material layout for circular parts

作者：青巧吴红乐管卫利

分类号：TP391

出版年,卷(期):页码：2018,43(4):175-179

摘要：

圆形件卷材排样问题是将一组不同尺寸的圆形件排样在宽度指定的卷材上，使得占据的卷材长度最小。针对该问题提出一种基于先定序后定位思想的启发式优化排样算法，构建了圆形件卷材排样问题的数学模型，计算了待排样圆形件在当前布局的所有可行放置位置的优度指标，选择优度指标最高的位置放置圆形件，并通过对圆形件排放序列进行变换，得到多种不同的排样方案，选择耗费卷材长度最小的排样方案作为最终解。构造了半径非递增、首圆形件置换和子序列划分3种算法，并利用文献中的例题，比较了3种算法和文献算法排样的计算时间和卷材使用长度。实验结果表明：本文算法生成的排样方案耗费的卷材长度较小，且算法计算时间比较合理；子序列划分算法的求解质量最好，能较好地使大小圆形件在卷材中均匀分布。

The coiled material layout of circular parts is to put a set of circular parts with different sizes on a coiled sheet with a specified width to minimize occupied area of coiled sheet. To solve this problem, a heuristic optimization algorithm of layout for sequencing first and then locating was proposed, and the mathematical model of coiled material layout for circular parts was built. Then, the optimization indexes of all feasible locations in the current layout for circular parts which are going to be placed were calculated, and the location of the maximum optimization index was selected to place circular parts. Furthermore, many different layout plans were obtained by changing the place sequence of circular parts, and the layout plan with the minimum coil sheet length was selected as the final solution. Finally, three kinds of algorithms were constructed, namely the non-incremental radius, the first circular part replacement and the sub-sequence division, and based on the examples in literature, the calculation time and coil sheet length of three algorithms and literature algorithm were compared. The experimental results show that the layout plan generated by this algorithm is with a shorter coil sheet length and a reasonable calculation time. Thus, the sub-sequence division algorithm has the best solution quality and can distribute the circular parts evenly on the coil sheet.

基金项目：

广西科学研究与技术开发计划(桂科攻11107006-13，桂科攻12118017-10A)

青巧（1972-），女，硕士，高级工程师；E-mail：qqiaosc@163.com；通讯作者：管卫利（1977-），男，硕士，副教授；E-mail:gwlnn2001@126.com

参考文献：

[1]王峰, 张军, 胡钢. 圆形件剪冲下料问题的一种求解算法[J]. 锻压技术, 2015, 40(10): 39-44.

Wang F, Zhang J, Hu G. An algorithm for solving the shearing problem of circular blanks[J]. Forging & Stamping Technology, 2015, 40(10): 39-44.

[2]朱强, 薛峰, 郑仕勇,等. 约束二维排样问题的一种求解算法[J]. 锻压技术, 2016, 41(9):148-152.

Zhu Q, Xue F, Zhen S Y, et al. An algorithm of the constrained two-dimensional nesting [J].Forging & Stamping Technology, 2016，41(9):148-152.

[3]扈少华，潘立武，管卫利. 复合条带三阶段排样方式的生成算法[J].锻压技术，2016，41（11）：149-152.

Hu S H，Pan L W，Guan W L. A generating algorithm of three-stage nesting patterns for composite strip[J].Forging & Stamping Technology，2016，41（11）：149-152.

[4]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.

[5]Litvinchev I, Infante L, Ozuna L. Packing circular-like objects in a rectangular container[J]. Journal of Computer & Systems Sciences International, 2015, 54(2): 259-267.

[6]Hifi M, M'hallah R. A literature review on circle and sphere packing problems: Models and methodologies[J]. Advances in Operations Research, 2015，2009，(4)：1-22.

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

Zhao X F, Cui Y D, Yang Y, et al. A genetic algorithm for the rectangular strip packing problem[J]. Journal of Computer-aided Design & Computer Graphics, 2008, 20(4): 540-544.

[8]李霞, 陈弦. 一种启发式矩形毛坯带排样算法研究[J]. 山西大学学报: 自然科学版, 2011, 34(2): 215-218.

Li X, Chen X. Heuristic algorithm for the rectangular strip packing problem[J]. Journal of Shangxi University: Natural Science Edition, 2011, 34(2): 215-218.

[9]姚怡, 吴金春, 赖朝安. 采用分层搜索填充策略的启发式带排样算法[J]. 武汉大学学报: 工学版, 2014, 47(6): 854-858.

Yao Y, Wu J C, Lai C A. Heuristics for rectangular strip packing problem based on hierarchical search filled strategy[J]. Engineering Journal of Wuhan University, 2014, 47(6): 854-858.

[10]Stoyan Y, Yaskov G. Packing unequal circles into a strip of minimal length with a jump algorithm[J]. Optimization Letters, 2014, 8(3): 949-970.

[11]呼子宇, 杨景明, 侯新培，等. 基于离散差分进化算法的热连轧批量计划优化[J]. 塑性工程学报，2017，24(3):148-153.

Hu Z Y, Yang J M, Hou X P, et al. Optimization of hot rolling batch planning based on discrete differential evolution[J]. Journal of Plasticity Engineering, 2017, 24 (3): 148-153.

[12]Kubach T, Bortfeldt A, Gehring H. Parallel greedy algorithms for packing unequal circles into a strip or a rectangle[J]. Central European Journal of Operations Research, 2009, 17(4): 461-477.

服务与反馈：

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