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

15

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

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

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

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

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

Дэвид Чжан
источник
1
Также размещены на CS.SE . Пожалуйста , не размещайте один и тот же вопрос на нескольких сайтах . Каждое сообщество должно иметь честный ответ, не теряя никого времени. Если вы не получите удовлетворительного ответа через неделю или около того, не стесняйтесь помечать для миграции.
DW

Ответы:

21

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

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

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

Гек Беннетт
источник
10

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

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

Майкл Лэмпис
источник