The symmetric traveling salesman problem and edge exchanges in minimal 1-trees

Keywords

Travelling salesman problem, Lin–Kernighan heuristic, Euclidean geometry, Relaxation (psychology), Enhanced Data Rates for GSM Evolution

References

• On the shortest spanning subtree of a graph and the traveling salesman problemJoseph B. Kruskal — 1956
• A dynamic programming approach to sequencing problemsMichael Held, Richard M. Karp — 1962
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxationTon Volgenant, Roy Jonker — 1982
• The Traveling-Salesman Problem and Minimum Spanning TreesMichael Held, Richard M. Karp — 1970
• Shortest connection networks and some generalizationsR. C. Prim — 1957
• Identification of non-optimal arcs for the travelling salesman problemRoy Jonker, Ton Volgenant — 1982
• Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution ProblemsV. Srinivasan, Gerald L. Thompson — 1972
• A Heuristic Approach to Solving Travelling Salesman ProblemsRobert L. Karg, Gerald L. Thompson — 1964
• The traveling-salesman problem and minimum spanning trees: Part IIMichael Held, Richard M. Karp — 1971
• Solving Large-Scale Symmetric Travelling Salesman Problems to OptimalityHarlan Crowder, Manfred Padberg — 1980
• Computer solutions of the traveling salesman problemShen Lin — 1965
• Flows in NetworksS. Vajda — 1963
• Polyedrische Charakterisierungen kombinatorischer OptimierungsproblemeMartin Grötschel — 1977
• A note on two problems in connexion with graphsE. Dijkstra — 1959
• A Lifo Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman Problem Using Held and Karp's 1-Tree RelaxationT. Smith, G.L. Thompson — 1977
• On the symmetric travelling salesman problem: Solution of a 120-city problemM. Grötschel — 1980

Cited by

• Metaheuristics: Some Principles for an Efficient DesignNicolas Zufferey — 2012
• Towards a taxonomy of parallel branch and bound algorithmsH.W.J.M. Trienekens, Arie de Bruin — 1992
• Parallel algorithms for the degree-constrained minimum spanning tree problem using nearest-neighbor chains and the heap-traversal techniqueLi-Jen Mao, Sheau-Dong Lang — 2002
• Comparison of Algorithms for the Degree Constrained Minimum Spanning TreeMohan Krishnamoorthy, Andreas Ernst, Yazid M. Sharaiha — 2001
• Symmetric traveling salesman problemsA. Volgenant — 1990
• Advanced vehicle routing algorithms for complex operations management problemsChristos D. Tarantilis, George Ioannou, Gregory P. Prastacos — 2005
• A note on relatives to the Held and Karp 1-tree problemAndreas Westerlund, Maud Göthe‐Lundgren, Torbjörn Larsson — 2006
• A gene-pool based genetic algorithm for TSPHui Yang, Kang Li-shanf, Chen Yu-ping — 2003
• A Lagrangean approach to the degree-constrained minimum spanning tree problemA. Volgenant — 1989
• An empirical study of a new metaheuristic for the traveling salesman problemShigeru Tsubakitani, James R. Evans — 1998
• Optimizing tabu list size for the traveling salesman problemShigeru Tsubakitani, James R. Evans — 1998
• A branch and cut method for the degree-constrained minimum spanning tree problemLouis Caccetta, Stephen P. Hill — 2001
• Nonoptimal Edges for the Symmetric Traveling Salesman ProblemRoy Jonker, Ton Volgenant — 1984
• Improved algorithms for the Steiner problem in networksTobias Polzin, Siavash Vahdati Daneshmand — 2001
• Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxationsT. H. C. Smith, Thomas Meyer, Gerald L. Thompson — 1990
• An effective implementation of the Lin-Kernighan traveling salesman heuristicKeld Helsgaun — 2000
• A note on finding a shortest complete cycle in an undirected graphA. Volgenant, R. Jonker, G.A.P. Kindervater — 1986
• On dual solutions of the linear assignment problemG.A.P. Kindervater, A. Volgenant, G. de Leve — 1985
• Edge exchanges in the degree-constrained minimum spanning tree problemMartin Savelsbergh, Ton Volgenant — 1985
• Improved polynomial algorithms for robust bottleneck problems with interval dataA. Volgenant, C.W. Duin — 2010

Related papers

• The Solutions to Traveling Salesman ProblemShuran Liao — 2023
• An empirical investigation into randomly generated Euclidean symmetric traveling salesman problemsMegha Sharma, Diptesh Ghosh — 2006
• The travelling salesman problemKaja Zupanc — 2012
• Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem as Applied to Transport Logistics ProblemsMichael Ulyanov, Michael Fomichev — 2022
• A Review of the Optimization Algorithms on Traveling Salesman ProblemN. Sathya, A. Muthukumaravel — 2015
• An Approximation Algorithm for the Maximum Traveling Salesman ProblemA.Yu. Evnin, N.I. Yusova — 2017
• Real-Life Traveling-Salesman ProblemSU Li-jie — 2005
• Hybrid Parallel Genetic Algorithm for Traveling Salesman ProblemKi-Tae Kim, Geon-Wook Jeo — 2011
• A PARAMETRIC HYBRID METHOD FOR THE TRAVELING SALESMAN PROBLEMGozde Kizilates-Evin, Fidan Nuriyeva — 2013
• A Review of the Optimization Algorithms on Traveling Salesman ProblemN. Sathya, A. Muthukumaravel — 2015