Análise do Método Caixeiro Viajante e suas Aplicações

Método Caixeiro Viajante Método Caixeiro Viajante Objetivo Viajar n cidades diferentes sem repetir nenhuma não importando a ordem com que elas são visitadas De cada cidade o trajeto pode ser tomado para qualquer outra A otimização é descobrir qual a rota total que torna o menor percurso para o viajante Importante deve sempre retornar ao ponto de origem De cada cidade chega parte apenas um arco Uma questão de análise combinatória como tratase de fatorial o número de soluções cresce mais rápido do que exponencialmente Ex rotas de vans escolares chamados manutenção entregas refeições visita diária à lojas etc Questões Como determinar todas as rotas possíveis Como saber qual delas é a menor Simétrico rotas n1 2 Assimétrico rotas n1 Método Caixeiro Viajante Simétrico Ex tanto faz de AB ou BA 9km Método Caixeiro Viajante Assimétrico Ex AB 9km e BA 7km custos diferentes custos iguais Método Caixeiro Viajante Exemplo com 4 cidades A D B C Caix Viaj Simétrico Cij Cji n12 3 Caix Viaj Assimétrico Cij Cji n1 6 Método Caixeiro Viajante Um computador que seja capaz de fazer 1 bilhão de adições por segundo para um problema com 20 cidades 19 adições 109 19 53 milhões de rotas por segundo n Rotas por seg milhões n12 tempo 5 250 12 inexpressivo 10 110 181400 inexpressivo 15 71 435 milhões 10 minutos 20 53 6106 365 anos Método Caixeiro Viajante Exemplos de resoluções Placa circuito impresso 2392 pontos cidades Padberg and Rinaldi 1987 Método Caixeiro Viajante Exemplos de resoluções 13509 cidades americanas Applegate Bixby Chvátal and Cook 1998 Método Caixeiro Viajante Exemplos de resoluções 15112 cidades alemãs Applegate Bixby Chvátal and Cook 2001 Método Caixeiro Viajante Exemplos de resoluções 24978 cidades na Suécia Applegate Bixby Chvátal Cook and Helsgaun 2004 Método Caixeiro Viajante Restrições do Método Apenas um arco de chegada Apenas um arco de saída Não conter subrotas Método Caixeiro Viajante Caixeiro Viajante Simétrico Aleatório j1 j2 j3 j4 j5 D 0 C 14 B 25 A 34 E 51 D 67 Método Caixeiro Viajante Caixeiro Viajante Simétrico Vizinho mais Próximo j1 j2 j3 j4 j5 D 0 B 7 A 16 C 26 E 32 D 48 Método Caixeiro Viajante Caixeiro Viajante Assimétrico Aleatório j1 j2 j3 j4 j5 D 0 C 16 B 32 A 39 E 58 D 73 Método Caixeiro Viajante Caixeiro Viajante Assimétrico Vizinho mais Próximo j1 j2 j3 j4 j5 D 0 B 5 A 12 C 21 E 27 D 42 Método Caixeiro Viajante Exercício Visita à London UK Você está fazendo uma viagem à Londres no Reino unido e fará a visita aos principais pontos turísticos listados a seguir Tower Bridge Palácio de Buckingham Madame Tussauds London The Windsor Castle Big Ben Harrods Método Caixeiro Viajante Exercício Visita à London UK Você está fazendo uma viagem à Londres no Reino unido e fará a visita aos principais pontos turísticos listados a seguir London Eye Oxford Street Trafalgar Square Abbey Road Zebra Ponto Saída Hotel Queens 324 Seven Sisters Rd Finsbury Park London N4 2AP Reino Unido Método Caixeiro Viajante 1 Mapear todas as rotas possíveis entre os pontos Palácio de Buckingham Madame Tussauds London The Windsor Castle Big Ben Harrods London Eye Oxford Street Trafalgar Square Abbey Road Zebra Tower Bridge Queens Hotel Método Caixeiro Viajante 1 Mapear todas as rotas possíveis entre os pontos Tower Bridget Palácio de Buckingham Madame Tussauds London The Windsor Castle Harrods London Eye Oxford Street Trafalgar Square Abbey Road Zebra Queens Hotel Big Ben Método Caixeiro Viajante 1 Mapear todas as rotas possíveis entre os pontos Palácio de Buckingham Madame Tussauds London The Windsor Castle Big Ben Harrods Oxford Street Trafalgar Square Abbey Road Zebra Tower Bridge London Eye Queens Hotel Método Caixeiro Viajante 2 Tabela de Distâncias Distâncias em milhas Queens Hotel Big Ben Palácio de Buckingham Tower Bridge Madame Tussauds The Windsor Castle Oxford Street Abbey Road Zebra Trafalgar Square London Eye Harrods Queens Hotel 0 59 59 62 47 46 49 52 51 54 69 Big Ben 59 0 08 28 33 24 16 47 06 06 19 Palácio de Buckingham 59 08 0 11 24 29 14 38 07 14 11 Tower Bridge 62 28 11 0 54 64 37 67 27 26 46 Madame Tussauds 47 33 24 54 0 31 15 2 19 41 27 The Windsor Castle 46 24 29 64 31 0 32 3 36 46 23 Oxford Street 49 16 14 37 15 32 0 29 15 28 19 Abbey Road Zebra 52 47 38 67 2 3 29 0 44 59 4 Trafalgar Square 51 06 07 27 19 36 15 44 0 12 19 London Eye 54 06 14 26 41 46 28 59 12 0 27 Harrods 69 19 11 46 27 23 19 4 19 27 0 10 milha 161 kms Ponto Saída Hotel Queens 324 Seven Sisters Rd Finsbury Park London N4 2AP Reino Unido Excel Método Caixeiro Viajante Rota 2 h 8 min 242 milhas Queens Hotel Método Caixeiro Viajante Queens The Windsor Castle Queens Hotel The Windsor Castle 741 kms Método Caixeiro Viajante The Windsor Castle Harrods The Windsor Castle Harrods Queens Hotel 1111 kms Método Caixeiro Viajante Harrods Palácio de Buckingham Harrods Palácio de Buckingham 1288 kms Método Caixeiro Viajante Palácio de Buckingham Trafalgar Square Palácio de Buckingham Trafalgar Square 1401 kms Método Caixeiro Viajante Trafalgar Square Big Ben Trafalgar Square Big Ben 1497 kms Método Caixeiro Viajante Big Bem London Eye Big Ben London Eye 1594 kms Método Caixeiro Viajante London Eye Tower Bridge London Eye Tower Bridge 2013 kms Método Caixeiro Viajante Tower Bridge Oxford Street Tower Bridge Oxford Street 2608 kms Método Caixeiro Viajante Oxford Street Madame Tussauds Oxford Street Madame Tussauds London 2850 kms Método Caixeiro Viajante Madame Tussauds Abbey Road Zebra Madame Tussauds London Abbey Road Zebra 3172 kms Método Caixeiro Viajante Abbey Road Zebra Queens Hotel Abbey Road Zebra Queens Hotel 4009 kms Como tarefa refazer o exercício considerando o tempo de deslocamento de transporte público Este exercício valerá uma parte da nota da A1 OBS a tabela poderá ser montada coletando os valores um a um no google maps ou pelo método de scraping de dados no Power BI