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

作     者：廖义辉 杨恩君 刘安东 俞立 LIAO Yi-hui;YANG En-jun;LIU An-dong;YU Li

作者机构：浙江工业大学信息工程学院杭州310023 

基　　金：NSFC-浙江省两化融合联合基金(U1709213) 浙江省自然科学基金(LY17F030019) 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2020年第47卷第10期

页      码：233-239页

摘      要：针对数控加工中平面多轮廓样片的空行程路径优化问题,文中提出了一种基于改进变邻域搜索(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的测试,所提算法在多数算例上达到或超过对比算法的精度值;对于GTSP的测试,虽然所提算法在少数算例上达到或超过对比算法的精度值,但是平均误差与对比算法的差距不超过1%,并且平均运行时间比对比算法缩短了73.7%。实验结果表明了该算法能同时兼顾求解精度和运行时间,具有一定的应用价值。

主 题 词：数控裁床 空行程路径 广义旅行商问题 变邻域搜索 禁忌搜索 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.11896/jsjkx.190800035

馆 藏 号：203986249...