圆形件卷材排样问题的启发式优化算法

圆形件卷材排样问题是将一组不同尺寸的圆形件排样在宽度指定的卷材上,使得占据的卷材长度最小。针对该问题提出一种基于先定序后定位思想的启发式优化排样算法,构建了圆形件卷材排样问题的数学模型,计算了待排样圆形件在当前布局的所有可行放置位置的优度指标,选择优度指标最高的位置放置圆形件,并通过对圆形件排放序列进行变换,得到多种不同的排样方案,选择耗费卷材长度最小的排样方案作为最终解。构造了半径非递增、首圆形件置换和子序列划分3种算法,并利用文献中的例题,比较了3种算法和文献算法排样的计算时间和卷材使用长度。实验结果表明:本文算法生成的排样方案耗费的卷材长度较小,且算法计算时间比较合理;子序列划分算法的求解质量最好,能较好地使大小圆形件在卷材中均匀分布。