计算机科学 ›› 2020, Vol. 47 ›› Issue (10): 233-239.doi: 10.11896/jsjkx.190800035
廖义辉, 杨恩君, 刘安东, 俞立
LIAO Yi-hui, YANG En-jun, LIU An-dong, YU Li
摘要： 针对数控加工中平面多轮廓样片的空行程路径优化问题,文中提出了一种基于改进变邻域搜索(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%。实验结果表明了该算法能同时兼顾求解精度和运行时间,具有一定的应用价值。
中图分类号:
| [1]SHAHZADEH A,KHOSRAVI A,ROBINETTE T,et al.Smooth Path Planning Using Biclothoid Fillets for High Speed CNC Machines[J].International Journal of Machine Tools and Manufacture,2018,132:36-49. [2]CHENTSOV A G,CHENTSOV P A,PETUNIN A A,et al.Model of Megalopolises in the Tool Path Optimisation for CNC Plate Cutting Machines[J].International Journal of Production Research,2018,56(14):4819-4830. [3]SHERIF S U,JAWAHAR N,BALAMURALI M.SequentialOptimization Approach for Nesting and Cutting Sequence in Laser Cutting[J].Journal of Manufacturing Systems,2014,33(4):624-638. [4]KARUPPANAN B R C,SARAVANAN M.Optimized Sequencing of CNC Milling Toolpath Segments Using Metaheuristic Algorithms[J].Journal of Mechanical Science and Technology,2019,33(2):791-800. [5]ZHANG C,HAN F,ZHANG W.A Cutting Sequence Optimization Method Based on Tabu Search Algorithm for Complex Parts Machining[J].Proceedings of the Institution of Mechanical Engineers,Part B:Journal of Engineering Manufacture,2019,233(3):745-755. [6]ARDALAN Z,KARIMI S,POURSABZI O,et al.A Novel Imperialist Competitive Algorithm for Generalized Traveling Salesman Problems[J].Applied Soft Computing,2015,26:546-555. [7]WANG Z,YANG W B,WANG W L,et al.Path Optimization for Multi-contour Based on Quantum Evolutionary Algorithm[J].Computer Integrated Manufacturing Systems,2017,23(10):2128-2135. [8]SMITH S L,IMESON F.GLNS:An Effective Large Neighborhood Search Heuristic for the Generalized Traveling Salesman Problem[J].Computers & Operations Research,2017,87:1-19. [9]CHENTSOV A,KHACHAY M,KHACHAY D.Linear TimeAlgorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem[C]//8th IFAC Conference on Manufacturing Modelling,Management and Control MIM 2016.Troyes:Elsevier,2016:651-655. [10]ZIA M,CAKIR Z,SEKER D.Spatial Transformation of Equality-Generalized Travelling Salesman Problem to Travelling Salesman Problem[J].ISPRS International Journal of Geo-Information,2018,7(3):115-131. [11]VENKATESH P,SINGH A.An Artificial Bee Colony Algo-rithm with Variable Degree of Perturbation for the Generalized Covering Traveling Salesman Problem[J].Applied Soft Computing,2019,78:481-895. [12]HANSEN P,MLADENOVICĆ N.Variable Neighborhood Search:Principles and Applications[J].European Journal of Operational Research,2001,130(3):449-467. [13]XU Z,CAI Y.Variable Neighborhood Search for Consistent Vehicle Routing Problem[J].Expert Systems with Applications,2018,113:66-76. [14]RANJBAR M,AHMAD K.A Generalized Variable Neighbor-hood Search Algorithm for the Talent Scheduling Problem[J].Computers & Industrial Engineering,2018,126:673-680. [15]PALUBECKIS G,TOMKEVČIUS A,OSTREIKA A.Hybridizing Simulated Annealing with Variable Neighborhood Search for Bipartite Graph Crossing Minimization[J].Applied Mathematics and Computation,2019,348:84-101. [16]HORE S,CHATTERJEE A,DEWANJI A.Improving Variable Neighborhood Search to Solve the Traveling Salesman Problem[J].Applied Soft Computing,2018,68:83-91. [17]WANG X,GOLDEN B,WASIL E.A Steiner Zone VariableNeighborhood Search Heuristic for the Close-Enough Traveling Salesman Problem[J].Computers & Operations Research,2019,101:200-219. [18]HERRÁN A,COLMENAR J M,DUARTE A.A VariableNeighborhood Search Approach for the Hamiltonian P-median Problem[J].Applied Soft Computing,2019,80:603-616. [19]QIU Y,WANG L,XU X,et al.A Variable Neighborhood Search Heuristic Algorithm for Production Routing Problems[J].Applied Soft Computing,2018,66:311-318. [20]OLENDER P,OGRYCZAK W.A Revised Variable Neighbor-hood Search for the Discrete Ordered Median Problem[J].European Journal of Operational Research,2019,274(2):445-465. [21]SUN Q,JIN Y,HE K,et al.Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J].Computer Science,2018,45(4):76-82. [22]FAIGL J.GSOA:Growing Self-Organizing Array-Unsupervised Learning for the Close-enough Traveling Salesman Problem and Other Routing Problems[J].Neurocomputing,2018,312:120-134. |
| [1] | 张志龙, 史贤俊, 秦玉峰. 基于改进准深度算法的诊断策略优化方法 Diagnosis Strategy Optimization Method Based on Improved Quasi Depth Algorithm 计算机科学, 2022, 49(6A): 729-732. https://doi.org/10.11896/jsjkx.210700076 |
| [2] | 陈玉涛, 许文超, 赵召娜, 刘洪恩, 王浩. 面向通用航空器运行排班及维修的策略优化 Optimization of Scheduling and Maintenance Strategy for Navigation Aircraft Operation 计算机科学, 2020, 47(11A): 632-637. https://doi.org/10.11896/jsjkx.200600053 |
| [3] | 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法 Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem 计算机科学, 2018, 45(4): 76-82. https://doi.org/10.11896/j.issn.1002-137X.2018.04.011 |
| [4] | 侯彦娥,党兰学,孔云峰,谢毅. 求解多车型校车路径问题的带参数选择机制的GRASP算法 GRASP Algorithm with Parameter Selection Mechanism for Heterogeneous Fleet School Bus Routing Problem 计算机科学, 2016, 43(8): 233-239. https://doi.org/10.11896/j.issn.1002-137X.2016.08.047 |
| [5] | 白雪骢,朱焱. 一种基于禁忌搜索算法的流程挖掘方法 Process Mining Approach Based on Tabu Search Algorithm 计算机科学, 2016, 43(4): 214-218. https://doi.org/10.11896/j.issn.1002-137X.2016.04.044 |
| [6] | 张贵军,夏华栋,周晓根,张贝金. 一种配电网络差分禁忌线路规划方法 Hybrid Differential Evolution Based on Tabu Search Algorithm for Distribution Network Line Planning 计算机科学, 2016, 43(10): 248-255. https://doi.org/10.11896/j.issn.1002-137X.2016.10.047 |
| [7] | 郑晶晶 张 晶 武继刚. 分布式交互应用中服务器放置问题的启发式算法 Heuristic Algorithm for Server Placement in Distributed Interactive Applications 计算机科学, 2015, 42(7): 95-98. https://doi.org/10.11896/j.issn.1002-137X.2015.07.020 |
| [8] | 蔡延光,汤雅连,朱 君. 混合禁忌搜索算法求解关联运输调度问题 Hybrid Tabu Search Algorithm for Solving Incident Vehicle Routing Problem 计算机科学, 2015, 42(4): 230-234. https://doi.org/10.11896/j.issn.1002-137X.2015.04.047 |
| [9] | 戚铭尧,张金金,任丽. 基于时空聚类的带时间窗车辆路径规划算法 Vehicle Routing Algorithm Based on Spatiotemporal Clustering 计算机科学, 2014, 41(3): 218-222. |
| [10] | 冶晓隆,兰巨龙,郭通. 基于PCA和禁忌搜索的网络流量特征选择算法 Algorithm of Network Traffic Feature Selection Based on PCA and Tabu Search 计算机科学, 2014, 41(1): 187-191. |
| [11] | 王璞,武继刚. 高效软硬件划分算法及其提升技术 Efficient Heuristic and Tabu Search for Hardware/Software Partitioning 计算机科学, 2012, 39(1): 290-294. |
| [12] | 温万惠，刘光远，熊勰. 基于生理信号的二分类情感识别系统特征选择模型和泛化性能分析 Feature Selection Model and Generalization Performance of Two-class Emotion Recognition Systems Based on Physiological Signals 计算机科学, 2011, 38(5): 220-223. |
| [13] | 康雁. 优化能耗的可变电压禁忌任务调度算法 Variable Voltage Tabu Task Scheduling Algorithm for Optimizing Energy Consumption 计算机科学, 2010, 37(10): 287-290. |
| [14] | . 基于GATS—C4．5的IP流分类 计算机科学, 2009, 36(4): 68-72. |
| [15] | . 基于GridSim ToolKits的网格仿真环境设计与实现 计算机科学, 2008, 35(6): 83-85. |
|
||
首页