O que se sabe sobre essa variante TSP?

15

Esta questão foi postada anteriormente em Computer Science Stack Exchange aqui .

Imagine que você é um vendedor ambulante de muito sucesso, com clientes em todo o país. Para acelerar o envio, você desenvolveu uma frota de drones descartáveis ​​de entrega, cada um com um alcance efetivo de 50 quilômetros. Com essa inovação, em vez de viajar para cada cidade para entregar suas mercadorias, você só precisa pilotar seu helicóptero dentro de 50 km e deixar que os drones terminem o trabalho.

Problema: Como você deve pilotar seu helicóptero para minimizar a distância de viagem?

Mais precisamente, dado um número real e N pontos distintos { p 1 , p 2 , … , p N } no plano euclidiano, qual caminho que intercepta um disco fechado de raio R sobre cada ponto minimiza o comprimento total do arco? O caminho não precisa ser fechado e pode cruzar os discos em qualquer ordem.R>0N{p1,p2,…,pN}R

Claramente, esse problema se reduz a TSP como , portanto, não espero encontrar um algoritmo exato eficiente. Eu ficaria satisfeito em saber como esse problema é chamado na literatura e se algoritmos de aproximação eficientes são conhecidos.R→0

ds.algorithms approximation-algorithms tsp David Zhang
fonte
1
Também postado em CS.SE . Por favor, não postar a mesma pergunta em vários sites . Cada comunidade deve ter uma chance honesta de responder sem perder tempo com ninguém. Se você não receber uma resposta satisfatória depois de uma semana, fique à vontade para sinalizar a migração.
DW

Respostas:

21

Este é um caso especial do problema do Vendedor ambulante com bairros (TSPN). Na versão geral, os bairros não precisam ser todos iguais.

Um artigo de Dumitrescu e Mitchell, Algoritmos de aproximação para TSP com vizinhanças no avião , aborda sua pergunta. Eles fornecem um algoritmo de aproximação de fator constante para um problema um pouco mais geral (caso 1) e um PTAS quando as vizinhanças são bolas disjuntas do mesmo tamanho (caso 2).

Como um comentário lateral, acho que Mitchell fez muito trabalho em variantes geométricas de TSP, então você pode querer olhar para os outros trabalhos dele.

Huck Bennett
fonte
10

Uma versão relevante do TSP é "Group TSP". Nesse problema, as "cidades" são divididas em grupos e o objetivo é encontrar um passeio que visite cada grupo pelo menos uma vez.

Isso também foi estudado no avião, mais próximo do que você descreve. Aqui cada grupo é uma região fechada do avião e basta visitar um ponto da região para cobri-lo. Veja, por exemplo, o artigo "Algoritmos de Aproximação para TSP do Grupo Euclidiano", de Elbassioni et al. no ICALP 2005.

Michael Lampis
fonte