O Problema do Caixeiro Viajante

Solucao com o algoritmo VNS

O problema do caixeiro viajante é um problema de otimização que consiste em encontrar o menor caminho para percorrer todas as cidades em uma instância de cidades dada e retornar a cidade inicial do percurso. Só é possível passar por uma cidade uma única vez no percurso.

Figura 1. Exemplo de caminho em uma instância e estrutura do vetor de percurso
Figura 1. Exemplo de caminho em uma instância e estrutura do vetor de percurso

O algoritmo criado no projeto inclui algumas heurísticas e variações da idéia original do algoritmo VNS. Estas heurísticas foram implementadas com o intuito de melhorar os resultados obtidos. Algumas heurísticas foram testadas no início do desenvolvimento e logo depois foram descartadas, pois não se encaixaram bem no algoritmo final que foi criado, não ajudando na melhora dos resultados. O algoritmo desenvolvido segue as seguintes etapas:

                                i.            Um caminho aleatório é criado, contendo um percurso completo da instância do problema.

                              ii.            Uma busca, a partir da primeira cidade, tenta encontrar o vizinho mais próximo da cidade corrente K. Este vizinho é posicionado na frente desta cidade, na posição K+1. Uma nova busca é feita a partir deste vizinho K+1, procurando, entre as cidades restantes, o seu vizinho mais próximo. A busca continua até que todas as cidades tenham sido posicionadas. Está é a solução inicial.

                            iii.             A partir da solução inicial criada, tentativas de melhora no resultado são aplicadas a cada iteração do algoritmo. Cada heurística aplicada no caminho só é aceita caso haja melhora na solução. Primeiro, um vizinho aleatório é escolhido e uma busca é feita procurando seu vizinho mais próximo, o posicionamento deste vizinho deve melhorar a solução.

                            iv.            Em seguida, uma cidade aleatória é instanciada por um trecho do caminho (escolhido aleatoriamente).

Figura 2.A cidade 3 foi escolhida para ser instanciada no percurso entre as cidades 2 e 7.
Figura 2.A cidade 3 foi escolhida para ser instanciada no percurso entre as cidades 2 e 7.

 A cidade é movimentada até que a solução melhore ou o percurso sobre este trecho do caminho acabe (se não houver melhora, o caminho inicial é mantido).

Figura 3. Neste caso, a cidade 3 entre as cidades 6 e 7 indica uma melhora na solução.
Figura 3. Neste caso, a cidade 3 entre as cidades 6 e 7 indica uma melhora na solução.

 

                                v.            No próximo passo é aplicado o 2-swap para todas as cidades com uma cidade aleatória que esteja a sua frente no caminho. A troca só acontece quando houver melhora.

                              vi.            2-opt é realizado no caminho, selecionando cidades aleatórias para a execução da troca e reposicionamento no caminho de solução.

 

            Após um número de iterações (definido no código) sem melhora, é aplicada uma heurística que faz o 2-opt e, dentro do trecho da solução onde será realizado o 2-opt, o 2-opt é executado novamente. È uma operação similar ao 3-opt (mas não tão eficiente), mas que é feita em O(n2).

Relatório de Testes

 

Instâncias 

MELHOR SOLUÇÃO

Solução Média

Pior Solução

SOLUÇÃO ÓTIMA DA LITERATURA

Distância da Solução Ótima

Tempo da solução encontrada

Tempo médio

Tempo máximo

bayg29

1610

1647

1702

1610

OTIMO

0 seg

2 seg

10 seg

att48

10610

11280

11299

10324

2,7702%

1 seg

1 seg

5 min

berlin52

7542

8168

8774

7542

OTIMO

0 seg

0 seg

10 seg

brazil58

25395

26625

28527

25395

OTIMO

0 seg

7 seg

5 min

eil76

546

567

586

538

1,4870%

2 seg

1 seg

5 min

kroA100

21282

23069

25849

21282

OTIMO

6 seg

5 seg

5 min

kroB100

22373

23678

24819

22141

1,0478%

3 seg

3 seg

1 min

lin105

14707

15387

16855

14379

2,2811%

13 seg

15 seg

1 min

bier127

121156

123652

12632

118282

2,4298%

48 seg

26 seg

5 min

pr144

58861

62699

72448

58537

0,5535%

35 seg

34 seg

5 min

ch150

6646

6965

7326

6528

1,8076%

10 seg

15 seg

1 min

kroB150

26809

28463

27667

26130

2,5985%

29 seg

31 seg

1 min

pr152

75656

77669

79351

73682

2,6791%

44 seg

31 seg

1 min

brg180

1950

4320

11050

1950

OTIMO

0 seg

5 seg

10 seg

d198

16388

17304

18512

15780

3,8530%

1 min 12 seg

1 min 2 seg

2 min

gr202

42692

44320

44738

40160

6,3048%

7 min 32 seg

7 min 36 seg

15 min

pr264

52182

54445

57817

49135

6,2013%

5 min 5 seg

4 min 10 seg

6 min

pr299

51886

53153

55477

48191

7,6674%

2 min 36 seg

3 min  19 seg

5 min

gr431

187344

193788

202590

171414

9,2933%

29 min 36 seg

28min 49 seg

30 min

rat575

7133

7625

8523

6773

5,3152%

26 min 25 seg

27min 12 seg

30 min

Documentação

 

Documentacao gerada com doxygen pode ser encontrada aqui.

 

 

Download
TSP-VNS
VNS.rar
compressed file archive 462.1 KB
Download

Sugestões e Comentários

Write a comment

Comments: 1

Visite: