¿Qué se sabe sobre esta variante TSP?

Esta pregunta se publicó anteriormente en Computer Science Stack Exchange aquí .

Imagine que es un vendedor ambulante muy exitoso con clientes en todo el país. Para acelerar el envío, ha desarrollado una flota de drones de entrega desechables, cada uno con un alcance efectivo de 50 kilómetros. Con esta innovación, en lugar de viajar a cada ciudad para entregar sus productos, solo necesita volar su helicóptero dentro de los 50 km y dejar que los drones terminen el trabajo.

Problema: ¿Cómo debe volar su helicóptero para minimizar la distancia de viaje?

Más precisamente, dado un número real y puntos distintos en el plano euclidiano, ¿qué camino que cruza un disco cerrado de radio sobre cada punto minimiza la longitud total del arco? No es necesario que la ruta esté cerrada y puede intersecar los discos en cualquier orden.$R>0$$N$$\{p_1, p_2, \ldots, p_N\}$$R$

Claramente, este problema se reduce a TSP como , por lo que no espero encontrar un algoritmo exacto eficiente. Me gustaría saber cómo se llama este problema en la literatura y si se conocen algoritmos de aproximación eficientes.$R \to 0$

Este es un caso especial del problema del vendedor ambulante con vecindarios (TSPN). En la versión general, los barrios no necesitan ser todos iguales.

Un artículo de Dumitrescu y Mitchell, Algoritmos de aproximación para TSP con vecindarios en el avión , aborda su pregunta. Proporcionan un algoritmo de aproximación de factor constante para un problema un poco más general (caso 1) y un PTAS cuando las vecindades son bolas disjuntas del mismo tamaño (caso 2).

Como comentario adicional, creo que Mitchell ha trabajado mucho en las variantes geométricas de TSP, por lo que es posible que desee ver sus otros documentos.

Una versión relevante de TSP es "Group TSP". En este problema, las "ciudades" se dividen en grupos y el objetivo es encontrar un recorrido que visite a cada grupo al menos una vez.

Esto también se ha estudiado en el avión, que está más cerca de lo que usted describe. Aquí cada grupo es una región cerrada del avión y es suficiente visitar un punto de la región para cubrirlo. Véase, por ejemplo, el documento "Algoritmos de aproximación para Euclidean Group TSP", de Elbassioni et al. en ICALP 2005.