Abstract: To efficiently solve the problem of two-dimensional irregular polygon packing in actual production,a heuristic algorithm driven by design knowledge was proposed.No Fit Polygon (NFP) was used to judge the relative positions between irregular polygons,and a mathematical model of local fitness was established to measure the fitting degree of irregular polygons.Then,a mathematical model driven by design knowledge was established to evaluate the position of irregular polygons to be placed.A greedy algorithm based on local search strategy was used to complete the packing.The experimental testing of international common benchmark cases and comparison with existing intelligent optimization algorithms proved that the proposed algorithm had certain advantages in layout quality and time performance with high stability.Besides,the experimental test of the sample data in actual production proved that the proposed algorithm had the value of being applied to actual production applications.

Key words: irregular packing problem, no fit polygon, knowledge-driven, heuristic algorithms

摘要： 为高效解决实际生产制造中的二维不规则多边形排样问题,提出一种设计知识驱动的启发式算法。利用临界多边形判定多边形之间的相对位置,并建立局部适应度数学模型用于衡量多边形的贴合程度;根据设计知识建立数学模型来评价多边形待摆放位置,利用基于局部搜索的贪心算法完成排样。通过对国际通用基准用例进行实验测试并与现有智能优化算法进行对比,证明了所提算法在排样质量与时间性能上不但具有一定优势,而且稳定性高。通过实际生产中样片数据的实验测试证明了所提算法的实用性。

关键词: 不规则排样问题, 临界多边形, 知识驱动, 启发式算法