Special cases of travelling salesman problems and heuristics

DOI10.1007/BF02019153MaRDI QIDQ2639760zbMATH OpenFDO

Authors Rainer E. Burkard

Publication date 1990

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02019153

zbMATH Keywords

heuristicssum and bottleneck objectivestravelling salesman

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Review text

The author describes some recently analysed special cases of the travelling salesman problem (TSP) which can be solved in polynomial time. The use of special cases as heuristics for the TSP are discussed.

Recommendations

• Special cases of the traveling salesman problem
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• The travelling salesman problem: selected algorithms and heuristics†
• Special issue: The traveling salesman problem
• On Some Generalizations of the Travelling-Salesman Problem
• On the solution of traveling salesman problems
• A new heuristic for the traveling salesman problem
• Efficiently solvable special cases of bottleneck travelling salesman problems
• The traveling salesman problem and its variations

Cites work

• An Analysis of Several Heuristics for the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Approximation algorithms for convex hulls
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• Efficient special case algorithms for the n-line planar traveling salesman problem
• Efficiently solvable special cases of bottleneck travelling salesman problems
• Extreme Hamiltonian lines
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• On Some Properties of Shortest Hamiltonian Circuits
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• The Euclidean traveling salesman problem is NP-complete

Cited in

(17)

• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Optimal arcs for the traveling salesman problem
• Special issue: The traveling salesman problem
• Special cases of the traveling salesman problem
• A general approach to avoiding two by two submatrices
• Spanning trees and shortest paths in Monge graphs
• Monge matrices make maximization manageable
• Perspectives of Monge properties in optimization
• Traveling salesman problem heuristics: leading methods, implementations and latest advances
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• A Note On Kalmanson Matrices^∗
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Pyramidal tours for the traveling salesman
• Applications of a special polynomial class of TSP
• Applications of a special polynomial class of TSP
• Optimal wire ordering and spacing in low power semiconductor design
• A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem

This page was built for publication: Special cases of travelling salesman problems and heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639760)