基于改进变邻域搜索的数控裁床路径优化

发布时间：2024-02-22 06:39

　　针对数控加工中平面多轮廓样片的空行程路径优化问题,文中提出了一种基于改进变邻域搜索(Modified Variable Neighborhood Search,MVNS)的元启发式方法。首先,将空行程路径优化问题转化为一类广义旅行商问题(Generalized Traveling Salesman Problem,GTSP)。其次,针对GTSP中的顺序序列问题,对传统的变邻域搜索中的局部搜索和抖动阶段进行了改进。在局部搜索中,设计了基于2-opt和插入算子的邻域结构,同时采用了一种增量计算方法,提高了求解质量和搜索效率;在抖动阶段中,结合遗传算法设计了分块和重组等算子,避免了过早地陷入局部最优。然后,利用禁忌搜索混合动态规划(Tabu Search with Dynamic Programming,TS-DP)算法排除重复的裁剪序列,并确定入刀点位置。最后,通过应用实例和对比实验,从求解精度和运行时间角度检验所提算法的有效性。对于服装样片的测试,所提算法相比服装CAD的精度值提升了51%以上,平均运行时间为9.3s;对于TSP的测试,所提算法在多数算例上达到或超过对比算法的精度值;对于...

【文章页数】：7 页

【部分图文】：

图1空行程路径示意图

待裁剪的样片排样图由若干个独立样片构成,样片外轮廓的形状并不规则,包括直线、圆弧和曲线。确定样片的排样图后,每个样片外轮廓的特征点可以用几何信息代替[4]。数控裁床裁剪时,裁刀由裁床原点出发,选择一个样片的入刀点,如图1中样片上的小圆点所示。裁刀裁完一个样片后,回到入刀点,即完成....

图2解的表示方式

算法的解可以用一个二维整数矩阵表示,包含了样片序号和入刀点序号。裁床原点可以看作只含一个轮廓点的样片,则数量为m的待裁剪样片用0,1,2,…,m进行编号,每个样片的轮廓点用1,2,…,ni进行编号。因此,该矩阵第1行表示裁剪序列,第2行对应位置表示该样片入刀点在每个样片轮廓点集内....

图3裁剪序列

然而,因为空行程是一个闭合回路,若将裁剪序列的初始序号设置为固定值如数字0,则图3中的序列A,B均可以转化为序列D。此外,鉴于空行程长度与路径方向无关,序列C可以通过改变路径方向转化为序列D。因此,式(3)必然会产生重复的裁剪序列而造成多余的计算,故本文做了进一步的优化,优化方法....

图42-opt算子

为了进一步缩短运行时间,本文采用了一种增量计算方法[21],仅计算部分样片间的长度而无需重新计算新路径长度。以2-opt算子为例,假定原序列为α,变换后的序列为β,变换位置分别为i和j,2-opt算子如图4所示。显然,图4所示序列中的翻转片段和头尾处的样片序列距离值并未改变,只需....

本文编号：3906546