An Analysis of Several Heuristics for the Traveling Salesman Problem

DOI10.1137/0206041zbMath0364.90104OpenAlexW2956015669WikidataQ56067407 ScholiaQ56067407MaRDI QIDQ4140001

Richard E. Stearns, Daniel J. Rosenkrantz, Philip Lewis

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ac5e93895ab03bf47070dab04f62f58717442f0d

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05)

Related Items (only showing first 100 items - show all)

Constructing competitive tours from local information ⋮ Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS ⋮ Length-constrained cycle partition with an application to UAV routing* ⋮ Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics ⋮ Treasure Hunt with Advice ⋮ Special cases of travelling salesman problems and heuristics ⋮ Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem ⋮ Cooperative receding horizon strategies for the multivehicle routing problem ⋮ Online graph exploration on trees, unicyclic graphs and cactus graphs ⋮ Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Probabilistic analysis of optimization problems on generalized random shortest path metrics ⋮ Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms ⋮ Evaluation of Heuristic Algorithms for the TSP: A New Statistical Approach ⋮ A competitive analysis of nearest neighbor based algorithms for searching unknown scenes ⋮ Lower Bounds for Insertion Methods for TSP ⋮ A partitioning column approach for solving LED sorter manipulator path planning problems ⋮ Reordering Strategy for Blocking Optimization in Sparse Linear Solvers ⋮ Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries ⋮ Exploration of Time-Varying Connected Graphs with Silent Agents ⋮ A scalable anticipatory policy for the dynamic pickup and delivery problem ⋮ Crowdsourced humanitarian relief vehicle routing problem ⋮ Truly tight bounds for TSP heuristics ⋮ Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising ⋮ Auction algorithm sensitivity for multi-robot task allocation ⋮ Sign depth tests in multiple regression ⋮ Probabilistic analysis of optimization problems on sparse random shortest path metrics ⋮ Heuristics for a cash-collection routing problem with a cluster-first route-second approach ⋮ Approximations for the Steiner multicycle problem ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ Unnamed Item ⋮ Exploring Endless Space ⋮ Fast upper and lower bounds for a large‐scale real‐world arc routing problem ⋮ Unnamed Item ⋮ Approximations for the Steiner multicycle problem ⋮ Recent progress of local search in handling the time window constraints of the vehicle routing problem ⋮ A Family of Unsupervised Sampling Algorithms ⋮ Online Graph Exploration: New Results on Old and New Algorithms ⋮ The single vehicle routing problem with deliveries and selective pickups ⋮ Association rule mining through the ant colony system for national health insurance research database in Taiwan ⋮ On the Nearest-Neighbor Algorithm for the Mean-Field Traveling Salesman Problem ⋮ Recent progress of local search in handling the time window constraints of the vehicle routing problem ⋮ The travelling salesman problem: selected algorithms and heuristics† ⋮ Compact storage schemes for formatted files by spanning trees ⋮ AN ASSIGNMENT-BASED LOCAL SEARCH METHOD FOR SOLVING VEHICLE ROUTING PROBLEMS ⋮ A Neural-Network-Based Approach to the Double Traveling Salesman Problem ⋮ Insertion heuristics for central cycle problems ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ Distributed MPC of constrained linear systems with time-varying terminal sets ⋮ A note on heuristics for the traveling salesman problem ⋮ Farthest-first traversal for identifying multiple influential spreaders ⋮ An improved upper bound for the online graph exploration problem on unicyclic graphs ⋮ Evasive Navigation of an Autonomous Mobile Robot in Hostile Unknown Environments ⋮ Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes ⋮ Adaptive PBDW Approach to State Estimation: Noisy Observations; User-Defined Update Spaces ⋮ Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio ⋮ An integrated inventory-routing system for multi-item joint replenishment with limited vehicle capacity ⋮ Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order ⋮ SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS ⋮ Bewertung heuristischer Methoden ⋮ Strongly Connected Spanning Subgraph for Almost Symmetric Networks ⋮ On the refinement of bounds of heuristic algorithms for the traveling salesman problem ⋮ On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem ⋮ Constructing competitive tours from local information ⋮ Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem ⋮ An improved lower bound for competitive graph exploration ⋮ Further results on the probabilistic traveling salesman problem ⋮ A new hybrid heuristic approach for solving large traveling salesman problem ⋮ The travelling salesman problem with pick-up and delivery ⋮ The traveling salesman problem with delivery and backhauls ⋮ Approximation algorithms for the Geometric Covering Salesman Problem ⋮ A geometric problem involving the nearest neighbour algorithm ⋮ A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance ⋮ Good triangulations yield good tours ⋮ The traveling group problem ⋮ Ordered spatial sampling by means of the traveling salesman problem ⋮ A new intuitional algorithm for solving heterogeneous fixed fleet routing problems: passenger pickup algorithm ⋮ Online network design with outliers ⋮ GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem ⋮ General solutions to the single vehicle routing problem with pickups and deliveries ⋮ The traveling salesman problem with backhauls ⋮ ALTO: A computer system for the design of vehicle routing algorithms ⋮ Cost of sequential connection for points in space ⋮ Genetic algorithms for the traveling salesman problem ⋮ Submodularity and the traveling salesman problem ⋮ Concurrent counting is harder than queuing ⋮ A hybrid scatter search for the probabilistic traveling salesman problem ⋮ On the greedy walk problem ⋮ Variable neighbourhood structures for cycle location problems ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems ⋮ Online graph exploration: New results on old and new algorithms ⋮ Compact location problems ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ Compatible connectivity augmentation of planar disconnected graphs ⋮ Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs ⋮ Using global search heuristics for the capacity vehicle routing problem.

This page was built for publication: An Analysis of Several Heuristics for the Traveling Salesman Problem