Nonoblivious 2-opt heuristics for the traveling salesman problem

DOI10.1002/NET.21512MaRDI QIDQ2811309zbMATHOpenAlexFDO

Authors Asaf Levin, Uri Yovel

Publication date 10 June 2016

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.21512

zbMATH Keywords

TSPheuristicslocal searchapproximation algorithmsperformance guarantees2-opt

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
• scientific article; zbMATH DE number 1003245
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)

Cites work

• A Randomized Rounding Approach to the Traveling Salesman Problem
• A Survey of Approximation Results for Local Search Algorithms
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Approximate Local Search in Combinatorial Optimization
• Computer Solutions of the Traveling Salesman Problem
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• New local search approximation techniques for maximum generalized satisfiability problems
• On Syntactic versus Computational Views of Approximability
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• TSPLIB—A Traveling Salesman Problem Library
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The design of approximation algorithms
• The traveling-salesman problem and minimum spanning trees: Part II
• Theoretical aspects of local search.

Cited in

(11)

• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• New TSP construction heuristics and their relationships to the 2-Opt
• A diagonal completion and 2-optimal procedure for the travelling salesman problem
• New TSP construction heuristics and their relationships to the 2-Opt
• scientific article; zbMATH DE number 7651222 (Why is no real title available?)
• Finding a best traveling salesman 4-opt move in the same time as a best 2-opt move
• Multiple \(k\)-opt evaluation multiple \(k\)-opt moves with GPU high performance local search to large-scale traveling salesman problems
• scientific article; zbMATH DE number 4031430 (Why is no real title available?)
• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
• On the neighborhood structure of the traveling salesman problem generated by local search moves

Describes a project that uses

Uses Software

• TSPLIB
• Concorde

This page was built for publication: Nonoblivious 2-opt heuristics for the traveling salesman problem

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