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