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

• 作者: 陈仕军 许继影 戎爱英 周伟刚
• 来源期刊: 锻压技术
• 学科: 工学
• 关键词: 矩形件 排样 空白矩形填充算法 邻域搜索算法 邻域算子
• 年，卷（期）: 2021,（2）
• 所属期刊栏目: 板料成形
• 页码范围: 52-58
• 页数: 7页
• 分类号: TP391
• 语种: 中文
• DOI: 10.13330/j.issn.1000-3940.2021.02.010

摘要

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