Results 151 to 160 of about 2,383 (189)
Some of the next articles are maybe not open access.
TRAVELING SALESMAN PROBLEM OF SEGMENTS
International Journal of Computational Geometry & Applications, 2004In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n ∊-separated segments in two dimensional space.
Jinhui Xu 0001 +3 more
openaire +1 more source
The landscape of the traveling salesman problem
Physics Letters A, 1992Abstract The landscapes of traveling salesman problems are investigated by random walk techniques. The autocorrelation functions for different metrics on the space of tours are calculated. The landscape turns out to be AR(1) for symmetric TSPs. For asymmetric problems there can be a random contribution superimposed on an AR(1) behaviour.
Stadler, P., Schnabel, W.
openaire +3 more sources
Today's Traveling Salesman Problem
IEEE Robotics & Automation Magazine, 2010Heterogeneous unmanned aerial vehicles (UAVs) are being developed for several civil and military applications. These vehicles can differ either in their motion constraints or sensing/attack capabilities. This article uses methods from operations research to address a fundamental routing problem involving heterogeneous UAVs. The approach is to transform
Paul Oberlin +2 more
openaire +1 more source
On The Approximability Of The Traveling Salesman Problem
Combinatorica, 2006We show that the traveling salesman problem with triangle inequality cannot be approximated with a ratio better than $$\frac{{117}}{{116}}$$ when the edge lengths are allowed to be asymmetric and $$\frac{{220}}{{219}}$$ when the edge lengths are symmetric, unless P=NP.
Christos H. Papadimitriou +1 more
openaire +1 more source
On inverse traveling salesman problems
4OR, 2012zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Yerim Chung, Marc Demange
openaire +2 more sources
The greedy travelling salesman's problem
Networks, 1979AbstractThe Travelling Salesman's Problem is to find a Hamilton path (or circuit) which has minimum total weight W*, in a graph (or digraph) with a non‐negative weight on each edge. The Greedy Travelling Salesman's Problem is “How much larger than W* can the total weight G* of the solution obtained by the Greedy Algorithm be?”.
openaire +2 more sources
The clustered traveling salesman problem
Computers & Operations Research, 1975Abstract The traveling salesman problem is expanded to include the situation where a group of cities (cluster) must be visited contiguously in an optimal, unspecified order. Given several sets of clusters within the problem, a method is developed for optimizing simultaneously the ordering of cities within each cluster and the ordering of clusters.
openaire +1 more source
The traveling-salesman problem (abstract)
Proceedings of the 1990 ACM annual conference on Cooperation - CSC '90, 1990The traveling-salesman problem is one of the classical NP-Complete problems. No current algorithms are available which can solve these problems in polynomial time, that is, the number of steps grows as a polynomial according to the size of the input. The traveling-salesman problem involves a salesman who must make a tour of a number of cities using the
Susan N. Twohig, Samuel O. Aletan
openaire +1 more source
The hierarchical traveling salesman problem
Optimization Letters, 2012zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Kiran Panchamgam +4 more
openaire +2 more sources
Maximum travelling salesman problem
Mathematical Methods of Operations Research, 1996Summary: We present different types of techniques for designing algorithms with worst-case performances for the Maximum Travelling Salesman Problem.
Vladimir Kotov, Michail M. Kovalev
openaire +2 more sources