Tenho cerca de 300 endereços em uma cidade e estou tentando encontrar um software que possa resolver o problema do vendedor ambulante. Tentei o OptiMap, uma solução baseada em navegador que usa a API do Google, mas está limitada a 100 destinos (mesmo quando você altera limites codificados) e os navegadores que tento acabam ficando sem memória. Eu sei que o problema é NP difícil, mas este não é um problema novo, certamente alguém já escreveu um software. As únicas soluções comerciais que vi são baseadas nos EUA (é uma cidade australiana) ou têm limites baixos.
Existe software comercial ou gratuito para realizar essa tarefa e seu tamanho?
software-rec
calculator
user348998
fonte
fonte
Respostas:
Não é exatamente "gratuito" - mas talvez implemente o algoritmo de aproximação para TSP descrito neste livro .
IIRC, fornece um TSP de solução para gráficos planares um fator 2 dentro da solução ideal.
fonte