二维不规则多边形快速排样优化算法研究  

Research On Two-Dimensional Irregular Polygon Quickly Nesting Optimize Algorithm

作　　者：邓飞[1] 陈子晗 张正人 黎博 DENG Fei;CHEN Zi-han;ZHANG Zheng-ren;LI Bo(School of Information Science and Technology,Chengdu University of Technology,Chengdu Sichuan 610000,China)

机构地区：[1]成都理工大学信息科学与技术学院,四川成都610000

出　　处：《计算机仿真》2023年第3期364-369,共6页Computer Simulation

基　　金：国家自然科学基金资助项目(42072306)。

摘　　要：排样问题研究的是将零件合理摆放至固定区域内的方法,研究的目的是减少原材料消耗。排料问题属于NP完全问题,排样算法主要包括定序和定位两个方面。定序通常使用迭代优化算法调整零件的放入顺序。而定位则根据零件排放的先后顺序,将每个零件定位排放到原料板材上。定位算法复杂度高,其效率决定了排样算法的整体效率,其效果也在很大程度上影响了排样的最终结果。故对原有的扫描定位启发式算法进行了改进,提出了基于最大移动距离的扫描定位算法,使得零件定位的时间大幅减少。另一方面,针对原有的BLF定位算法因其最下最左的定位方式往往会产生零件间契合度较低的问题,提出一种多行扫描气泡消除算法,对零件排放时产生的气泡进行了优化,提高了母版的利用率。The nesting problem is to search for a method of properly placing the given parts into a fixed area,aiming to save raw materials in a large part.The nesting algorithm comes under the NP-complete problems.The layout algorithm mainly includes two aspects:ordering and positioning.Sequencing usually uses iterative optimization algorithms to adjust the placement order of parts.Positioning,on the other hand,discharges each part onto the raw material plate according to the order in which the parts are discharged.The positioning algorithm has high complexity,its efficiency determines the overall efficiency of the layout algorithm,and its effect also affects the final result of the layout to a great extent.Due to the complexity of the calculation of parts positioning in the layout process,a scanning location algorithm based on the maximum moving distance is presented as a substitute for the original scanning positioning heuristic algorithm,which greatly reduces the time of part positioning.In the former BLF positioning algorithm,the bottom-up and left-to-right orientation can easily send the parts into low compatibility.As a result,a multi-line scanning algorithm is proposed to eliminate the bubbles generated during parts positioning.Based on the optimization of the above two algorithms,the layout efficiency of the parts and the usage of the master can be effectively improved.

关 键 词：不规则排料算法 快速定位 仿真 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]