Prévia do material em texto
Avaliação 1 1 0 8 1 4 Departamento de Engenharia de Produção 1 0 7 9 9 1 Disciplina: Meta-heurísticas aplicadas à Engenharia de Produçao Prof. Gilberto Clóvis Antonelli Integrantes da Equipe RA Mariana Néspoli de Melo 110814 17 Camila Rafael 107991 COLONIA DE FORMIGAS Determine a sequência de locais as serem visitados pelo robô de modo a minimizar a distância percorrida. Para esse cálculo utilize o método heurístico 1ª Avaliação - Parte Prática Determine a sequência de locais as serem visitados pelo robô de modo a minimizar a distância percorrida. Para esse cálculo utilize o método heurístico COLONIA DE FORMIGAS. A tabela abaixo indica as distâncias aproximadas, em milhas, entre oito locais de Marte, onde cientistas da NASA pensam haver maior probabilidade de encontrar vestígios de vida. (OBS: ANTES DE INICIAR PREENCHA OS DADOS DOS MEMBROS DA EQUIPE) A G H I N P W S A 0 18 50 18 99 83 91 102 G 72 0 106 99 23 19 84 98 H 150 53 0 50 60 12 37 3 I 72 33 75 0 83 66 63 14 N 297 46 40 55 0 29 17 22 P 249 19 6 33 58 0 28 53 W 273 84 37 31 8 28 0 33 S 306 196 1 14 11 106 16 0 Quer-se planejar uma viagem que colocará um robô em Marte. O robô deverá percorrer cada um dos locais, recolher amostras de solo e regressar ao ponto inicial, de onde um foguetão trará as amostras para a Terra de forma a serem analisadas. Determine a sequência de locais as serem visitados pelo robô de modo a minimizar a distância percorrida. Para esse cálculo utilize o método heurístico COLONIA DE FORMIGAS. OBSERVAÇÃO: Preencha primeiramente os dados da equipe para a definição das informações da tabela. Deverá ser entregue na forma escrita todas as iterações utilizadas para resolver o problema, bem como a apresentação dos parâmetros utilizados. ESTA PAGINA DEVE SER PREENCHIDA E ENTREGUE JUNTO COM A RESOLUÇÃO DO PROBLEMA Solução Definicao dos parametros e metodos Tabela de probabilidade Caminhos das formigas 1 ITERACAO Atualizacao da tabela de feromonio Tabela de probabilidade Caminhos das formigas 2 ITERACAO 428 207 275 235 777 399 580 551 Parametros α = 1 Foram feitas tabelas com a probabilidade de cada caminho em ambas as iteracoes conforme a formula já prevista no metodo Ant Colony 1 iteracao Caminho Distancia Caminhos Formigas 2 iteracao Caminho Distancia β = 1 Partida Chegada Distância Inverso da distância (T) Feromônio (n) n*T Probabilidade (p) % FORMIGA 1 AGPHSIWNA 428 Partida Chegada Feromônio (n) 1 2 3 4 5 6 7 8 Feromonio att (n) Partida Chegada Distância Inverso da distância (T) Feromônio (n) n*T Probabilidade (p) % FORMIGA 1 APWISHNGA 335 A G 18 0.0555555556 0.1 0.006 0.3191871261 31.9% Partida Chegada % % Acumulado valor aleatorio A G 0.099 0.0420560748 0.0869565217 0.2280125965 A G 18 0.0555555556 0.2280125965 0.013 0.3197004752 32.0% Partida Chegada % % Acumulado valor aleatorio Coeficiente de evaporacao ơ ou ρ = 0,01 A H 50 0.02 0.1 0.002 0.1149073654 11.5% A G 31.9% 31.9% 16 A H 0.099 0.099 A H 50 0.02 0.099 0.002 0.0499714714 5.0% A G 32.0% 32.0% 74 A I 18 0.0555555556 0.1 0.006 0.3191871261 31.9% A H 11.5% 43.4% A I 0.099 0.0765957447 0.1755957447 A I 18 0.0555555556 0.1755957447 0.010 0.2462058846 24.6% A H 5.0% 37.0% Feromonio inicial ŋ = 0,1 A N 99 0.0101010101 0.1 0.001 0.0580340229 5.8% A I 31.9% 75.3% A N 0.099 0.1274131274 0.2264131274 A N 99 0.0101010101 0.2264131274 0.002 0.0577196057 5.8% A I 24.6% 61.6% (Todas as formigas depositaram feromonio no metodo utilizado) A P 83 0.0120481928 0.1 0.001 0.0692213045 6.9% A N 5.8% 81.1% A P 0.099 0.3018181818 0.2080200501 0.6088382319 A P 83 0.0120481928 0.6088382319 0.007 0.1851316921 18.5% A N 5.8% 67.4% Constante de atualizacao do feromonio Q = 10 A W 91 0.010989011 0.1 0.001 0.0631359151 6.3% A P 6.9% 88.1% A W 0.099 0.1568965517 0.2558965517 A W 91 0.010989011 0.2558965517 0.003 0.070970847 7.1% A P 18.5% 85.9% (taxa alta para compensar o numero baixo de iteracoes) A S 102 0.0098039216 0.1 0.001 0.0563271399 5.6% A W 6.3% 94.4% A S 0.099 0.1851179673 0.2841179673 A S 102 0.0098039216 0.2841179673 0.003 0.0703000241 7.0% A W 7.1% 93.0% Numero de formigas m = 8 G A 72 0.0138888889 0.1 0.001 0.0915896586 9.2% A S 5.6% 100.0% G A 0.099 0.2618181818 0.3063829787 0.6672011605 G A 72 0.0138888889 0.6672011605 0.009 0.2477461139 24.8% A S 7.0% 100.0% (numero base para cada formiga sair de um local diferente) E a atualizacao realizada nos feromonios tambem seguiu a seguinte formula do metodo G H 106 0.0094339623 0.1 0.001 0.0622118436 6.2% Partida Chegada % % Relativa % Acumulado G H 0.099 0.099 G H 106 0.0094339623 0.099 0.001 0.0249696172 2.5% Partida Chegada % % Relativa % Acumulado Numero de iteracoes n = 2 G I 99 0.0101010101 0.1 0.001 0.0666106608 6.7% G H 6.2% 6.8% 6.8% 65 G I 0.099 0.1274131274 0.2481203008 0.4745334282 G I 99 0.0101010101 0.4745334282 0.005 0.1281486901 12.8% P G 16.0% 16.5% 16.5% 81 G N 23 0.0434782609 0.1 0.004 0.286715453 28.7% G I 6.7% 7.3% 14.2% G N 0.099 0.1111111111 0.0396551724 0.0417422868 0.2915085703 G N 23 0.0434782609 0.2915085703 0.013 0.3388488732 33.9% P H 48.9% 50.5% 67.0% A G G P 19 0.0526315789 0.1 0.005 0.347076601 34.7% G N 28.7% 31.6% 45.7% G P 0.099 0.0443925234 0.1433925234 G P 19 0.0526315789 0.1433925234 0.008 0.2017694735 20.2% P I 5.5% 5.7% 72.7% G W 84 0.0119047619 0.1 0.001 0.0785054217 7.9% G P 34.7% 38.2% 84.0% G W 0.099 0.099 G W 84 0.0119047619 0.099 0.001 0.0315092788 3.2% P N 3.1% 3.2% 75.9% G S 98 0.0102040816 0.1 0.001 0.0672903614 6.7% G W 7.9% 8.6% 92.6% G S 0.099 0.099 G S 98 0.0102040816 0.099 0.001 0.0270079533 2.7% P W 15.3% 15.8% 91.7% H A 150 0.0066666667 0.1 0.001 0.0131779664 1.3% G S 6.7% 7.4% 100.0% H A 0.099 0.099 H A 150 0.0066666667 0.099 0.001 0.0091065965 0.9% P S 8.0% 8.3% 100.0% H H G 53 0.0188679245 0.1 0.002 0.0372961313 3.7% Partida Chegada % % Relativa % Acumulado H G 0.099 0.099 H G 53 0.0188679245 0.099 0.002 0.0257733862 2.6% Partida Chegada % % Relativa % Acumulado S H I 50 0.02 0.1 0.002 0.0395338992 4.0% P H 51.2% 62.0% 62.0% 53 H I 0.099 0.0862068966 0.0907441016 0.2759509982 H I 50 0.02 0.2759509982 0.006 0.076150739 7.6% W G 2.4% 2.8% 2.8% 20 H N 60 0.0166666667 0.1 0.002 0.032944916 3.3% P I 9.3% 11.3% 73.3% H N 0.099 0.099 H N 60 0.0166666667 0.099 0.002 0.0227664912 2.3% W H 5.5% 6.4% 9.2% H P 12 0.0833333333 0.1 0.008 0.1647245798 16.5% P N 5.3% 6.4% 79.7% H P 0.099 0.0579710145 0.1569710145 H P 12 0.0833333333 0.1569710145 0.013 0.1804888494 18.0% W I 16.5% 19.2% 28.5% H W 37 0.027027027 0.1 0.003 0.0534241881 5.3% P W 11.0% 13.3% 93.0% H W 0.099 0.1345454545 0.0927318296 0.3262772841 H W 37 0.027027027 0.3262772841 0.009 0.1216738561 12.2% W N 51.5% 60.2% 88.7% H S 3 0.3333333333 0.1 0.033 0.6588983193 65.9% P S 5.8% 7.0% 100.0% H S 0.099 0.0070093458 0.0127659574 0.0038610039 0.1226363071 H S 3 0.3333333333 0.1226363071 0.041 0.5640400817 56.4% W S 9.7% 11.3% 100.0% I I A 72 0.0138888889 0.1 0.001 0.0807368925 8.1% Partida Chegada % % Relativa % Acumulado I A 0.099 0.347826087 0.1804511278 0.6272772148 I A 72 0.0138888889 0.6272772148 0.009 0.2209982093 22.1% Partida Chegada % % Relativa % Acumulado W I G 33 0.0303030303 0.1 0.003 0.17615322 17.6% H I 4.0% 5.1% 5.1% 91 I G 0.099 0.12 0.219 I G 33 0.0303030303 0.219 0.007 0.1683417794 16.8% I G 16.8% 40.9% 40.9% 69 I H 75 0.0133333333 0.1 0.001 0.0775074168 7.8% H N 3.3% 4.2% 9.3%I H 0.099 0.099 I H 75 0.0133333333 0.099 0.001 0.0334838717 3.3% I H 3.3% 8.1% 49.1% I N 83 0.0120481928 0.1 0.001 0.0700368224 7.0% H W 5.3% 6.8% 16.1% I N 0.099 0.099 I N 83 0.0120481928 0.099 0.001 0.0302565106 3.0% I N 3.0% 7.4% 56.4% *Os caminhos possuem tamanhos diferentes dependendo da posicao I P 66 0.0151515152 0.1 0.002 0.08807661 8.8% H S 65.9% 83.9% 100.0% I P 0.099 0.2808510638 0.1137931034 0.1197822142 0.6134263814 I P 66 0.0151515152 0.6134263814 0.009 0.2357654991 23.6% I S 17.9% 43.6% 100.0% P N I W 63 0.0158730159 0.1 0.002 0.0922707343 9.2% Partida Chegada % % Relativa % Acumulado I W 0.099 0.1471962617 0.0810810811 0.3272773428 I W 63 0.0158730159 0.3272773428 0.005 0.1317762454 13.2% Partida Chegada % % Relativa % Acumulado 2 -> 3 difere de 3 -> 2 I S 14 0.0714285714 0.1 0.007 0.4152183042 41.5% S I 5.7% 31.7% 31.7% 24 I S 0.099 0.099 I S 14 0.0714285714 0.099 0.007 0.1793778844 17.9% S G 1.2% 1.5% 1.5% 22 N A 297 0.0033670034 0.1 0.000 0.0162618842 1.6% S N 7.3% 40.6% 72.2% N A 0.099 0.6939252336 0.5120689655 1.3049941992 N A 297 0.0033670034 1.3049941992 0.004 0.1024482469 10.2% S H 75.6% 91.1% 92.5% N G 46 0.0217391304 0.1 0.002 0.1049952087 10.5% S W 5.0% 27.8% 100.0% N G 0.099 0.1957446809 0.1152882206 0.4100329014 N G 46 0.0217391304 0.4100329014 0.009 0.2078324102 20.8% S N 6.2% 7.5% 100.0% Os caminhos foram escolhidos por numeros aleatorios gerados entre 0 e 100 a cada esquina por meio de porcentagens ajustadas entre os caminhos remanescentes e os resultados obtidos foram destacados nas tabelas. Os caminhos e as distancias percorridas por cada formiga estao listadas sempre ao topo de cada tabela de caminho. N H 40 0.025 0.1 0.003 0.12074449 12.1% Partida Chegada % % Relativa % Acumulado N H 0.099 0.0514800515 0.1504800515 N H 40 0.025 0.1504800515 0.004 0.0877144893 8.8% Partida Chegada % % Relativa % Acumulado N I 55 0.0181818182 0.1 0.002 0.0878141745 8.8% I N 7.0% 14.3% 14.0% 88 N I 0.099 0.099 N I 55 0.0181818182 0.099 0.002 0.0419686408 4.2% H G 2.6% 53.1% 53.1% 98 N P 29 0.0344827586 0.1 0.003 0.1665441241 16.7% I W 41.5% 85.7% 100.0% N P 0.099 0.099 N P 29 0.0344827586 0.099 0.003 0.0795956981 8.0% H N 2.3% 46.9% 100.0% N W 17 0.0588235294 0.1 0.006 0.2841046823 28.4% Partida Chegada % % Relativa % Acumulado N W 0.099 0.0308529946 0.1298529946 N W 17 0.0588235294 0.1298529946 0.008 0.1780965257 17.8% Partida Chegada % % Relativa % Acumulado Melhor solucao encontrada Caminho = GNSHPWIAG N S 22 0.0454545455 0.1 0.005 0.2195354363 22.0% W N 47.0% 100.0% 100.0% N S 0.099 0.1062801932 0.08 0.2852801932 N S 22 0.0454545455 0.2852801932 0.013 0.3023439889 30.2% N G 20.8% 100.0% 100.0% Distancia = 207 P A 249 0.0040160643 0.1 0.000 0.0123403785 1.2% P A 0.099 0.3204633205 0.4194633205 P A 249 0.0040160643 0.4194633205 0.002 0.0308476838 3.1% *destacada na imagem do problema acima P G 19 0.0526315789 0.1 0.005 0.1617239079 16.2% P G 0.099 0.0327586207 0.0344827586 0.1662413793 P G 19 0.0526315789 0.1662413793 0.009 0.1602187908 16.0% P H 6 0.1666666667 0.1 0.017 0.5121257084 51.2% P H 0.099 0.0140186916 0.0218181818 0.0255319149 0.1603687883 P H 6 0.1666666667 0.1603687883 0.027 0.489436681 48.9% P I 33 0.0303030303 0.1 0.003 0.0931137652 9.3% P I 0.099 0.099 P I 33 0.0303030303 0.099 0.003 0.0549350054 5.5% P N 58 0.0172413793 0.1 0.002 0.0529785216 5.3% P N 0.099 0.099 P N 58 0.0172413793 0.099 0.002 0.0312561238 3.1% P W 28 0.0357142857 0.1 0.004 0.1097412232 11.0% P W 0.099 0.1352657005 0.2342657005 P W 28 0.0357142857 0.2342657005 0.008 0.1532069944 15.3% P S 53 0.0188679245 0.1 0.002 0.0579764953 5.8% P S 0.099 0.1328320802 0.2318320802 P S 53 0.0188679245 0.2318320802 0.004 0.0800987207 8.0% W A 273 0.0036630037 0.1 0.000 0.0137774148 1.4% S* W A 0.099 0.4954627949 0.5944627949 W A 273 0.0036630037 0.5944627949 0.002 0.0447014656 4.5% W G 84 0.0119047619 0.1 0.001 0.0447765982 4.5% Caminho Distancia W G 0.099 0.099 W G 84 0.0119047619 0.099 0.001 0.0241944436 2.4% Caminho Distancia W H 37 0.027027027 0.1 0.003 0.1016549796 10.2% FORMIGA 2 GNSHPWIAG 207 W H 0.099 0.099 W H 37 0.027027027 0.099 0.003 0.0549279259 5.5% FORMIGA 2 GIAWNSHPG 324 W I 31 0.0322580645 0.1 0.003 0.1213301369 12.1% Partida Chegada % % Acumulado valor aleatorio W I 0.099 0.1497584541 0.2487584541 W I 31 0.0322580645 0.2487584541 0.008 0.1647312088 16.5% Partida Chegada % % Acumulado valor aleatorio W N 8 0.125 0.1 0.013 0.4701542807 47.0% G A 9.2% 9.2% 43 W N 0.099 0.0186915888 0.0290909091 0.0340425532 0.0200501253 0.2008751764 W N 8 0.125 0.2008751764 0.025 0.5154612399 51.5% G A 24.8% 24.8% 30 W P 28 0.0357142857 0.1 0.004 0.1343297945 13.4% G H 6.2% 15.4% W P 0.099 0.036036036 0.135036036 W P 28 0.0357142857 0.135036036 0.005 0.0990036895 9.9% G H 2.5% 27.3% W S 33 0.0303030303 0.1 0.003 0.1139767953 11.4% G I 6.7% 22.0% W S 0.099 0.0568965517 0.1558965517 W S 33 0.0303030303 0.1558965517 0.005 0.0969800267 9.7% G I 12.8% 40.1% S A 306 0.0032679739 0.1 0.000 0.0026298603 0.3% G N 28.7% 50.7% S A 0.099 0.099 S A 306 0.0032679739 0.099 0.000 0.0022249024 0.2% G N 33.9% 74.0% S G 196 0.0051020408 0.1 0.001 0.0041058022 0.4% G P 34.7% 85.4% S G 0.099 0.2522522523 0.3512522523 S G 196 0.0051020408 0.3512522523 0.002 0.0123242425 1.2% G P 20.2% 94.1% S H 1 1 0.1 0.100 0.8047372375 80.5% G W 7.9% 93.3% S H 0.099 0.0048309179 0.0025062657 0.0017241379 0.001814882 0.1098762035 S H 1 1 0.1098762035 0.110 0.755615457 75.6% G W 3.2% 97.3% S I 14 0.0714285714 0.1 0.007 0.0574812313 5.7% G S 6.7% 100.0% S I 0.099 0.0327102804 0.0509090909 0.1826193713 S I 14 0.0714285714 0.1826193713 0.013 0.0897048648 9.0% G S 2.7% 100.0% S N 11 0.0909090909 0.1 0.009 0.0731579307 7.3% Partida Chegada % % Relativa % Acumulado S N 0.099 0.099 S N 11 0.0909090909 0.099 0.009 0.0618927383 6.2% Partida Chegada % % Relativa % Acumulado 7 S P 106 0.0094339623 0.1 0.001 0.0075918607 0.8% N A 1.6% 1.8% 1.8% 81 S P 0.099 0.099 S P 106 0.0094339623 0.099 0.001 0.0064228313 0.6% I A 22.1% 26.6% 26.6% S W 16 0.0625 0.1 0.006 0.0502960773 5.0% N H 12.1% 13.5% 15.3% S W 0.099 0.0680851064 0.1670851064 S W 16 0.0625 0.1670851064 0.010 0.0718149637 7.2% I H 3.3% 4.0% 30.6% N I 8.8% 9.8% 25.1% I N 3.0% 3.6% 34.2% N P 16.7% 18.6% 43.7% I P 23.6% 28.3% 62.6% N W 28.4% 31.7% 75.5% I W 13.2% 15.8% 78.4% N S 22.0% 24.5% 100.0% I S 17.9% 21.6% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 69 S A 0.3% 0.3% 0.3% 63 A H 5.0% 11.5% 11.5% S H 80.5% 87.2% 87.5% A N 5.8% 13.3% 24.8% S I 5.7% 6.2% 93.7% A P 18.5% 42.6% 67.5% S P 0.8% 0.8% 94.5% A W 7.1% 16.3% 83.8% S W 5.0% 5.5% 100.0% A S 7.0% 16.2% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 15 H A 1.3% 4.9% 4.9% 50 W H 5.5% 7.2% 7.2% H I 4.0% 14.6% 19.5% W N 51.5% 67.3% 74.4% H P 16.5% 60.8% 80.3% W P 9.9% 12.9%87.3% H W 5.3% 19.7% 100.0% W S 9.7% 12.7% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 73 P A 1.2% 5.7% 5.7% 78 N H 8.8% 18.7% 18.7% P I 9.3% 43.3% 49.0% N P 8.0% 16.9% 35.6% P W 11.0% 51.0% 100.0% N S 30.2% 64.4% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado W A 1.4% 10.2% 10.2% 12 S H 75.6% 99.2% 99.2% 70 W I 12.1% 89.8% 100.0% S P 0.6% 0.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado I A 8.1% 100.0% 100.0% H P 18.0% 100.0% 100.0% Caminho Distancia Caminho Distancia FORMIGA 3 HWNSIGAPH 275 FORMIGA 3 HGIPNWSAH 682 Partida Chegada % % Acumulado valor aleatorio Partida Chegada % % Acumulado valor aleatorio H A 1.3% 1.3% 32 H A 0.9% 0.9% 3 H G 3.7% 5.0% H G 2.6% 3.5% H I 4.0% 9.0% H I 7.6% 11.1% H N 3.3% 12.3% H N 2.3% 13.4% H P 16.5% 28.8% H P 18.0% 31.4% H W 5.3% 34.1% H W 12.2% 43.6% H S 65.9% 100.0% H S 56.4% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 38 W A 1.4% 1.5% 1.5% 35 G A 24.8% 25.4% 25.4% W G 4.5% 5.0% 6.5% G I 12.8% 13.1% 38.6% W I 12.1% 13.5% 20.0% G N 33.9% 34.8% 73.3% W N 47.0% 52.3% 72.4% G P 20.2% 20.7% 94.0% W P 13.4% 15.0% 87.3% G W 3.2% 3.2% 97.2% W S 11.4% 12.7% 100.0% G S 2.7% 2.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 43 N A 1.6% 2.7% 2.7% 71 I A 22.1% 27.7% 27.7% N G 10.5% 17.6% 20.4% I N 3.0% 3.8% 31.5% N I 8.8% 14.8% 35.1% I P 23.6% 29.5% 61.0% N P 16.7% 28.0% 63.1% I W 13.2% 16.5% 77.5% N S 22.0% 36.9% 100.0% I S 17.9% 22.5% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 19 S A 0.3% 3.7% 3.7% 41 P A 3.1% 10.4% 10.4% S G 0.4% 5.7% 9.4% P N 3.1% 10.6% 21.0% S I 5.7% 80.0% 89.4% P W 15.3% 51.9% 72.9% S P 0.8% 10.6% 100.0% P S 8.0% 27.1% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 39 I A 8.1% 23.4% 23.4% 44 N A 10.2% 17.6% 17.6% I G 17.6% 51.1% 74.5% N W 17.8% 30.6% 48.1% I P 8.8% 25.5% 100.0% N S 30.2% 51.9% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 94 G A 9.2% 20.9% 20.9% 2 W A 4.5% 31.6% 31.6% G P 34.7% 79.1% 100.0% W S 9.7% 68.4% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado A P 6.9% 100.0% 100.0% S A 0.2% 100.0% 100.0% Caminho Distancia Caminho Distancia FORMIGA 4 IPHSWNGAI 235 FORMIGA 4 IWNSHPGAI 215 Partida Chegada % % Acumulado valor aleatorio Partida Chegada % % Acumulado valor aleatorio I A 8.1% 8.1% 45 I A 22.1% 22.1% 80 I G 17.6% 25.7% I G 16.8% 38.9% I H 7.8% 33.4% I H 3.3% 42.3% I N 7.0% 40.4% I N 3.0% 45.3% I P 8.8% 49.3% I P 23.6% 68.9% I W 9.2% 58.5% I W 13.2% 82.1% I S 41.5% 100.0% I S 17.9% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 33 P A 1.2% 1.4% 1.4% 63 W A 4.5% 5.4% 5.4% P G 16.2% 17.8% 19.2% W G 2.4% 2.9% 8.2% P H 51.2% 56.5% 75.7% W H 5.5% 6.6% 14.8% P N 5.3% 5.8% 81.5% W N 51.5% 61.7% 76.5% P W 11.0% 12.1% 93.6% W P 9.9% 11.9% 88.4% P S 5.8% 6.4% 100.0% W S 9.7% 11.6% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 70 H A 1.3% 1.7% 1.7% 23 N A 10.2% 13.1% 13.1% H G 3.7% 4.7% 6.3% N G 20.8% 26.6% 39.8% H N 3.3% 4.1% 10.5% N H 8.8% 11.2% 51.0% H W 5.3% 6.7% 17.2% N P 8.0% 10.2% 61.2% H S 65.9% 82.8% 100.0% N S 30.2% 38.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 82 S A 0.3% 2.0% 2.0% 67 S A 0.2% 0.3% 0.3% S G 0.4% 3.2% 5.2% S G 1.2% 1.6% 1.9% S N 7.3% 56.2% 61.4% S H 75.6% 97.3% 99.2% S W 5.0% 38.6% 100.0% S P 0.6% 0.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 59 W A 1.4% 2.6% 2.6% 27 H A 0.9% 4.2% 4.2% W G 4.5% 8.5% 11.1% H G 2.6% 12.0% 16.2% W N 47.0% 88.9% 100.0% H P 18.0% 83.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 43 N A 1.6% 13.4% 13.4% 60 P A 3.1% 16.1% 16.1% N G 10.5% 86.6% 100.0% P G 16.0% 83.9% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado G A 9.2% 100.0% 100.0% G A 24.8% 100.0% 100.0% Caminho Distancia Caminho Distancia FORMIGA 5 NHSGIWPAN 777 FORMIGA 5 NSHGAPWIN 373 Partida Chegada % % Acumulado valor aleatorio Partida Chegada % % Acumulado valor aleatorio N A 1.6% 1.6% 15 N A 10.2% 10.2% 74 N G 10.5% 12.1%N G 20.8% 31.0% N H 12.1% 24.2% N H 8.8% 39.8% N I 8.8% 33.0% N I 4.2% 44.0% N P 16.7% 49.6% N P 8.0% 52.0% N W 28.4% 78.0% N W 17.8% 69.8% N S 22.0% 100.0% N S 30.2% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 35 H A 1.3% 1.4% 1.4% 69 S A 0.2% 0.2% 0.2% H G 3.7% 3.9% 5.2% S G 1.2% 1.3% 1.6% H I 4.0% 4.1% 9.3% S H 75.6% 80.5% 82.1% H P 16.5% 17.0% 26.3% S I 9.0% 9.6% 91.7% H W 5.3% 5.5% 31.9% S P 0.6% 0.7% 92.3% H S 65.9% 68.1% 100.0% S W 7.2% 7.7% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 4 S A 0.3% 2.2% 2.2% 4 H A 0.9% 2.2% 2.2% S G 0.4% 3.4% 5.5% H G 2.6% 6.2% 8.4% S I 5.7% 47.1% 52.6% H I 7.6% 18.4% 26.9% S P 0.8% 6.2% 58.8% H P 18.0% 43.7% 70.6% S W 5.0% 41.2% 100.0% H W 12.2% 29.4% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 8 G A 9.2% 15.7% 15.7% 17 G A 24.8% 40.7% 40.7% G I 6.7% 11.4% 27.1% G I 12.8% 21.0% 61.7% G P 34.7% 59.5% 86.6% G P 20.2% 33.1% 94.8% G W 7.9% 13.4% 100.0% G W 3.2% 5.2% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 67 I A 8.1% 30.9% 30.9% 94 A I 24.6% 49.0% 49.0% I P 8.8% 33.7% 64.7% A P 18.5% 36.9% 85.9% I W 9.2% 35.3% 100.0% A W 7.1% 14.1% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 36 W A 1.4% 9.3% 9.3% 48 P I 5.5% 26.4% 26.4% W P 13.4% 90.7% 100.0% P W 15.3% 73.6% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado P A 1.2% 100.0% 100.0% W I 16.5% 100.0% 100.0% Caminho Distancia Caminho Distancia FORMIGA 6 PSHWNGIAP 399 FORMIGA 6 PHWAGISNP 487 Partida Chegada % % Acumulado valor aleatorio Partida Chegada % % Acumulado valor aleatorio P A 1.2% 1.2% 97 P A 3.1% 3.1% 65 P G 16.2% 17.4% P G 16.0% 19.1% P H 51.2% 68.6% P H 48.9% 68.1% P I 9.3% 77.9% P I 5.5% 73.5% P N 5.3% 83.2% P N 3.1% 76.7% P W 11.0% 94.2% P W 15.3% 92.0% P S 5.8% 100.0% P S 8.0% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 25 S A 0.3% 0.3% 0.3% 55 H A 0.9% 1.1% 1.1% S G 0.4% 0.4% 0.7% H G 2.6% 3.1% 4.3% S H 80.5% 81.1% 81.8% H I 7.6% 9.3% 13.5% S I 5.7% 5.8% 87.6% H N 2.3% 2.8% 16.3% S N 7.3% 7.4% 94.9% H W 12.2% 14.8% 31.2% S W 5.0% 5.1% 100.0% H S 56.4% 68.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 1 H A 1.3% 7.5% 7.5% 87 W A 4.5% 5.3% 5.3% H G 0.0372961313 21.1% 28.6% W G 2.4% 2.9% 8.1% H I 0.0395338992 22.4% 51.0% W I 16.5% 19.5% 27.6% H N 0.032944916 18.7% 69.7% W N 51.5% 60.9% 88.5% H W 0.0534241881 30.3% 100.0% W S 9.7% 11.5% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 42 W A 1.4% 2.1% 2.1% 36 A G 32.0% 46.1% 46.1% W G 4.5% 6.9% 9.0% A I 24.6% 35.5% 81.6% W I 12.1% 18.7% 27.7% A N 5.8% 8.3% 89.9% W N 47.0% 72.3% 100.0% A S 7.0% 10.1% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 22 N A 1.6% 7.8% 7.8% 44 G I 12.8% 25.9% 25.9% N G 10.5% 50.2% 58.0% G N 33.9% 68.6% 94.5% N I 8.8% 42.0% 100.0% G S 2.7% 5.5% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 76 G A 9.2% 57.9% 57.9% 78 I N 3.0% 14.4% 14.4% G I 6.7% 42.1% 100.0% I S 17.9% 85.6% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado I A 8.1% 100.0% 100.0% S N 6.20% 100.0% 100.0% Caminho Distancia Caminho Distancia FORMIGA 7 WSHIPGNAW 580 FORMIGA 7 WNGPSHIAW 340 Partida Chegada % % Acumulado valor aleatorio Partida Chegada % % Acumulado valor aleatorio W A 1.4% 1.4% 99 W A 4.5% 4.5% 40 W G 4.5% 5.9% W G 2.4% 6.9% W H 10.2% 16.0% W H 5.5% 12.4% W I 12.1% 28.2% W I 16.5% 28.9% W N 47.0% 75.2% W N 51.5% 80.4% W P 13.4% 88.6% W P 9.9% 90.3% W S 11.4% 100.0% W S 9.7% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 27 S A 0.3% 0.3% 0.3% 59 N A 10.2% 12.5% 12.5% S G 0.4% 0.4% 0.7% N G 20.8% 25.3% 37.8% S H 80.5% 84.7% 85.4% N H 8.8% 10.7% 48.4% S I 5.7% 6.1% 91.5% N I 4.2% 5.1% 53.5% S N 7.3% 7.7% 99.2% N P 8.0% 9.7% 63.2% S P 0.8% 0.8% 100.0% N S 30.2% 36.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 88 H A 1.3% 4.6% 4.6% 30 G A 24.8% 39.3% 39.3% H G 3.7% 13.0% 17.5% G H 2.5% 4.0% 43.3% H I 4.0% 13.7% 31.3% G I 12.8% 20.4% 63.7% H N 3.3% 11.5%42.7% G P 20.2% 32.0% 95.7% H P 16.5% 57.3% 100.0% G S 2.7% 4.3% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 95 I A 8.1% 19.5% 19.5% 81 P A 3.1% 4.7% 4.7% I G 17.6% 42.4% 61.9% P H 48.9% 74.7% 79.4% I N 7.0% 16.9% 78.8% P I 5.5% 8.4% 87.8% I P 8.8% 21.2% 100.0% P S 8.0% 12.2% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 65 P A 1.2% 5.4% 5.4% 66 S A 0.2% 0.3% 0.3% P G 16.2% 71.2% 76.7% S H 75.6% 89.2% 89.4% P N 5.3% 23.3% 100.0% S I 9.0% 10.6% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 91 G A 9.2% 24.2% 24.2% 72 H A 0.9% 10.7% 10.7% G N 28.7% 75.8% 100.0% H I 7.6% 89.3% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado N A 1.6% 100.0% 100.0% I A 22.1% 100.0% 100.0% Caminho Distancia Caminho Distancia FORMIGA 8 SHIPGNWAS 551 FORMIGA 8 SHIGPAWNS 473 Partida Chegada % % Acumulado valor aleatorio Partida Chegada % % Acumulado valor aleatorio S A 0.3% 0.3% 19 S A 0.2% 0.2% 64 S G 0.4% 0.7% S G 1.2% 1.5% S H 80.5% 81.1% S H 75.6% 77.0% S I 5.7% 86.9% S I 9.0% 86.0% S N 7.3% 94.2% S N 6.2% 92.2% S P 0.8% 95.0% S P 0.6% 92.8% S W 5.0% 100.0% S W 7.2% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 19 H A 1.3% 3.9% 3.9% 17 H A 0.9% 2.1% 2.1% H G 3.7% 10.9% 14.8% H G 2.6% 5.9% 8.0% H I 4.0% 11.6% 26.4% H I 7.6% 17.5% 25.5% H N 3.3% 9.7% 36.0% H N 2.3% 5.2% 30.7% H P 16.5% 48.3% 84.3% H P 18.0% 41.4% 72.1% H W 5.3% 15.7% 100.0% H W 12.2% 27.9% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 33 I A 8.1% 15.9% 15.9% 70 I A 22.1% 28.1% 28.1% I G 17.6% 34.7% 50.6% I G 16.8% 21.4% 49.5% I N 7.0% 13.8% 64.4% I N 3.0% 3.8% 53.3% I P 8.8% 17.4% 81.8% I P 23.6% 30.0% 83.3% I W 9.2% 18.2% 100.0% I W 13.2% 16.7% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 72 P A 1.2% 3.7% 3.7% 27 G A 24.8% 30.2% 30.2% P G 16.2% 48.0% 51.7% G N 33.9% 41.3% 71.5% P N 5.3% 15.7% 67.4% G P 20.2% 24.6% 96.2% P W 11.0% 32.6% 100.0% G W 3.2% 3.8% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 10 G A 9.2% 20.0% 20.0% 35 P A 3.1% 14.3% 14.3% G N 28.7% 62.8% 82.8% P N 3.1% 14.5% 28.8% G W 7.9% 17.2% 100.0% P W 15.3% 71.2% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado 60 N A 1.6% 5.4% 5.4% 14 A N 5.8% 44.9% 44.9% N W 28.4% 94.6% 100.0% A W 7.1% 55.1% 100.0% Partida Chegada % % Relativa % Acumulado Partida Chegada % % Relativa % Acumulado W A 1.4% 100.0% 100.0% W N 51.5% 100.0% 100.0%