计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 199-205.doi: 10.11896/jsjkx.210400065

• 智能计算 • 上一篇    下一篇

基于四边形最优圈内最短路径的旅行商问题割边方法

王永1,2, 崔源2   

  1. 1 华北电力大学新能源学院 北京 102206
    2 塔里木大学信息工程学院 新疆 阿拉尔 843300
  • 出版日期:2022-06-10 发布日期:2022-06-08
  • 通讯作者: 王永(yongwang@ncepu.edu.cn)
  • 基金资助:
    国家自然科学基金(51205129);国家重点研发计划(2018YFB1501302)

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).

摘要: 随着旅行商问题规模的增长,完全图上最优解的搜索空间呈指数增长。为了减小最优解的搜索空间,提出一种针对旅行商问题的割边算法。推导出四边形最优圈内的最短路径包含一般边与最优哈密顿圈边的不同概率,采用一定数量的四边形最优圈内的最短路径计算边频率,根据所有边的平均边频率割边,基于建立的二项分布模型推导出最优哈密顿圈内边的保留概率。任给一个完全图,割边算法有4个步骤:1)随机选取包含每条边的若干个四边形;2)采用所选四边形最优圈内的最短路径计算各边的边频率;3)步删除5/6条最小边频率的边;4)对度数小于2的节点进行添边操作。计算实验表明:保留边数为完全图上边数量的1/6左右,采用精确算法求解割边后旅行商问题的计算时间也有所减少。

关键词: 边频率, 割边方法, 旅行商问题, 四边形最优圈, 最短路径

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

中图分类号: 

  • 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] 陈钧吾, 余华山.
面向无尺度图的Δ-stepping算法改进策略
Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs
计算机科学, 2022, 49(6A): 594-600. https://doi.org/10.11896/jsjkx.210400062
[2] 赵晓薇, 朱小军, 韩周卿.
面向定位应用的无人机的悬停位置和飞行路径优化
Hover Location Selection and Flight Path Optimization for UAV for Localization Applications
计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105
[3] 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊.
智能3D打印路径规划算法
Intelligent 3D Printing Path Planning Algorithm
计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[4] 胡士娟, 鲁海燕, 向蕾, 沈莞蔷.
求解MMTSP的模糊聚类单亲遗传算法
Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP
计算机科学, 2020, 47(6): 219-224. https://doi.org/10.11896/jsjkx.190500137
[5] 周建新, 张志鹏, 周宁.
基于CKSP的分段路由负载均衡技术
Load Balancing Technology of Segment Routing Based on CKSP
计算机科学, 2020, 47(4): 256-261. https://doi.org/10.11896/jsjkx.190500122
[6] 廖义辉, 杨恩君, 刘安东, 俞立.
基于改进变邻域搜索的数控裁床路径优化
Path Optimization in CNC Cutting Machine Based on Modified Variable Neighborhood Search
计算机科学, 2020, 47(10): 233-239. https://doi.org/10.11896/jsjkx.190800035
[7] 耿海军, 尹霞.
基于增量最短路径优先的域内高效路由保护算法
Efficient Intra-domain Routing Protection Algorithm Based on i-SPF
计算机科学, 2019, 46(8): 116-120. https://doi.org/10.11896/j.issn.1002-137X.2019.08.019
[8] 蔡延光, 陈厚仁, 戚远航.
混沌烟花算法求解旅行商问题
Chaotic Fireworks Algorithm for Solving Travelling Salesman Problem
计算机科学, 2019, 46(6A): 85-88.
[9] 耿海军.
基于优化链路权值的域内路由保护方案
Intra-domain Routing Protection Scheme by Optimizing Link Weight
计算机科学, 2019, 46(1): 143-147. https://doi.org/10.11896/j.issn.1002-137X.2019.01.022
[10] 陈建荣,陈建华.
求解TSP问题的离散捕鱼策略优化算法
Discrete Fishing Strategy Optimization Algorithm for TSP
计算机科学, 2017, 44(Z6): 139-140. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.032
[11] 满振祯,余世明,何德峰.
基于改进伊藤算法的最短路径网络路由优化算法
Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm
计算机科学, 2017, 44(7): 215-220. https://doi.org/10.11896/j.issn.1002-137X.2017.07.038
[12] 李兵奎,庄雷,马丁,胡颖,王国卿,景晨凯.
SDN网络中基于业务划分的路由选择机制
Routing Mechanism Based on Business Differentiating in Software Defined Network
计算机科学, 2017, 44(3): 118-122. https://doi.org/10.11896/j.issn.1002-137X.2017.03.026
[13] 高法钦.
一种基于概率的路径预测与查询算法
Path Prediction and Query Algorithm Based on Probability
计算机科学, 2016, 43(8): 207-211. https://doi.org/10.11896/j.issn.1002-137X.2016.08.042
[14] 顾明皓,徐明.
路网中基于地理位置和区域封闭性的最短路径的查询算法
Shortest Path Searching Algorithm Based on Geographical Coordinates and Closed Attribute in Road Network
计算机科学, 2016, 43(6): 188-193. https://doi.org/10.11896/j.issn.1002-137X.2016.06.038
[15] 高峰,郑波.
基于IPSO算法的TSP问题求解研究
Study on TSP Solving Based on IPSO
计算机科学, 2014, 41(Z11): 69-71.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!