Co wiadomo o tym wariancie TSP?

To pytanie zostało wcześniej opublikowane w Computer Science Stack Exchange tutaj .

Wyobraź sobie, że jesteś odnoszącym sukcesy podróżnym sprzedawcą z klientami w całym kraju. Aby przyspieszyć wysyłkę, opracowałeś flotę dronów jednorazowego użytku o efektywnym zasięgu 50 kilometrów. Dzięki tej innowacji zamiast podróżować do każdego miasta w celu dostarczenia towarów, wystarczy przelecieć helikopterem w promieniu 50 km i pozwolić dronom dokończyć robotę.

Problem: Jak latać helikopterem, aby zminimalizować odległość podróży?

Dokładniej, biorąc pod uwagę liczbę rzeczywistą i N odrębnych punktów w płaszczyźnie euklidesowej, która ścieżka przecinająca zamknięty dysk o promieniu wokół każdego punktu minimalizuje całkowitą długość łuku? Ścieżka nie musi być zamknięta i może przecinać dyski w dowolnej kolejności.$R>0$$N$$\{p_1, p_2, \ldots, p_N\}$$R$

Oczywiście ten problem ogranicza się do TSP jako , więc nie oczekuję, że znajdę skuteczny dokładny algorytm. Z przyjemnością dowiem się, jak nazywa się ten problem w literaturze i czy znane są skuteczne algorytmy aproksymacyjne.$R \to 0$

Jest to szczególny przypadek problemu Traveling Salesman with Neighborhoods (TSPN). W wersji ogólnej dzielnice nie muszą być takie same.

Artykuł Dumitrescu i Mitchella, Algorytmy aproksymacyjne dla TSP z okolicami samolotu , odpowiada na twoje pytanie. Dają stały algorytm aproksymacji współczynnika dla nieco bardziej ogólnego problemu (przypadek 1) oraz PTAS, gdy sąsiedztwa są rozłącznymi kulkami tego samego rozmiaru (przypadek 2).

Na marginesie, myślę, że Mitchell wykonał wiele pracy nad geometrycznymi wariantami TSP, więc warto przyjrzeć się jego innym artykułom.

Jedną z istotnych wersji TSP jest „Group TSP”. W tym problemie „miasta” są podzielone na grupy, a celem jest znalezienie wycieczki, która odwiedza każdą grupę co najmniej raz.

Zostało to również zbadane na płaszczyźnie, która jest bliższa temu, co opisujesz. Tutaj każda grupa jest zamkniętym regionem samolotu i wystarczy odwiedzić jeden punkt w regionie, aby go objąć. Patrz np. Artykuł „Algorytmy aproksymacji dla grupy Euclidean TSP”, Elbassioni i in. w ICALP 2005.