Existem vendedores ambulantes inteligentes?

Brincadeiras à parte, tive um problema de roteamento que é quase um problema de vendedor ambulante (TSP):

• o ponto de partida é definido
• o ponto final coincide com o ponto inicial
• cada nó deve ser visitado
• o custo total deve ser minimizado

Dois anos atrás, eu pensei que o TSP seria uma combinação perfeita, então eu executei alguns dados de amostra no tsp_solveConcorde. Felizmente, ficou rapidamente óbvio que o caminho mais curto do TSP não é o caminho mais curto real , já que o problema é facilitado ao exigir de forma irrealista que os nós sejam visitados exatamente uma vez . Essa imagem é apenas uma tentativa manual de uma etapa de otimização da solução computada e já economiza a distância da borda mais longa usada.

O problema ressurgiu, pois estou tentando encontrar rotas ideais para subconjuntos de sites de mapeamento / monitoramento. Os dados de localização e rede de estradas são bastante precisos e precisos; portanto, um exercício como esse faz sentido.

Eu olhei para generalizações do TSP, mas não encontrei um algoritmo apropriado. As árvores de extensão mínima não são responsáveis ​​pelo retorno dos galhos (a primeira solução aqui custa mais 3). Pelo que entendi, o problema do caminho mais curto eventualmente se preocupa apenas com dois nós e os que estão fora do caminho ideal seriam deixados de fora. Um caso especial do problema de roteamento de veículos parece se encaixar melhor, embora eu não saiba se considera caminhos não diretos.

Minha pergunta: existe algum nome definido, definição para esse tipo de problema (família)? Qual algoritmo e ferramenta você usaria para resolvê-lo?

Tenho certeza de que seria computacionalmente pesado, mas estou interessado em respostas gerais (recursos infinitos) e práticas.

Este é o TSP . Você apenas não definiu uma métrica de distância válida porque ela não satisfaz a desigualdade do triângulo: se houver uma rota de A a C a B que seja menor que a distância declarada de A a C, então a distância declarada de A a C é simplesmente errado. A solução é atualizar a matriz de distância definindo o comprimento de A a C para ser o menor comprimento de todas as rotas de A a C.