<p>There was a paper on the arxive last month, dealing with this generalization of the TSP:</p>

<blockquote>
  <p>The multi-stripe travelling salesman problem<br>
  Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger<br>
  (Submitted on 20 Sep 2016)<br>
  <a href="https://arxiv.org/abs/1609.09796" rel="nofollow">https://arxiv.org/abs/1609.09796</a>  </p>
</blockquote>

<p>The problem does not seem to have a particular name in the literature.</p>

CC BY-SA 3.0
2016-10-27T07:44:20.067Z
2016-10-27T07:44:20.067Z
Gamow
<p>Consider a weighted <a href="https://en.wikipedia.org/wiki/Complete_graph" rel="nofollow">graph</a> $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^{th}$ step of the path. (For example, $\sigma_{n+1} = \sigma_1$)</p>

<p>Traveling salesman problem (TSP) minimizes the following objective : $$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}$$</p>

<p>A variant of TSP, <strong>2-Fold TSP</strong>, will additionally consider the weights between the 1-skipped vertices on the path. The objective of a 2-Fold TSP is to minimize</p>

<p>$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}$$</p>

<p>and similarly the objective of <strong>K-fold TSP</strong> is to minimize</p>

<p>$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}+\cdots+w_{\sigma_i,\sigma_{i+k}}$$</p>

<p><strong>Question</strong></p>

<ol>
<li>Can this be reduced to the original TSP?</li>
<li>Is there any reference which deals with k-fold TSP? What is the name of this problem in the literature?</li>
<li>Any heuristics/approximation algorithms?</li>
</ol>

<reference-request><graph-theory><shortest-path><hamiltonian-paths>
K-fold Traveling salesman problem - A variant of TSP
Vivek Bagaria
# K-fold Traveling salesman problem - A variant of TSP

(Asked by: username_0 on 2016-10-27)

Consider a weighted [graph](https://en.wikipedia.org/wiki/Complete_graph) $K\_n$ and where the weights between vertices $i,j$ is $w\_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma\_i$ is the vertex in the $(i\%n)^{th}$ step of the path. (For example, $\sigma\_{n+1} = \sigma\_1$)

Traveling salesman problem (TSP) minimizes the following objective : $$\sum\_{i=1}^{n}w\_{\sigma\_i,\sigma\_{i+1}}$$

A variant of TSP, **2-Fold TSP**, will additionally consider the weights between the 1-skipped vertices on the path. The objective of a 2-Fold TSP is to minimize

$$\sum\_{i=1}^{n}w\_{\sigma\_i,\sigma\_{i+1}}+w\_{\sigma\_i,\sigma\_{i+2}}$$

and similarly the objective of **K-fold TSP** is to minimize

$$\sum\_{i=1}^{n}w\_{\sigma\_i,\sigma\_{i+1}}+w\_{\sigma\_i,\sigma\_{i+2}}+\cdots+w\_{\sigma\_i,\sigma\_{i+k}}$$

**Question**

1. Can this be reduced to the original TSP?
2. Is there any reference which deals with k-fold TSP? What is the name of this problem in the literature?
3. Any heuristics/approximation algorithms?

**Tags:** reference-request, graph-theory, shortest-path, hamiltonian-paths


---

## 1 answers

### Answer by username_1 on 2016-10-27. Score: 1

There was a paper on the arxive last month, dealing with this generalization of the TSP:

> The multi-stripe travelling salesman problem  
> Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger  
> (Submitted on 20 Sep 2016)  
> <https://arxiv.org/abs/1609.09796>

The problem does not seem to have a particular name in the literature.


---

