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

Heuristic optimization algorithms of coiled material layout for circular parts

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

The coiled material layout of circular parts is to put a set of circular parts with different sizes on a coiled sheet with a specified width to minimize occupied area of coiled sheet. To solve this problem,a heuristic optimization algorithm of layout for sequencing first and then locating was proposed,and the mathematical model of coiled material layout for circular parts was built. Then,the optimization indexes of all feasible locations in the current layout for circular parts which are going to be placed were calculated,and the location of the maximum optimization index was selected to place circular parts. Furthermore,many different layout plans were obtained by changing the place sequence of circular parts,and the layout plan with the minimum coil sheet length was selected as the final solution. Finally,three kinds of algorithms were constructed,namely the non-incremental radius,the first circular part replacement and the sub-sequence division,and based on the examples in literature,the calculation time and coil sheet length of three algorithms and literature algorithm were compared. The experimental results show that the layout plan generated by this algorithm is with a shorter coil sheet length and a reasonable calculation time. Thus,the sub-sequence division algorithm has the best solution quality and can distribute the circular parts evenly on the coil sheet.