Questions tagged [traveling-salesman-problem]
The traveling-salesman-problem tag has no usage guidance.
21
questions with no upvoted or accepted answers
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 $...
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$ ...
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 ...
1
vote
0
answers
51
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 ...
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?
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 ...
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 ...
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\\ ...
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 ...
0
votes
0
answers
24
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 ...
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 ...
0
votes
0
answers
90
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 ...
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 ...
0
votes
0
answers
64
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 ...
0
votes
2
answers
137
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$ ...
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 ...
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-...
0
votes
0
answers
69
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 ...
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 ...
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 ...
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 ...