O vizinho mais próximo e mais solitário de dois lados - uma variação da heurística do vizinho mais próximo para o problema do caixeiro viajante

Resumo

Este artigo apresenta uma nova heurística para o problema do caixeiro viajante que introduz o conceito de solidão de uma cidade - calculada como a distância média dessa cidade a todas as outras - e o combina com ideias de outras variações de heurísticas do vizinho mais próximo. Tendo a mesma complexidade das heurísticas de vizinho mais próximo mais rápidas, o novo método conduz a melhores resultados que estas heurísticas, ultrapassando igualmente várias outras heurísticas reportadas na literatura. Uma característica interessante da heurística proposta é que dá prioridade a localizações mais isoladas na definição de rotas. A antecipação da distribuição de bens e serviços a localizações mais periféricas pode ser considerada uma externalidade social positiva, tornando a heurística passível de adopção por determinadas entidades por razões não meramente económicas mas também sociais.