The optimum assignments and a new heuristic approach for the traveling salesman problem

DOI10.1016/0020-0255(82)90055-XzbMath0514.90083MaRDI QIDQ1051562

Kabekode V. S. Bhat

Publication date: 1982

Published in: Information Sciences (Search for Journal in Brave)

zbMATH Keywords

error boundsnetwork approachheuristic algorithmassignment problemNP-hardnesscomparison of algorithmsaugmentation procedureKarp's patching algorithmn by n traveling salesmannonsymmetric traveling salesmansuboptimum tours

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)

Related Items

Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Degree switching operations in networks and large scale systems assignment problems
• Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• An algorithm for then×n optimum assignment problem
• Some Simple Applications of the Travelling Salesman Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Theory of Output Set Assignments and Degree Switching Operations
• Lineare Charakterisierungen von Travelling Salesman Problemen
• P-Complete Approximation Problems
• On the Complexity of Local Search for the Traveling Salesman Problem
• Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Computer Solutions of the Traveling Salesman Problem
• A Sequential Method for Discrete Optimization Problems and its Application to the Assignment, Travelling Salesman, and Three Machine Scheduling Problems
• An Algorithm for the Traveling Salesman Problem
• Discrete Optimizing
• The Traveling Salesman Problem: A Survey
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• On some techniques useful for solution of transportation network problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• A SOLVABLE CASE OF THE TRAVELING SALESMAN PROBLEM