GeogInfo (Tópicos de Geografia e Informática)

	Tours de instâncias de teste (ainda em aberto)

O Problema do Caixeiro Viajante (Traveling Salesman Problem) atrai muitos pesquisadores devido, em parte, aos seus desafios, suas aplicações, e também devido ao seu enunciado simples (de fácil entendimento) e ao grande número de publicações sobre o tema (em livros, artigos de periódicos, em sites na internet...). Existem sites que abordam o problema de maneira ampla, disponibilizando informações sobre a história do problema, suas aplicações, estratégias de resolução, etc... Dentre eles podemos citar a página mantida pelo Prof. William Cook:
The Traveling Salesman Problem
http://www.math.uwaterloo.ca/tsp/ (acesso em 04/03/2014)
Na página mencionada, temos um link Test Data que aponta para uma região contendo instâncias (amostras, exemplos) para testes. Essas "amostras" são utilizadas por diversos pesquisadores e a partir delas podemos verificar se a estratégia na qual estamos trabalhando está sendo promissora ou não (basta comparar os resultados).
Um fato curioso é que existem instâncias consideradas pequenas, para as quais ainda não foi encontrada uma solução ótima. Existem algoritmos eficientes, capazes de resolver instâncias grandes de {15112, 24978, 85900} vértices (pontos) de maneira exata, ou seja, encontrando a/uma solução ótima. O interessante é que essas estratégias ainda não foram capazes de resolver algumas pequenas instâncias, de tamanhos variando entre 2000 e 4000 vértices, de maneira exata. A tabela seguinte apresenta exemplos dessas "pequenas notáveis" !

TSP Test Data - VLSI TSP Collection

Instância	Gap	Bound	Tour	Source	Nosso Objetivo
dea2382	x.x%	xxx	8017	LKH	Ok - tour abaixo
bch2762	x.x%	xxx	8234	LKH	Ok - tour abaixo
lsm2854	x.x%	xxx	8014	LKH	Ok - tour abaixo
xva2993	x.x%	xxx	8492	LKH	Ok - tour abaixo
dke3097	x.x%	xxx	10539	LKH	Ok - tour abaixo
lsn3119	x.x%	xxx	9114	LKH	Ok - tour abaixo
lta3140	x.x%	xxx	9517	LKH	Ok - tour abaixo
fdp3256	x.x%	xxx	10008	LKH	Ok - tour abaixo
beg3293	x.x%	xxx	9772	LKH	Ok - tour abaixo
dhb3386	x.x%	xxx	11137	LKH	Ok - tour abaixo
fjs3649	x.x%	xxx	9272	LKH	Ok - tour abaixo
fjr3672	x.x%	xxx	9601	LKH	Ok - tour abaixo
ltb3729	x.x%	xxx	11821	LKH	Ok - tour abaixo
xua3937	x.x%	xxx	11239	LKH	Pendente - nosso valor: 11242
dkc3938	x.x%	xxx	12503	LKH	Ok - tour abaixo
dkf3954	x.x%	xxx	12538	LKH	Pendente - nosso valor: 12539

Fonte: http://www.math.uwaterloo.ca/tsp/vlsi/summary.html (acesso em 04/03/2014)
Obs: LKH -> Implementação da heurística de Lin-Kernighan (pelo Prof. Keld Helsgaun)
x.x% indica que ainda não sabemos se esse valor é ótimo e nem a que porcentagem estamos da solução ótima...

Observando as páginas dessas instâncias, notei que algumas delas não apresentavam o "circuito resposta" (o tour), o arquivo contendo a solução. Como esses resultados foram reportados há muito tempo, imagino que os pesquisadores esqueceram de acrescentar os arquivos das respectivas soluções.
Pensando nisso, dediquei um tempo para encontrar e disponibilizar alguns desses "arquivos resposta". As soluções (tours) apresentadas nessa página foram obtidas a partir do "cruzamento" de sementes (soluções, tours) geradas pela implementação da heurística de Lin e Kernighan incluída no software Concorde (disponível no site do tsp). As sementes coletadas passam por processos de melhoria e em seguida são mescladas com outras sementes, na tentativa de obter uma solução de melhor qualidade.
Para acessar os arquivos contendo os "circuitos resposta" (tours), basta clicar sobre os links nas células abaixo. As escalas das figuras foram alteradas para o desenho se espalhar ocupando toda a área da tela do simulador (quadrado).

dea2382