Nonoblivious 2-opt heuristics for the traveling salesman problem

DOI10.1002/NET.21512zbMATH Open1338.90345OpenAlexW2047057401MaRDI QIDQ2811309FDOQ2811309

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

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)

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)

Cites Work

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

Cited In (11)

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

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)