Approximate Traveling Salesman Algorithms

DOI10.1287/OPRE.28.3.694zbMath0447.90081OpenAlexW1972385709MaRDI QIDQ3893692

T. B. Doyle, W. Jun. Stewart, Bruce L. Golden, Lawrence Bodin

Publication date: 1980

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.28.3.694

zbMATH Keywords

heuristic algorithmscomparison of algorithmsnumerical theoryapproximate traveling salesman algorithmslarge scale traveling salesman problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (38)

On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem ⋮ The fleet size and mix vehicle routing problem ⋮ Global strategies for augmenting the efficiency of TSP heuristics ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ Evaluation of Heuristic Algorithms for the TSP: A New Statistical Approach ⋮ Lower Bounds for Insertion Methods for TSP ⋮ Scheduling Large-Scale Advance-Request Dial-A-Ride Systems ⋮ Time complexity of the analyst's traveling salesman algorithm ⋮ Heuristics and their design: A survey ⋮ Multiple stack branch and bound ⋮ Verschnittoptimierung im praktischen Einsatz. Eine Fallstudie ⋮ Reducing reexpansions in iterative-deepening search by controlling cutoff bounds ⋮ One-to-Many-to-One Single Vehicle Pickup and Delivery Problems ⋮ Locating concentrators in centralized computer networks ⋮ A tabu search approach to an urban transport problem in northern Spain ⋮ On the complexity of generating synchronizable test sequences ⋮ Operational estimators for the length of a traveling salesman tour ⋮ On the method of interchanging networks for permutation problems ⋮ Shuffling heuristics for the storage location assignment in an AS/RS ⋮ A computational tool for optimizing the urban public transport: A real application ⋮ A diagonal completion and 2-optimal procedure for the travelling salesman problem ⋮ Point estimation of a global optimum for large combinatorial problems ⋮ Genetic algorithms and traveling salesman problems ⋮ Asymptotic expected performance of some TSP heuristics: An empirical evaluation ⋮ Heuristic methods and applications: A categorized survey ⋮ Computational efficiency and interactive MOLP algorithms: An implementation of the SIMOLP procedure ⋮ Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem ⋮ An empirical study of a new metaheuristic for the traveling salesman problem ⋮ A model for warehouse order picking ⋮ Tourenplanung für zwei Depots bei offenen Touren ⋮ Determination of optimal path under approach and exit constraints ⋮ IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem ⋮ A parallel insert method for the capacitated arc routing problem ⋮ A useful transform of standard input data for a classical NP-complete problem ⋮ A hybrid algorithm for TSP ⋮ A comparison of techniques for solving the fleet size and mix vehicle routing problem ⋮ Set-up saving schemes for printed circuit boards assembly ⋮ A two-dimensional mapping for the traveling salesman problem

This page was built for publication: Approximate Traveling Salesman Algorithms