A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation

DOI10.1016/0377-2217(82)90015-7zbMath0471.90088OpenAlexW1995274002MaRDI QIDQ1158108

Roy Jonker, Ton Volgenant

Publication date: 1982

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(82)90015-7

zbMATH Keywords

computational resultsbranch and bound algorithmheuristic solutions1-tree relaxationsymmetric traveling salesmanLagrangean approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05)

Related Items (34)

Sensitivity analysis for symmetric 2-peripatetic salesman problems ⋮ Edge exchanges in the degree-constrained minimum spanning tree problem ⋮ TSP race: minimizing completion time in time-sensitive applications ⋮ A simulation tool for the performance evaluation of parallel branch and bound algorithms ⋮ Efficient optimization of the Held-Karp lower bound ⋮ Bounds for the symmetric 2-peripatetic salesman problem ⋮ A branch-and-bound algorithm for the singly constrained assignment problem ⋮ Exact hybrid algorithms for solving a bi-objective vehicle routing problem ⋮ The symmetric travelling salesman problem. II: New low bounds ⋮ A discrete cross aisle design model for order-picking warehouses ⋮ Identification of non-optimal arcs for the traveling salesman problem ⋮ The symmetric traveling salesman problem and edge exchanges in minimal 1- trees ⋮ Coarse-Graining Large Search Landscapes Using Massive Edge Collapse ⋮ Travelling salesman problem tools for microcomputers ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ Iterative state-space reduction for flexible computation ⋮ An efficient heuristic algorithm for the bottleneck traveling salesman problem ⋮ A note on relatives to the Held and Karp 1-tree problem ⋮ Symmetric traveling salesman problems ⋮ Optimizing tabu list size for the traveling salesman problem ⋮ A framework for multi-robot node coverage in sensor networks ⋮ Stability aspects of the traveling salesman problem based on \(k\)-best solutions ⋮ The symmetric clustered traveling salesman problem ⋮ New lower bounds for the symmetric travelling salesman problem ⋮ Estimating the Held-Karp lower bound for the geometric TSP ⋮ An empirical study of a new metaheuristic for the traveling salesman problem ⋮ A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron \& Steel Complex ⋮ Lower bounding techniques for frequency assignment ⋮ Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem ⋮ Improving heuristics for the frequency assignment problem ⋮ An effective implementation of the Lin-Kernighan traveling salesman heuristic ⋮ A useful transform of standard input data for a classical NP-complete problem ⋮ A branch and bound algorithm for symmetric 2-peripatetic salesman problems ⋮ Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A Dynamic Programming Approach to Sequencing Problems
• Validation of subgradient optimization
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• Computer Solutions of the Traveling Salesman Problem
• The Shortest Hamiltonian Chain of a Graph
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II

This page was built for publication: A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation