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

Path Optimization in CNC Cutting Machine Based on Modified Variable Neighborhood Search

作　　者：廖义辉 杨恩君 刘安东[1] 俞立[1] LIAO Yi-hui;YANG En-jun;LIU An-dong;YU Li(College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China)

机构地区：[1]浙江工业大学信息工程学院,杭州310023

出　　处：《计算机科学》2020年第10期233-239,共7页Computer Science

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

摘　　要：针对数控加工中平面多轮廓样片的空行程路径优化问题,文中提出了一种基于改进变邻域搜索(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%。实验结果表明了该算法能同时兼顾求解精度和运行时间,具有一定的应用价值。To solve the optimization problem of non-cutting path for multi-contour segments,a modified variable neighborhood search(MVNS)based metaheuristic algorithm is proposed for computer numerical control(CNC)processing systems.Firstly,this paper transfers the optimization problem into a generalized traveling salesman problem(GTSP).Secondly,for the sequential sequence problems in GTSP,it modifies the local search and shaking procedure in traditional variable neighborhood search.A 2-opt with insertion operator of neighborhood structure and an incremental calculation method are proposed for local search,which improve the solution quality and search efficiency.Combining genetic algorithm,some operators such as partition and reorganization are designed for shaking procedure,which avoid to prematurely fall into local optimum.Furthermore,a Tabu search with dynamic programming(TS-DP)algorithm is used to eliminate duplicate cutting sequences and determine the starting point of each segment.Finally,through the application examples and comparative experiments,the effectiveness of the proposed algorithm is tested from the perspective of solution accuracy and running time.In the test of cloth segments,the proposed algorithm improves the results of garment CAD about more than 51%,and the average running time is 9.3 s.In the test of TSP,the proposed algorithm achieves or exceeds the accuracy value of the comparison algorithm in most instances.In the test of GTSP,although the proposed algorithm achieves or exceeds the accuracy of the comparison algorithm in some instances,the difference of the average error between the proposed algorithm and the comparison algorithm is within 1%,and average running time of the proposed algorithm is 73.7%shorter than the comparison algorithm.Thus,the test results demonstrate that the proposed algorithm can simultaneously consider the solution accuracy and running time,which has a certain application value.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]