Questions tagged [traveling-salesman-problem]

Filter by
Sorted by
Tagged with
1 vote
1 answer
55 views

Traveling salesperson problem algorithm

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 ...
0 votes
0 answers
22 views

Simple-path decomposition of random tours

let $V$ denote a set of $n$ vertices, $\lbrace\lbrace v_i,v_j\rbrace\subset V\rbrace$ the set $E$ of edges and $\lbrace\omega_{ij}=\omega_{ji}\in\mathbb{R}:\lbrace i,j\rbrace\mapsto\omega_{ij}\rbrace$ ...
  • 11.4k
0 votes
0 answers
17 views

Complexity of divide&conquer for TSP

It is a known fact that the Held-Karp algorithm that uses Dynamic Programming reduces the complexity of the symmetric TSP with $n$ cities from $O(\frac{(n-1)!}{2})$ for enumerating all tours to $O(2^n\...
  • 11.4k
0 votes
0 answers
30 views

The best of two worlds for TSP heuristics

Let $G$ be a finite, simple graph with weighted edges. The objective of TSP heuristics is to find a Hamilton cycle in $G$ that comes close to the ideal of being the shortest possible. From that ...
  • 11.4k
0 votes
0 answers
28 views

find a path that can maximize the minimum distance in the path in a full mesh graph

I have the following problem. You have a full mesh graph and the link between any two nodes has a certain distance. The question is to find a path that can contain all the nodes and maximize the ...
1 vote
2 answers
90 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$ ...
  • 11
0 votes
0 answers
8 views

Non-optimality of an edge shared between the initial subtour and the optimal cycle cover

Suppose we have an initial tour $T_0$ on which the vertices are encountered in the same order in which they will be encountered on the optimal tour $T_{OPT}$ (in the planar Euclidean case the convex ...
  • 11.4k
1 vote
1 answer
93 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$...
0 votes
0 answers
24 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 ...
  • 11.4k
0 votes
0 answers
14 views

Calculating lower bounds for optimal tours via approximate tours

Let $T=\lbrace t_{i,\pi(i)}\rbrace\subset E,\ S=\lbrace s_{ij}\rbrace =E\setminus T$ denote the set of tour edges, resp. of tour "secants". Let $\lbrace x_{i,\pi(i)}\rbrace \in \lbrace 0,1\...
  • 11.4k
1 vote
0 answers
23 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\\ ...
  • 11.4k
0 votes
0 answers
19 views

MSTs as "connectivity donors" for ILPs of TSPs

Traditionally the constraints that eliminate subtours from the optimal solution of an ILP for a TSP are based on partitions of the vertex set that resemble a $2$-factor of the problem instance. ...
  • 11.4k
0 votes
0 answers
32 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-...
  • 11.4k
1 vote
1 answer
61 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 ...
  • 11.4k
0 votes
0 answers
47 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
39 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 ...
  • 11.4k
0 votes
1 answer
123 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 ...
0 votes
0 answers
39 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 ...
  • 79
-1 votes
1 answer
223 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 ...
  • 11.4k
1 vote
1 answer
74 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 ...
  • 11.4k
0 votes
1 answer
45 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)$ ...
  • 11.4k
3 votes
0 answers
75 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 $...
  • 11k
0 votes
0 answers
48 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 ...
  • 439
1 vote
1 answer
178 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 ...
  • 11
2 votes
1 answer
162 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 ...
  • 11.4k
1 vote
0 answers
168 views

Mathematical problems reducing to the traveling salesman problem

The superpermutation problem is: what is the shortest word that contains every permutation of $k$ letters as a substring. This can phrased as a Travelling Salesman Problem, where the nodes of your ...
11 votes
1 answer
371 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})$...
3 votes
1 answer
229 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 (...
9 votes
4 answers
600 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 ...
2 votes
1 answer
134 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 ...
  • 11.4k
3 votes
0 answers
133 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$ ...
  • 373
2 votes
0 answers
116 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,580
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 ...
  • 6,162
4 votes
2 answers
391 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 ...
  • 11.4k
11 votes
1 answer
782 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 ...