Computer Science ›› 2022, Vol. 49 ›› Issue (6A): 199-205.doi: 10.11896/jsjkx.210400065

• Intelligent Computing • Previous Articles     Next Articles

Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals

WANG Yong1,2, CUI Yuan2   

  1. 1 School of New Energy,North China Electric Power University,Beijing 102206,China
    2 College of Information Engineering,Tarium University,Alar,Xinjiang 843300,China
  • Online:2022-06-10 Published:2022-06-08
  • About author:WANG Yong,born in 1978,Ph.D,professor,graduate supervisor,is a member of China Computer Federation.His main research interests include graph algorithmsand applications and so on.
  • Supported by:
    National Natural Science Foundation of China(51205129) and National Key R & D Program of China(2018YFB1501302).

Abstract: With the expansion of traveling salesman problem,the search space for optimal solution on the complete graph increases exponentially.The cutting edge algorithm is proposed to reduce the search space of the optimal solution for the traveling salesman problem.It proves that the probability that an optimal Hamiltonian cycle edge contained in the shortest paths in the optimal cycles of quadrilaterals is different from that for a common edge.A number of shortest paths in the optimal cycles of quadrilaterals are selected to compute the edge frequency of edges.As the edges are cut according to the average edge frequency of all edges,the retention probability that an optimal Hamiltonian cycle edge is derived based on the constructed binomial distributions.Given Knof a traveling salesman problem,there are four steps for eliminating edges.Firstly,a finite number of quadrilaterals containing each edge are chosen.Secondly,the shortest path in the optimal cycle of every selected quadrilateral is used to compute the edge frequency.Thirdly,5/6 of edges having the smallest edge frequencies are cut.In the last step,some edges are added for vertices of degree below 2 according to the edge frequency.Experiments illustrate that the preserved edges occupy 1/6 of the total edges.Moreover,the computation time of the exact algorithms for the traveling salesman problem on the remaining graphs is reduced to some extent.

Key words: Cutting edge method, Edge frequency, Optimal cycles of quadrilaterals, Shortest path, Traveling salesman problem

CLC Number: 

  • TP301
[1] CHEN X J,XUD C,ZHANG G C.New perspectives of several fundamental problems in combinatorial optimization[J].Operations Research Transactions,2014,18(1):149-158.
[2] HU X D,YUAN Y X,ZHANG X S.Review and Prospect forthe Development of Operations Research[J].Disciplinary Deve-lopment,2012,27(2):145-160.
[3] KARP M.On the computational complexity of combinatorialproblems[J].Networks(USA),1975,5(1):45-68.
[4] ROBERTO R,MARIO R.Exact Methods for the TravelingSalesman Problem with Drone[J].Transportaton Science,2021,55(2):315-335.
[5] GONZALOL R,JUANJOSEM B.A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints[J].European Journal of Operational Research,2021,289(3):879-896.
[6] HELD M,KARP R M.The traveling salesman problem andminimum spanning trees[J].Operations Research,1970,18(6):1138-1162.
[7] HELD M,KARP R M.A dynamic programming approach to sequencing problems[J].Journal of the Society for Industrial and Applied Mathematics,1962,10(1):196-210.
[8] BELLMAN R E.Dynamic programming treatment of the travelling salesman problem[J].Journal of the ACM,1962,9(1):61-63.
[9] COOK W J,CUNNINGHAM W H.Combinatorial Optimization [M].Beijing:Higher Education Press,2011:217-242.
[10] MANERBA D,MANSINI R,RIERA-LEDESMA J.The Traveling Purchaser Problem and its variants[J].European Journal of Operational Research,2017,259(1):1-18.
[11] LV X H.Research on vehicle routing optimization based on improved branch pricing method[J].Software,2020(4):165-168.
[12] JIE W C,YANG J,LU J Y.Electric vehicle routing problembased on a branch-and-price algorithm[J].Operations Research and Management Science,2016,25(4):93-100.
[13] APPLEGATE D L,BIXBY R E.Certification of an optimal TSP tour through 85900 cities[J].Operations Research Letters,2009,37(1):11-15.
[14] COOK W.The traveling salesman problem:postcards from the edge of impossibility(Plenary talk)[C]//The 30th European Conference on Operational Research.Dublin,Ireland,2019:23-26.
[15] SEEJA K R.Solving Travelling Salesman Problem with Sparse Graphs[C]//International Conference of Computational Me-thods in Sciences and Engineering.Rhodes,GREECE,2019:1-5.
[16] XIAO M,NAGAMOCHI H.An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure[J].Algorithmica,2016,74(2):713-741.
[17] JONKER R,VOLGENANT T.Nonoptimal edges for the symmetric traveling salesman problem[J].Operations Research,1984,32(4):837-846.
[18] HOUGARDY S,SCHROEDER R T.Edges elimination in TSP instances[C]//Graph-Theoretic Concepts in Computer Science.Berlin:Springer,2014:275-286.
[19] WANG Y,HAN Z P.The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem[C]//14th International Conference on Algorithmic Aspects in Information and Management(AAIM 2020).2020:513-524.
[20] WANG Y,REMMEL J B.A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals[J].Journal of Graph Algorithms & Applications,2016,20(2):411-434.
[21] WANG Y,REMMEL J B.An iterative algorithm to eliminate edges for traveling salesman problem based on a new binomial distribution[J].Applied Intelligence,2018,48(11):4470-4484.
[22] REINELT G.TSPLIB[EB/OL]http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
[23] MITTELMANN H.Comcorde Online[EB/OL].http://neos-server.org/neos/solvers/co:concorde/TSP.html.
[24] WANG Y.Bounded degree graphs computed for TravelingSalesman Problem based on frequency quadrilaterals[C]//International Conference on Combinatorial Optimization and Applications(COCOA 2019).2019:529-540.
[1] CHEN Jun-wu, YU Hua-shan. Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs [J]. Computer Science, 2022, 49(6A): 594-600.
[2] ZHAO Xiao-wei, ZHU Xiao-jun, HAN Zhou-qing. Hover Location Selection and Flight Path Optimization for UAV for Localization Applications [J]. Computer Science, 2021, 48(11): 345-355.
[3] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[4] HU Shi-juan, LU Hai-yan, XIANG Lei, SHEN Wan-qiang. Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP [J]. Computer Science, 2020, 47(6): 219-224.
[5] LIAO Yi-hui, YANG En-jun, LIU An-dong, YU Li. Path Optimization in CNC Cutting Machine Based on Modified Variable Neighborhood Search [J]. Computer Science, 2020, 47(10): 233-239.
[6] GENG Hai-jun, YIN Xia. Efficient Intra-domain Routing Protection Algorithm Based on i-SPF [J]. Computer Science, 2019, 46(8): 116-120.
[7] MAN Zhen-zhen, YU Shi-ming and HE De-feng. Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm [J]. Computer Science, 2017, 44(7): 215-220.
[8] ZUO Xiu-feng and SHEN Wan-jie. Improved Algorithm about Muti-shortest Path Problem Based on Floyd Algorithm [J]. Computer Science, 2017, 44(5): 232-234.
[9] LI Bing-kui, ZHUANG Lei, MA Ding, HU Ying, WANG Guo-qing and JING Chen-kai. Routing Mechanism Based on Business Differentiating in Software Defined Network [J]. Computer Science, 2017, 44(3): 118-122.
[10] GAO Fa-qin. Path Prediction and Query Algorithm Based on Probability [J]. Computer Science, 2016, 43(8): 207-211.
[11] GU Ming-hao and XU Ming. Shortest Path Searching Algorithm Based on Geographical Coordinates and Closed Attribute in Road Network [J]. Computer Science, 2016, 43(6): 188-193.
[12] LONG Qi,YE Chen and ZHANG Ya-ying. Distributed Path Generation Algorithm Based on Real-time Traffic Information in Dynamic Road Network [J]. Computer Science, 2014, 41(9): 259-262.
[13] WANG Zhao-yuan,LI Tian-rui and YI Xiu-wen. Approach for Development of Ant Colony Optimization Based on MapReduce [J]. Computer Science, 2014, 41(7): 261-265.
[14] MA Hui,LI Jian-guo and LIANG Rui-shi. Finding Optimal Long Paths over Multi-cost Road Networks Using Bidirectional Searches [J]. Computer Science, 2014, 41(7): 242-245.
[15] DENG Dong-mei,WANG Guan-nan,ZHU Jian,GAO Hui and CHEN Duan-bing. Temporal Shortest Path Algorithm [J]. Computer Science, 2014, 41(6): 185-187.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!