An Analysis of Several Heuristics for the Traveling Salesman Problem
From MaRDI portal
Publication:4140001
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
Related Items
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., Discrete extremal problems, An analysis of the extended Christofides heuristic for the \(k\)-depot TSP, The selective travelling salesman problem, Distance-based index structures for fast similarity search, A fast distributed approximation algorithm for minimum spanning trees, Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP, Multi-objective meta-heuristics for the traveling salesman problem with profits, On the nearest neighbor rule for the traveling salesman problem, Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem, Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms, Topological design of telecommunication networks --- local access design methods, Dynamic programming based heuristics for the topological design of local access networks, Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP, Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees, Random shortest paths: non-Euclidean instances for metric optimization problems, On the nearest neighbor rule for the metric traveling salesman problem, The traveling salesman problem: An overview of exact and approximate algorithms, A multiperiod traveling salesman problem: Heuristic algorithms, A modified ant colony system for solving the travelling salesman problem with time windows, On-line Steiner trees in the Euclidean plane, A competitive analysis of algorithms for searching unknown scenes, An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem, Operational estimators for the length of a traveling salesman tour, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, A location-routing problem in glass recycling, Minimizing the average searching time for an object within a graph, Minimum-weight two-connected spanning networks, An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem, Weighted nearest neighbor algorithms for the graph exploration problem on cycles, The traveling salesman puts-on a hard hat -- tower crane scheduling in construction projects, On the solutions of stochastic traveling salesman problems, The pickup and delivery traveling salesman problem with first-in-first-out loading, Two-way incremental seriation in the temporal domain with three-dimensional visualization: making sense of evolving high-dimensional datasets, Insertion techniques for the heuristic solution of the job shop problem, The traveling purchaser problem with budget constraint, Approximation algorithms for multi-criteria traveling salesman problems, Practical aspects of route planning for magazine and newspaper wholesalers, The use of dynamic programming in genetic algorithms for permutation problems, A framework for multi-robot node coverage in sensor networks, On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP, Optimal spatial monitoring of populations described by reaction-diffusion models, 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, Transgenetic algorithm for the traveling purchaser problem, An empirical study of a new metaheuristic for the traveling salesman problem, A model for warehouse order picking, Reoptimization of minimum and maximum traveling salesman's tours, Combined location-routing problems: A synthesis and future research directions, Worst-case analysis of two travelling salesman heuristics, An effective implementation of the Lin-Kernighan traveling salesman heuristic, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem, Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation, The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems, A location-or-routing problem with partial and decaying coverage, Time window optimization for attended home service delivery under multiple sources of uncertainties, Not all insertion methods yield constant approximate tours in the Euclidean plane, Approximate spanning cactus, Edge crossings in drawings of bipartite graphs, A tabu search heuristic for the undirected selective travelling salesman problem, Flexible pair-copula estimation in D-vines using bivariate penalized splines, 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, 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, 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
