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

• 作者: 俞立 刘安东 廖义辉 杨恩君
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 数控裁床 空行程路径 广义旅行商问题 变邻域搜索 禁忌搜索
• 年，卷（期）: 2020,（10）
• 所属期刊栏目: 人工智能
• 页码范围: 233-239
• 页数: 7页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.11896/jsjkx.190800035

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	俞立		253	3625	30.0	50.0
2	刘安东		20	51	4.0	6.0
3	廖义辉		2	0	0.0	0.0
4	杨恩君		2	0	0.0	0.0