Что известно об этом варианте TSP?

Этот вопрос был ранее размещен на бирже компьютерных наук здесь .

Представьте, что вы очень успешный коммивояжёр с клиентами по всей стране. Чтобы ускорить доставку, вы разработали парк одноразовых доставочных дронов, каждый из которых имеет эффективный радиус действия 50 километров. Благодаря этой инновации, вместо того, чтобы ездить в каждый город, чтобы доставить свой товар, вам нужно всего лишь лететь на вертолете в пределах 50 км и позволить дронам завершить работу.

Проблема: как вы должны управлять своим вертолетом, чтобы минимизировать расстояние в пути?

Точнее, учитывая действительное число и N различных точек { p 1 , p 2 , … , p N } в евклидовой плоскости, какой путь, пересекающий замкнутый диск радиуса R вокруг каждой точки, минимизирует общую длину дуги? Путь не должен быть закрыт и может пересекать диски в любом порядке.$R>0$$N$$\{p_1, p_2, \ldots, p_N\}$$R$

Очевидно, что эта проблема сводится к TSP при , поэтому я не ожидаю найти эффективный точный алгоритм. Я был бы рад узнать, как эта проблема называется в литературе, и если известны эффективные алгоритмы аппроксимации.$R \to 0$

Это особый случай проблемы коммивояжёра с соседями (TSPN). В общем варианте окрестности не обязательно должны быть одинаковыми.

Статья Думитреску и Митчелла, Алгоритмы аппроксимации для TSP с окрестностями на плоскости , отвечает на ваш вопрос. Они дают алгоритм приближения с постоянным множителем для чуть более общей задачи (случай 1) и PTAS, когда окрестности представляют собой непересекающиеся шары одинакового размера (случай 2).

Как побочный комментарий, я думаю, что Митчелл проделал большую работу над геометрическими вариантами TSP, так что вы можете посмотреть его другие статьи.

Одной из соответствующих версий TSP является «Группа TSP». В этой задаче «города» делятся на группы, и цель состоит в том, чтобы найти тур, который посещает каждую группу хотя бы один раз.

Это также было изучено на плоскости, которая ближе к тому, что вы описываете. Здесь каждая группа является замкнутой областью плоскости, и для этого достаточно посетить одну точку в этой области. См., Например, статью «Алгоритмы аппроксимации для TSP Евклидовой группы», Elbassioni et al. в ICALP 2005.