锻压技术

空白矩形填充和邻域搜索结合的矩形件排样优化算法

英文标题：Optimal algorithm on rectangular workpiece layout combining blank rectangle filling and neighborhood search algorithms

作者：陈仕军许继影戎爱英周伟刚

单位：湖北文理学院

关键词：矩形件排样空白矩形填充算法邻域搜索算法邻域算子

分类号：TP391

出版年,卷(期):页码：2021,46(2):52-58

摘要：

针对矩形件排样问题，提出一种新的空白矩形填充算法和邻域搜索算法相结合的混合优化算法。首先，设计空白矩形填充算法时，提出了消除多余空白矩形的方法，以减小计算时间复杂度。其次，利用邻域搜索算法优化矩形件排放顺序，通过挖掘矩形件排样的问题特征，设计了受限距离的交叉和插入两种邻域算子，并提出了特殊算子执行点选择策略。然后，设计了基于两种邻域算子交替迭代的邻域搜索算法。最后，对文献中的21个经典案例进行试验计算，4个案例的排样利用率达到了100%，绝大多数案例的排样利用率超过了99%，最小排样利用率超过了98%。将其他常用算法和文献中算法进行比较，验证了本文算法的有效性。同时，对某建材加工企业所提供的8个实际案例进行试验计算，所得排样利用率与理想最优排样利用率的平均差为1.7%，说明了本文算法的实用性。

For the problem of rectangular workpiece layout, a new hybrid optimization algorithm was proposed by combining blank rectangle filling and neighborhood search algorithms. Firstly, when the blank rectangle filling algorithm was designed, a method to eliminate extra blank rectangles was proposed to reduce the computation time complexity. Secondly, two kinds of neighborhood operators such as crossover and insertion of the limited distance are designed when the layout order of rectangular workpieces was optimized by using neighborhood search algorithm according to the characteristics of the problem. In addition, the execution point selection strategy of special operators was proposed. Then, a neighborhood search algorithm was implemented based on alternating iteration of two neighborhood operators. Finally, the experiment calculations of twenty-one classical cases in literature show that the layout utilization rate of four cases is up to 100%, the layout utilization rate of most cases exceeds 99%, and the minimum layout utilization rate exceeds 98%. Compared with other algorithms commonly used in the literature, the effectiveness of the proposed algorithm was verified. At the same time, eight actual cases provided by a building materials processing enterprise were tested and calculated, and the average difference between the obtained layout utilization rate and the ideal optimal layout utilization rate is 1.7% to indicate the practicability of the algorithm in this paper.

基金项目：

湖北省教育厅科学技术研究计划指导性项目（B2016171）

陈仕军（1980-），男，博士，讲师，E-mail：csj@hbuas.edu.cn；通讯作者：许继影（1980-），女，硕士，讲师，E-mail:xjy@hbuas.edu.cn

参考文献：

[1]Oliveira J F, Alvaro N J, Silva E M, et al. A survey on heuristics for the two-dimensional rectangular strip packing problem[J]. Pesquisa Operacional, 2016, 36(2):197-226.
[2]王睿，崔轶平，崔耀东，等.PCB多工作板尺寸单一下料精确算法[J]. 锻压技术，2019,44(3):17-23.
Wang R，Cui Y P，Cui Y D，et al. Exact algorithm of single cutting for PCB multi-working plate size[J]. Forging & Stamping Technology，2019,44(3):17-23.
[3]Baker B S, Coffman E G, Rivest R L. Orthogonal packings in two dimensions[J]. SIAM Journal on Computing, 1980, 9(4):846-855.
[4]Hopper E, Turton B C H. A genetic algorithm for a 2D industrial packing problem[J]. Computers & Industrial Engineering, 1999, 37(1-2)：375-378.
[5]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.
[6]Leung S C H, Zhang D F. A fast layer-based heuristic for non-guillotine strip packing[J]. Expert Systems with Applications, 2011,38(10):13032-13042.
[7]Chen Z, Chen J. An effective corner increment-based algorithm for the two-dimensional strip packing problem[J]. IEEE Access, 2018, 6:72906-72924.
[8]邓见凯,王磊,尹爱华. 一种求解二维矩形Packing问题的拟人型全局优化算法[J]. 计算机工程与科学, 2018, 40(2): 331-340.
Deng J K, Wang L, Yin A H. A quasi-human global optimization algorithm for solving the two dimensional rectangular packing problem[J]. Computer Engineering and Science, 2018, 40(2): 331-340.
[9]王凌. 智能优化算法及其应用[M]. 北京：清华大学出版社，2001.
Wang L. Intelligence Optimization Algorithm and Its Application[M]. Beijing: Press of Tsinghua University, 2001.
[10]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.
[11]Babalik A. Implementation of bat algorithm on 2D strip packing problem[A]. Lavangnananda K, Phon-Amnuaisuk S, Engchuan W, et al. Proceedings in Adaptation, Learning and Optimization[C].Switzerland：Springer International Publishing，2016.
[12]Babaoglu I. Solving 2D strip packing problem using fruit fly optimization algorithm[J]. Procedia Computer Science, 2017, 111:52-57.
[13]许继影,陈仕军,郑晴. 基于两阶段排放算法的矩形件排样优化方法[J]. 计算机时代, 2020, (5):13-15,19.
Xu J Y, Chen S J, Zheng Q. Optimal rectanglepacking based on two-stage placing algorithm[J]. Computer Eta, 2020,(5):13-15,19.
[14]Anand K V, Babu A R. Heuristic and genetic approach for nesting of two-dimensional rectangular shaped parts with common cutting edge concept for laser cutting and profile blanking processes[J]. Computers & Industrial Engineering, 2015, 80(2):111-124.
[15]刘海明,周炯,吴忻生,等. 基于改进最低水平线方法与遗传算法的矩形件排样优化算法[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, 2015, 36(4):526-531.
[16]范展,梁国龙,林旺生,等. 求解TSP问题的自适应邻域搜索法及其扩展[J].计算机工程与应用, 2008, (12):75-78.
Fan Z, Liang G L, Lin W S, et al. Design and expending of adaptive neighborhood searching algorithm for TSP[J]. Computer Engineering and Applications, 2008, (12):75-78.
[17]李妍峰,李军,高自友. 大规模邻域搜索算法求解时变车辆调度问题[J]. 管理科学学报, 2012, 15(1):22-32.
Li Y F, Li J, Gao Z Y. Very large scale neighborhood search algorithm for solving time dependent vehicle routing problem[J]. Journal of Management Sciences in China, 2012, 15(1):22-32.

服务与反馈：

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