Questions tagged [traveling-salesman-problem]

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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.5k
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
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 ...
whiterock's user avatar
  • 111
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.6k
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
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
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.6k
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.6k
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 ...
Manfred Weis's user avatar
  • 12.6k
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
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 ...
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.6k
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 ...
Tomi's user avatar
  • 101
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$ ...
mc.math'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.6k
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.6k
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 ...
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.6k
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
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
  • 459