超边界约束条件下异形件排样问题的求解算法研究  

Algorithm for solving irregular parts packing problem with beyond boundary constraint

作　　者：饶运清[1] 彭灯 杜冰 罗强 林信海 RAO Yunqing;PENG Deng;DU Bing;LUO Qiang;LIN Xinhai(School of Mechanical Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China;China Ship Development and Design Center,Wuhan 430064,China)

机构地区：[1]华中科技大学机械科学与工程学院,湖北武汉430074 [2]中国舰船研究设计中心,湖北武汉430064

出　　处：《计算机集成制造系统》2023年第12期4063-4072,共10页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(51975231);中央高校基本科研业务费专项资金资助(2019kfyXKJC043)。

摘　　要：针对超边界约束条件,提出了板材动态边界搜索的处理策略,然后以临界多边形(NFP)为基础,同时引入无碰撞区域(CFR)的概念,以保证排样方案的可行性,在综合考虑零件之间的重合率和BL(bottom left)策略,以及CFR可能退化为点或线段的情况之后,提出基于CFR的混合启发式定位算法。在上述零件定位算法的基础上,采用遗传算法对零件排样顺序进行优化以解决超边界约束排样问题,并通过实例验证了所提算法的有效性。In view of the beyond boundary constraint,a processing strategy for dynamic boundary search of sheet was proposed.Based on the No-Fit Polygon(NFP),the concept of Collision Free Region(CFR)was introduced to ensure the feasibility of the layout scheme.A hybrid heuristic localization algorithm based on CFR was proposed after considering the coincidence rate between parts and the Bottom-Left(BL)strategy,as well as the situation where CFR might degenerate into points or line segments.On the basis of the above-mentioned part positioning algorithm,the genetic algorithm was used to optimize the part layout order to solve the problem of beyond boundary constraint packing,and the effectiveness of the proposed algorithm was verified by example.

关 键 词：异形件排样 超边界约束 临界多边形 动态边界搜索 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]