矩形石板优化排样及切割路径规划研究

袁 哲，王永振，赵汉驰，安 冬

（1.沈阳建筑大学 机械工程学院，2.高档石材数控加工设备与技术国家地方联合工程实验室，沈阳 110168）

0 引言

国内石材加工现处于粗放型的加工阶段，多采用人工计算排样和切割加工，石材利用率低，浪费了大量珍贵的不可再生资源[1]。为了提高石材的利用效率，有必要研制一种可自动排样及切割加工的桥式切机，这需要对矩形石板的优化排样及对应的切割路径规划问题进行研究[2～4]。国内外学者对矩形排样进行了很多的研究，赵民[5]等利用VC++设计了矩形单一排样系统；M.Z.Arslanov等[6]人利用多项式算法得到了同高度或同宽度矩形的最优排样方式，并且得到了相应的最短路寻优路径；Andrea Cassioli等[7]利用启发式算法研究了同尺寸矩形在凸区域中的最优排样方式。上述学者对矩形排样有了深入的研究，并且给出了最短路寻优路径，但是并没有给出与排样方式对应的切割方式及切割坐标，不能满足桥式切机“一刀切”的特点。因此，针对石材“一刀切”的单一排样方式以及切割路径规划方面还有待研究。

本文利用动态规划算法建立单一排样的数学模型，通过寻求动态规划算法的全局最优路线，确定矩形石板的单一排样方式，并且按照单一排样的过程，寻找到矩形石板的切割路径，提高了矩形石板的加工效率。

1 基于动态规划的单一排样数学模型的建立及求解

动态规划是解决多阶段决策问题的一种数学方法。动态规划算法根据多阶段决策问题的特点，把多阶段的问题变换为一系列相互联系的单阶段问题，然后逐个加以解决的算法[8]。……