What is known about this TSP variant? This question was cross-posted to cstheory.SE here.


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&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.

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.
Huck Bennett has answered this question on cstheory.SE here.


  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, 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.