Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (10): 233-239.doi: 10.11896/jsjkx.190800035

• Artificial Intelligence • Previous Articles     Next Articles

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

LIAO Yi-hui, YANG En-jun, LIU An-dong, YU Li   

  1. College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China
  • Received:2019-08-08 Revised:2019-10-11 Online:2020-10-15 Published:2020-10-16
  • About author:LIAO Yi-hui,born in 1994,postgra-duate.His main research interests include intelligent algorithms and path optimization.
    LIU An-dong,born in 1985,Ph.D,associate professor.His main research inte-rests include distributed predictive control and robot control.
  • Supported by:
    NSFC-Zhejiang Joint Fund for the Intergration of Industrialization and Informatization (U1709213) and NaturalScience Foundation of Zhejiang Province, China (LY17F030019)

PDF (PC)

771

Abstract: 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.

Key words: Computer numerical control cutting machine, Generalized traveling salesman problem, Non-cutting path, Tabu search, Variable neighborhood search

CLC Number: 

  • TP301.6
[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] ZHANG Zhi-long, SHI Xian-jun, QIN Yu-feng. Diagnosis Strategy Optimization Method Based on Improved Quasi Depth Algorithm [J]. Computer Science, 2022, 49(6A): 729-732.
[2] CHEN Yu-tao, XU Wen-chao, ZHAO Zhao-na, LIU Hong-en, WANG Hao. Optimization of Scheduling and Maintenance Strategy for Navigation Aircraft Operation [J]. Computer Science, 2020, 47(11A): 632-637.
[3] YU Jian-jun, WU Chun-ming. Offline Static Virtual Network Mapping Algorithm Based on Tabu Search Genetic Optimization [J]. Computer Science, 2019, 46(12): 114-119.
[4] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem [J]. Computer Science, 2018, 45(4): 76-82.
[5] HOU Yan-e, DANG Lan-xue, KONG Yun-feng and XIE Yi. GRASP Algorithm with Parameter Selection Mechanism for Heterogeneous Fleet School Bus Routing Problem [J]. Computer Science, 2016, 43(8): 233-239.
[6] BAI Xue-cong and ZHU Yan. Process Mining Approach Based on Tabu Search Algorithm [J]. Computer Science, 2016, 43(4): 214-218.
[7] HOU Yan-e, KONG Yun-feng, DANG Lan-xue and XIE Yi. Model and Algorithm for Heterogeneous Fixed Fleet School Bus Routing Problem [J]. Computer Science, 2016, 43(12): 234-240.
[8] ZHANG Gui-jun, XIA Hua-dong, ZHOU Xiao-gen and ZHANG Bei-jin. Hybrid Differential Evolution Based on Tabu Search Algorithm for Distribution Network Line Planning [J]. Computer Science, 2016, 43(10): 248-255.
[9] ZHENG Jing-jing ZHANG Jing WU Ji-gang. Heuristic Algorithm for Server Placement in Distributed Interactive Applications [J]. Computer Science, 2015, 42(7): 95-98.
[10] CAI Yan-guang, TANG Ya-lian and ZHU Jun. Hybrid Tabu Search Algorithm for Solving Incident Vehicle Routing Problem [J]. Computer Science, 2015, 42(4): 230-234.
[11] QI Ming-yao,ZHANG Jin-jin and REN Li. Vehicle Routing Algorithm Based on Spatiotemporal Clustering [J]. Computer Science, 2014, 41(3): 218-222.
[12] YE Xiao-long,LAN Ju-long and GUO Tong. Algorithm of Network Traffic Feature Selection Based on PCA and Tabu Search [J]. Computer Science, 2014, 41(1): 187-191.
[13] . Efficient Heuristic and Tabu Search for Hardware/Software Partitioning [J]. Computer Science, 2012, 39(1): 290-294.
[14] WEN Wan-hui,LIU Guang-yuan,XIONG Xie. Feature Selection Model and Generalization Performance of Two-class Emotion Recognition Systems Based on Physiological Signals [J]. Computer Science, 2011, 38(5): 220-223.
[15] ZHOU Ya-lan,WANG Jia-hai,BI Wei,MO Bin,LI Shu-guang. Competitive Hopfield Network Combined with Variable Neighborhood Search for Maximum Diversity Problems [J]. Computer Science, 2010, 37(3): 208-211252.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.