Tours

Débora Zupeli Bossois João Olavo Baião de Vasconcelos

1 de março de 2005

1 Testes comparativos TSP

Nesta seção, realizamos testes comparativos para as heurísticas Nearest Neighbor, FRP, Greedy e PQGreedy. Dividimos em três tabelas distintas, que informam o tempo (Tabela 1) e a memória gastos (Tabela 2), e a qualidade do tour (Tabela 3).

Função

Conj. de ptos  NN  FRP  Greedy  PQGreedy
att48  0m0.039s 0m0.038s  0m0.052s  0m0.046s
kroA100  0m0.051s 0m0.050s  0m0.147s  0m0.071s
lin105  0m0.052s 0m0.050s  0m0.154s  0m0.073s
lin318  0m0.086s 0m0.085s  0m3.482s  0m0.246s
linp318  0m0.080s 0m0.084s  0m3.446s  0m0.238s
pr1002  0m0.222s 0m0.238s  1m7.729s  0m0.635s
nrw1379  0m0.315s 0m0.332s  3m46.173s  0m1.309s
pla33810 0m25.161s 0m24.585s (stack overflow) (stack overflow)

Tabela 1: Tempo

Função

Conj. de ptos  NN  FRP  Greedy  PQGreedy
att48  1,113,244 b  1,113,244 b  3,013,780 b  2,695,140 b
kroA100  2,396,416 b  2,396,416 b  15,753,164 b  6,767,764 b
lin105  2,568,920 b  2,568,920 b  17,537,272 b  7,558,516 b
lin318  8,376,768 b  8,376,768 b  322,469,132 b  30,066,568 b
linp318  8,376,768 b  8,376,768 b  322,469,132 b  30,066,568 b
pr1002  27,966,400 b  27,966,400 b  8,751,621,964 b 110,927,624 b
nrw1379  38,321,168 b  38,321,168 b  21,729,092,080 b 151,630,216 b
pla33810 1,818,744,456 bytes 1,818,744,456 bytes (stack overflow) (stack overflow)

Tabela 2: Uso de memória, dado em 10^{6} bytes

Função

Conj. de ptos NN FRP Greedy PQGreedy
att48  1.2089 1.8216 1.1980  1.1980
kroA100  1.2617 1.8874 1.1368  1.1368
lin105  1.4158 1.9016 1.1661  1.1661
pr1002  2.9926 5.0329 2.9218  2.9594

Tabela 3: Qualidade do tour (razão entre o melhor tour possível e o tour da função correspondente)

2 Conclusões

A partir da análise dos testes, podemos observar que as heurísticas Nearest Neighbor e FRP são as melhores em relação ao tempo e memória.