计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 199-205.doi: 10.11896/jsjkx.210400065
王永1,2, 崔源2
WANG Yong1,2, CUI Yuan2
摘要: 随着旅行商问题规模的增长,完全图上最优解的搜索空间呈指数增长。为了减小最优解的搜索空间,提出一种针对旅行商问题的割边算法。推导出四边形最优圈内的最短路径包含一般边与最优哈密顿圈边的不同概率,采用一定数量的四边形最优圈内的最短路径计算边频率,根据所有边的平均边频率割边,基于建立的二项分布模型推导出最优哈密顿圈内边的保留概率。任给一个完全图,割边算法有4个步骤:1)随机选取包含每条边的若干个四边形;2)采用所选四边形最优圈内的最短路径计算各边的边频率;3)步删除5/6条最小边频率的边;4)对度数小于2的节点进行添边操作。计算实验表明:保留边数为完全图上边数量的1/6左右,采用精确算法求解割边后旅行商问题的计算时间也有所减少。
中图分类号:
[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. |
|