<p>One relevant TSP version is "Group TSP". In this problem, the "cities" are divided into groups and the goal is to find a tour that visits each group at least once. </p>

<p>This has also been studied on the plane, which is closer to what you describe. Here each group is a closed region of the plane and it suffices to visit one point in the region to cover it. See e.g. the paper "Approximation Algorithms for Euclidean Group TSP", by Elbassioni et al. in ICALP 2005.</p>

CC BY-SA 3.0
2015-05-17T17:44:09.453Z
2015-05-17T17:44:09.453Z
Michael Lampis
<p>This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.</p>

<p>A paper by Dumitrescu and Mitchell, <a href="http://www.ams.sunysb.edu/~jsbm/papers/tspn-soda01.pdf">Approximation algorithms for TSP with neighborhoods in the plane</a>, addresses your question. They give a constant factor approximation algorithm for a slightly more general problem (case 1), and a PTAS when the neighborhoods are disjoint balls of the same size (case 2).</p>

<p>As a side comment, I think Mitchell has done a lot of work on geometric TSP variants, so you might want to look at his other papers.</p>

CC BY-SA 3.0
2015-05-17T17:44:29.027Z
2015-05-17T17:44:29.027Z
Huck Bennett
<blockquote>
  <p>This question was previously posted to Computer Science Stack Exchange <a href="https://cs.stackexchange.com/questions/42645/what-is-known-about-this-tsp-variant">here</a>.</p>
</blockquote>

<p>Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.</p>

<p><strong>Problem: How should your fly your helicopter to minimize travel distance?</strong></p>

<p>More precisely, given a real number $R&gt;0$ and $N$ distinct points $\{p_1, p_2, \ldots, p_N\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.</p>

<p>Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.</p>

CC BY-SA 3.0
2015-05-17T22:06:12.743Z
Also posted on [CS.SE](http://cs.stackexchange.com/q/42645/755).
Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration.
D.W.
<ds.algorithms><approximation-algorithms><tsp>
What is known about this TSP variant?
David Zhang
# What is known about this TSP variant?

(Asked by: username_0 on 2015-05-17)

> This question was previously posted to Computer Science Stack Exchange [here](https://cs.stackexchange.com/questions/42645/what-is-known-about-this-tsp-variant).

Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.

**Problem: How should your fly your helicopter to minimize travel distance?**

More precisely, given a real number $R>0$ and $N$ distinct points $\{p\_1, p\_2, \ldots, p\_N\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.

Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.

**Tags:** ds.algorithms, approximation-algorithms, tsp
> **Comments:**
> **username_1**: Also posted on [CS.SE](http://cs.stackexchange.com/q/42645/755). Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration.  

---

## 2 answers

### Answer by username_3 on 2015-05-17. Score: 22 | Accepted answer

This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.

A paper by Dumitrescu and Mitchell, [Approximation algorithms for TSP with neighborhoods in the plane](http://www.ams.sunysb.edu/~jsbm/papers/tspn-soda01.pdf), addresses your question. They give a constant factor approximation algorithm for a slightly more general problem (case 1), and a PTAS when the neighborhoods are disjoint balls of the same size (case 2).

As a side comment, I think Mitchell has done a lot of work on geometric TSP variants, so you might want to look at his other papers.


---

### Answer by username_2 on 2015-05-17. Score: 10

One relevant TSP version is "Group TSP". In this problem, the "cities" are divided into groups and the goal is to find a tour that visits each group at least once.

This has also been studied on the plane, which is closer to what you describe. Here each group is a closed region of the plane and it suffices to visit one point in the region to cover it. See e.g. the paper "Approximation Algorithms for Euclidean Group TSP", by Elbassioni et al. in ICALP 2005.


---

