需求:
目前有固定尺寸板材一块,需要在多个位置开孔,孔径不定。
开料机排钻包钻头位置可自己定义,各钻头槽间距暂定32mm。
问题:
计算打孔方式及打孔顺序满足以下两个条件:
1 、路径最短。排钻移动路径最少。
2 、多换钻头。尽量在一个位置下多个钻打孔。
思路:
由问题一路径最短可参考TSP问题,标准算法是递归遍历,但是若孔位较多时间复杂度(n!)就会暴增。当前场景孔位已经固定,策略具备无后效性。同时考虑到问题二多钻头的情况。所以采用适配排钻布局的贪心算法来寻求最优解。最终将步骤描述如下:
a. 孔位用数字编号来表示:0,1,2...,N,孔位尺寸为H [ i ]。
b. 任何两个孔位的距离记录在数组 D0 [ i , j ] 中。
c. 按照最短路径排序重新入栈。将排钻包排列为数组。
c. 将访问过的孔位记录再 S[ i ] 中。0代表未访问,1代表已访问。指定 S[0] = 1。
d. 将在水平/垂直方向符合要求(32倍数,小于排钻包尺寸)的点位、距离及尺寸放入数组D1/D2。
e. 从 S [ 0 ] 开始,寻找排钻匹配策略,然后分别在D1、D2上迈步寻找符合多钻同打的策略。
e.1 多钻同打需要符合排钻包的尺寸排列。
e.2 同时打孔要求深度相同。
e.3 当匹配到最近同钻打孔后,重复e推进策略。
g. 采取上述所有策略中包含点位最多的策略,将策略中所有钻孔置1。排完第 t 个钻孔后,寻求局部最近坐标 t+1 ,继续匹配 e 步骤 。