Results 1 to 10 of about 161,336 (310)
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP [PDF]
Algorithmica, 2023 Abstract2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt.
Matthias Englert +2 more
core +8 more sources
Graph attention, learning 2-opt algorithm for the traveling salesman problem [PDF]
Complex & Intelligent SystemsIn recent years, deep graph neural networks (GNNs) have been used as solvers or helper functions for the traveling salesman problem (TSP), but they are usually used as encoders to generate static node representations for downstream tasks and are ...
Jia Luo, Herui Heng, Geng Wu
doaj +3 more sources
An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour [PDF]
Applied Sciences, 2023 The travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and
Fakhar Uddin +6 more
doaj +2 more sources
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP [PDF]
AlgorithmicaAbstract The 2-opt heuristic is a simple local search heuristic for the travelling salesperson problem (TSP). Although it usually performs well in practice, its worst-case running time is exponential in the number of cities. Attempts to reconcile this difference between practice and theory have used smoothed analysis, in which adversarial ...
Manthey B, van Rhijn J.
europepmc +9 more sources
Comparison of Tabu/2‐opt heuristic and optimal tree search method for assignment problems [PDF]
International Journal of Robust and Nonlinear Control, 2011 AbstractA nonlinear cooperative control problem involving several vehicles is detailed and solved. The vehicles must be assigned to perform many tasks such that they obey constraints on the order of task completion and minimize a nonlinear objective function, the total time to finish all tasks.
J. Jackson, Mariam Faied, Anouck Girard
openalex +4 more sources
Learning 2-Opt Heuristics for Routing Problems via Deep Reinforcement Learning [PDF]
SN Computer Science, 2021 AbstractRecent works using deep learning to solve routing problems such as the traveling salesman problem (TSP) have focused on learning construction heuristics. Such approaches find good quality solutions but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance.
Paulo da Costa +4 more
openalex +3 more sources
The 2-opt behavior of the Hopfield Network applied to the TSP [PDF]
Operational Research, 2020 The Continuous Hopfield Network (CHN) became one of the major breakthroughs in the come back of Neural Networks in the mid 80s, as it could be used to solve combinatorial optimization problems such as the Traveling Salesman Problem. Once researchers provided a mechanism, not based in trial-and-error, to guarantee the feasibility of the CHN, the quality
Lucas Sánchez García +2 more
openalex +3 more sources
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise. [PDF]
AlgorithmicaAbstract The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is exponential and its approximation performance is poor in the worst case. Englert, Röglin, and Vöcking
Künnemann M, Manthey B, Veenstra R.
europepmc +7 more sources
Simulated Annealing – 2 Opt Algorithm for Solving Traveling Salesman Problem
International Journal of Computing, 2023 The purpose of this article is to elaborate performance of the hybrid model of Simulated Annealing (SA) and 2 Opt algorithm for solving the traveling salesman problem (TSP). The SA algorithm used in this article is based on the outer and inner loop SA algorithm.
P. H. Gunawan, Iryanto Iryanto
openalex +3 more sources
Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep\n Reinforcement Learning [PDF]
, 2020 To appear in Proceedings Machine Learning Research - ACML ...
Paulo Roberto de Oliveira da Costa +3 more
openalex +6 more sources