Apresentação 5 - POII - Método Caixeiro Viajante(1)

Prévia do material em texto

Pesquisa Operacional II
Apresentação 5
Prof. Fábio J. Ricardo
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 trata-se 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 = (n-1)! ÷ 2 	Assimétrico: rotas = (n-1)!
Método Caixeiro Viajante
Simétrico:
Ex.: tanto faz de AB ou BA = 9km
Método Caixeiro Viajante
Assimétrico:
Ex.: AB = 9km e BA = 7km
 custos diferentes
custos iguais
Método Caixeiro Viajante
Exemplo com 4 cidades:
A
D
B
C
Caix. Viaj. Simétrico Cij = Cji => (n-1)!/2 = 3
Caix. Viaj. Assimétrico Cij ≠ Cji => (n-1)! = 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) ....
 10^9 /19 = 53 milhões de rotas por segundo
Método Caixeiro Viajante
Exemplos de resoluções:
 Placa circuito impresso: 2.392 pontos (“cidades”)  Padberg and Rinaldi (1987)
Método Caixeiro Viajante
Exemplos de resoluções:
 13.509 cidades americanas. Applegate, Bixby Chvátal and Cook (1998)
Método Caixeiro Viajante
Exemplos de resoluções:
 15.112 cidades alemãs. Applegate, Bixby Chvátal and Cook (2001)
Método Caixeiro Viajante
Exemplos de resoluções:
 24.978 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”
D
0
C
14
B
25
A
34
E
51
D
67
Método Caixeiro Viajante
Caixeiro Viajante Simétrico  “Vizinho mais Próximo”
D
0
B
7
A
16
C
26
E
32
D
48
Método Caixeiro Viajante
Caixeiro Viajante Assimétrico  “Aleatório”
D
0
C
16
B
32
A
39
E
58
D
73
Método Caixeiro Viajante
Caixeiro Viajante Assimétrico  “Vizinho mais Próximo”
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
Tower Bridget
Palácio de Buckingham
Madame Tussauds London
The Windsor Castle
Big Ben
Harrods
London Eye
Oxford Street
Trafalgar Square
Abbey Road Zebra
Queens Hotel
Método Caixeiro Viajante
1 - Mapear todas as rotas possíveis entre os pontos
Tower Bridget
Madame Tussauds London
The Windsor Castle
Harrods
London Eye
Oxford Street
Trafalgar Square
Abbey Road Zebra
Tower Bridge
Queens Hotel
Big Ben
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
Big Ben
Harrods
Oxford Street
Trafalgar Square
Abbey Road Zebra
London Eye
Queens Hotel
Método Caixeiro Viajante
2 – Tabela de Distâncias
Excel
Método Caixeiro Viajante
Rota
Método Caixeiro Viajante
Queens - The Windsor Castle
Queens Hotel
The Windsor Castle
7,41 kms 
Método Caixeiro Viajante
The Windsor Castle - Harrods
The Windsor Castle
Harrods
Queens Hotel
11,11 kms 
Método Caixeiro Viajante
Harrods - Palácio de Buckingham
Harrods
Palácio de Buckingham
12,88 kms 
Método Caixeiro Viajante
Palácio de Buckingham - Trafalgar Square
Palácio de Buckingham
Trafalgar Square
14,01 kms 
Método Caixeiro Viajante
Trafalgar Square - Big Ben
Trafalgar Square
Big Ben
14,97 kms 
Método Caixeiro Viajante
Big Bem - London Eye
Big Ben
London Eye
15,94 kms 
Método Caixeiro Viajante
London Eye - Tower Bridge
London Eye
Tower Bridge
20,13 kms 
Método Caixeiro Viajante
Tower Bridge - Oxford Street
Tower Bridge
Oxford Street
26,08 kms 
Método Caixeiro Viajante
Oxford Street - Madame Tussauds
Oxford Street
Madame Tussauds London
28,50 kms 
Método Caixeiro Viajante
Madame Tussauds - Abbey Road Zebra
Madame Tussauds London
Abbey Road Zebra
31,72 kms 
Método Caixeiro Viajante
Abbey Road Zebra – Queens Hotel
Abbey Road Zebra
Queens Hotel
40,09 kms 
Método Caixeiro Viajante
Uso do Power Query (BI) para coleta de informações
Projeto
Começar a roteirizar os pontos do projeto
Inserir no arquivo Excel
Lista de pontos escolhidos
Hotel (ponto de saída)
Imagem do Power Query com as consultas realizadas (instruções em sala de aula)
Imagem da lista gerada no Power BI (instruções em sala de aula)
Tabela de distâncias e tempos de deslocamentos entre os pontos (conforme slide 22)
Roteirização usando método do Caixeiro Viajante
OBS: Em primeiro lugar, considerar que serão visitados os 10 pontos em um único dia. 
Lembrando: projeto tem peso 3 pontos no bimestre, sendo 1 ponto o custo mínimo já repassado e 2 pontos Caixeiro Viajante.
Caso queira, poderá coletar as informações à mão usando Google Maps ou Bing, porém serão acrescentados pelo menos mais dois pontos aleatórios a cada projeto (pelo professor), fazendo com que os cálculos alterem, neste caso o Power BI trará as demais combinações de rotas automaticamente.
O método do caixeiro viajante será montado no Excel (manualmente) ou, à livre escolha, pode ser montado também no Power BI. A planilha do Excel poderá ser também automatizada cado desejem
n
Rotas por seg. 
(milhões)(n-1)!/2tempo
525012inexpressivo
10110181.400inexpressivo
157143,5 milhões10 minutos
20536*10
^6
36,5 anos
j=1j=2j=3j=4j=5* 
Distâncias em milhas
Queens HotelBig Ben
Palácio de 
Buckingham
Tower Bridge
Madame 
Tussauds
The Windsor 
Castle
Oxford Street
Abbey Road 
Zebra
Trafalgar SquareLondon EyeHarrods
Queens Hotel05,95,96,24,74,64,95,25,15,46,9
Big Ben5,900,82,83,32,41,64,70,60,61,9
Palácio de Buckingham5,90,801,12,42,91,43,80,71,41,1
Tower Bridge6,22,81,105,46,43,76,72,72,64,6
Madame Tussauds4,73,32,45,403,11,521,94,12,7
The Windsor Castle4,62,42,96,43,103,233,64,62,3
Oxford Street4,91,61,43,71,53,202,91,52,81,9
Abbey Road Zebra5,24,73,86,7232,904,45,94
Trafalgar Square5,10,60,72,71,93,61,54,401,21,9
London Eye5,40,61,42,64,14,62,85,91,202,7
Harrods6,91,91,14,62,72,31,941,92,70
1,0 milha 
≅
 1,61 kms
Ponto Saída --> Hotel Queens
324 Seven Sisters Rd, Finsbury Park, London N4 2AP, Reino Unido