Skip to content

implementation of constructive and improvement heuristics for the Travelling Salesman Problem

Notifications You must be signed in to change notification settings

renanleonel/tsp-heuristics

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Trabalho realizado na disciplina de Modelagem e Otimização Algorítmica

implementação de algoritmos heurísticos de construção e de melhoramento para o problema do Caixeiro Viajante (PCV), utilizando as heurísticas construtivas vizinho mais próximo e inserção aleatória, assim como as heurísticas melhorativas 2-opt e 3-opt.
detalhes sobre a implementação podem ser encontrados no arquivo "relatório.pdf"
1- As entradas são feitas pelo terminal, copie e cole a entrada completa igual dos exemplos;
2- A entrada precisam acabar em EOF e não ter espaço em branco após o EOF ou o programa não vai executar;
3- Compile com g++ "nomedoarquivo.cpp" e executo com ./a.out, no caso ja estão compilados, entao deve se executar o comando ./"nomedoarquivocompilado" ;
4- Em cada pasta tem seu algoritmo equivalente ao seu nome;
5- Os arquivos que devem ser avaliados no runcodes estão na pasta "arquivosRunCodes", eles possuem apenas uma saida, diferente dos outros arquivos, que escrevem na tela o custo do caminho do algoritmo construtor e do melhorativo;
6- Os arquivos com subnome de "adaptacao" podem ter sem tempo de execução e tentativas de melhoramento alterados no topo do código, em suas constantes;
7- Os dois algoritmos da pasta "arquivosRunCodes" estão ajustados para tentar melhorar 5 vezes e com um tempo maximo de 10 segundos de execução, já os outros, estão ajustados para 5 tentativas e com um limite de 5 minutos de execução. Esses dois parâmetros podem ser ajustados nas constantes logo no começo do código;

About

implementation of constructive and improvement heuristics for the Travelling Salesman Problem

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages