Questions tagged [traveling-salesman-problem]

Filter by
Sorted by
Tagged with
1 vote
0 answers
52 views

A generalized/set hamiltonian cycle problem on directed graphs

So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...
whiterock's user avatar
  • 111
0 votes
0 answers
26 views

Monotony of enforced subtour merging

Is it true that for a symmetric TSP instance in the sequence of edges generated by successively: calculating the optimal 2-factor adding cardinality constraints on the edgesets of the 2-factor's ...
Manfred Weis's user avatar
  • 12.7k
1 vote
0 answers
42 views

Complexity of the TSP for hypercube graphs

Question: what is known about the complexity of finding the Hamilton cycle of minimum weight in graphs that resemble hypercubes with weighted edges?
Manfred Weis's user avatar
  • 12.7k
2 votes
1 answer
113 views

Constructing optimal Hamilton cycles from optimal Hamilton paths

Question: can the shortest Hamilton cycle in a complete symmetric graph with weighted edges be constructed from the shortest Hamilton path in the same graph by connecting its ends and then exchanging ...
Manfred Weis's user avatar
  • 12.7k
0 votes
0 answers
46 views

Approximation factor for TSP Algorithm

The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
Mathematician....'s user avatar
0 votes
0 answers
91 views

Reformulate Traveling Salesman Problem in areas traversed problem

I was wondering whether one has ever considered to reformulate TSP in terms of the areas traversed in either direction. Thus take three initial points of the solution they span a triangle with a ...
ahsalden's user avatar
0 votes
0 answers
13 views

Identifying optimization-potential in weighted Hamilton cycles

From the (possibly incorrect) assumption that inoptimality of weighted Hamilton cycles, that resemble a heuristic solution to a TSP problem, can be identified by calculating the MST (minimum spanning ...
Manfred Weis's user avatar
  • 12.7k
0 votes
0 answers
67 views

Adapting Held–Karp algorithm to visit groups of vertices

The Held–Karp algorithm has exponential time complexity $\Theta\left(2^n n^2\right)$, which is better than brute forcing the TSP which requires $\Theta(n !)$. I'm interesting in amending the Held–Karp ...
Tomi's user avatar
  • 101
1 vote
0 answers
55 views

Knotted Traveling Salesperson route

Let us consider fixed points in space, if we apply the well-known Traveling Salesperson Problem algorithm, we get the shortest route. It can give a nontrivial knot in the three-space. The question is ...
knotMJ's user avatar
  • 71
3 votes
1 answer
153 views

Fastest algorithm for calculating optimal tours in weighted $K_5$

Weighted $K_5$ have the unique property that their edge set can be interpreted as the disjoint union of their shortest and their longest Hamilton cycle. That makes $K_5$ attractive for designing new ...
Manfred Weis's user avatar
  • 12.7k
1 vote
0 answers
90 views

Traveling Salesman: Optimization over cities, not distance

In the classical traveling salesman problem, we are given a graph of cities with distances between each city and are asked to find the shortest path that traverses all of the cities. Meaning that the ...
MathManiac5772's user avatar
-2 votes
2 answers
144 views

Greedy euclidean tour expansion - a case of unexpected hanging?

In the euclidean plane an common heuristic for the TSP is to start with the convex hull of the point set and then successively integrate as the next point and insertion position the combination that ...
Manfred Weis's user avatar
  • 12.7k
0 votes
1 answer
115 views

Traveling salesperson problem algorithm [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...
Ehsan Javanbakht's user avatar
0 votes
2 answers
149 views

References for geometric properties of optimal Euclidean traveling salesman tour

Consider a finite set of points $V \subseteq \mathbb{R}^2 $ as a TSP-instance under the standard $\| \cdot \|_2$ norm. (TSP stands for traveling salesman tour.) We know that every optimal TSP tour $T$ ...
mc.math's user avatar
1 vote
1 answer
104 views

Characterization of greedy TSPs?

Define a greedy tour of a set $S=\{p_1,\ldots,p_n\}$ of $n$ points in $\mathbb{R}^2$ as produced by selecting the $i$-th point $p_i$ to start, and then connecting to the nearest neighbor $p_j$ to $p_i$...
Joseph O'Rourke's user avatar
0 votes
0 answers
26 views

Are there any examples of "autonomous" TSP heuristics

By "autonomous" TSP heuristic I mean algorithms whose reported edge-set for a short Hamilton cycle is invariant under the addition of vertex weights; the terminology is borrowed from ...
Manfred Weis's user avatar
  • 12.7k
1 vote
0 answers
32 views

How to chose the start vector for the MTZ variables

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...
Manfred Weis's user avatar
  • 12.7k
0 votes
0 answers
40 views

Subtour-gluing constraints for ILP formulation of TSPs

If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
Manfred Weis's user avatar
  • 12.7k
1 vote
1 answer
78 views

Do we really need degree constraints for ILP formulations of TSP problems

The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is $$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...
Manfred Weis's user avatar
  • 12.7k
0 votes
0 answers
70 views

TSP on a unitary circle

I am interested in knowing which is the expected length of a random path in a circle. That is, if there are $n$ random points located in the unitary circle $\{(x,y): x^2+y^2\leq 1\}$, what is the ...
user105059's user avatar
0 votes
0 answers
55 views

Degree-constraints for the existence of vertex-disjoint directed cycle covers in digraphs

Given a digraph $G(E,V): (u,v)\in E\implies(v,u)\notin E$, what is known about lower bounds on the indegree and outdegree of the vertices that guarantee the existence of a vertex-disjoint directed ...
Manfred Weis's user avatar
  • 12.7k
1 vote
1 answer
162 views

Could you provide some TSP examples from real world to test a new algorithm?

It's well known that to find a hamilton cycle is NPC, while TSP is NPH. But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...
shen lixing's user avatar
0 votes
0 answers
67 views

Travelling salesman problem with variable weights

Take a fully connected graph with $v$ vertices. We assign weights to edges using an arbitrary function $f_{ij}(x)$ for pairs of vertices $0 < i, j \le v$, then starting at $c_{0}=0$, traverse the ...
George's user avatar
  • 79
-1 votes
1 answer
240 views

Helsgaun's $k$-Opt moves

In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as: with a cycle defined here: which ...
Manfred Weis's user avatar
  • 12.7k
1 vote
1 answer
103 views

$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
Manfred Weis's user avatar
  • 12.7k
0 votes
1 answer
52 views

Relation of 1-trees to optimal tours

Question: given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ ...
Manfred Weis's user avatar
  • 12.7k
3 votes
0 answers
81 views

Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
M. Winter's user avatar
  • 12.6k
0 votes
0 answers
57 views

A variant of travel salesman problem with charging points

Given a graph composed of a set $V$ of nodes, each representing a point to be visited by a salesman, and a set of fixed charging points. The salesman disposes a car that can travel $D$ distance before ...
lchen's user avatar
  • 436
1 vote
1 answer
304 views

Algorithm for multiple travelling salesmen problem with given starting point and end point

Given: Set of n>0 cities is to be traversed by m>0 salespeople Where all the salespeople: Are positioned at the same starting city; Finish at a same destination (which different from starting ...
Nhân's user avatar
  • 11
2 votes
1 answer
175 views

Trying to understand "moats"

According to the TSP Gallery moats provide lower bounds for the optimal solution of TSP instances. On the webpage they are depicted as blue rings around red disks, whose radii represent maximal vertex ...
Manfred Weis's user avatar
  • 12.7k
11 votes
1 answer
399 views

Traveling Salesman Problem on finite group

Given a finite group $H$, define a norm on $H$ to be a function $f : H \rightarrow \mathbb{R}_{\geq 0}$ satisfying: $f(x) = 0 \iff x = e$ is the identity; $\forall x \in H$, we have $f(x) = f(x^{-1})$...
Adam P. Goucher's user avatar
3 votes
1 answer
244 views

What is known about this TSP variant?

Euclidian (planar) TSP asks for a tour with the minimum total length. The problem is known to be NP-hard. I am interested in the variant of finding a closed tour with the minimum enclosed area (...
Mohammad Al-Turkistany's user avatar
9 votes
4 answers
658 views

What would $\mathcal{P} \neq \mathcal{NP}$ tell us about some non-constructive proofs?

Let me sum up my - hopefully correct - understanding of the travelling salesman problem and complexity classes. It's about decision problems: "[...] a decision problem is a problem that can be ...
Hans-Peter Stricker's user avatar
2 votes
1 answer
138 views

Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in "G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
Manfred Weis's user avatar
  • 12.7k
3 votes
0 answers
143 views

Hamiltonian cycle polytope for the hypercube graph

Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ ...
Ozzy's user avatar
  • 383
2 votes
0 answers
118 views

Corporate salesman problem

A salesman is employed by a large corporation. He has a $n$ cities to visit, connected by roads, forming a graph. But as travel takes a lot of time, he has to pick hotels between visits. He cannot ...
kakaz's user avatar
  • 1,596
3 votes
2 answers
1k views

Is there a lower bound for the computational complexity of the traveling salesman problem?

A (non-mathematician) acquaintance of mine recently proposed to me a polynomial-time algorithm for solving the traveling salesman problem. While I was able to point out a flaw in his approach, it did ...
Simon Rose's user avatar
  • 6,240
4 votes
2 answers
410 views

What Kind of Graph is This?

I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph. The overarching rationale is that the reduction is done via a sequence of ...
Manfred Weis's user avatar
  • 12.7k
11 votes
1 answer
819 views

Generalized Euclidean TSP

Suppose I have n sets $X_1,\dots,X_n$ consisting of $k$ points each, where all $nk$ points are i.i.d. uniform random samples in the unit square $[0,1]\times[0,1]$. Consider the shortest path that ...
John Gunnar Carlsson's user avatar