Pesquisa Operacional 2
Semana 04 - Aula 01
Prof. Anibal Tavares de Azevedo
Tema da Semana
Caixeiro Viajante e Roteamento de Veículos - Teoria
Semana 03
Componentes do problema
Locais de Facilidades | Regiões de Demanda
Semana 03
Componentes do problema
Locais de Facilidades | Regiões de Demanda
J = {1, ..., n}
Demanda
Semana 03
Componentes do problema
Locais de Facilidades | Regiões de Demanda
J = {1, ..., n}
Demanda
I = {1, ..., m}
Facilidades
Problema do Caixeiro Viajante
Descrição do problema
Percorrer todas as cidades 1 vez e min dist.
Problema do Caixeiro Viajante
Variável de Decisão
Caixeiro sai da cidade i para a cidade j
J = {1, ..., m}
Cidade destino
I = {1, ..., m}
Cidade origem
xij = 1
Origem i = 1 Destino j = 2
Problema do Caixeiro Viajante
Restrições: Qual a próxima cidade?
Só pode haver 1 próxima cidade!
x12 = 1
x13 = 1
x12 + x13 + … +x110 = 1
Problema do Caixeiro Viajante
Restrições: Qual a próxima cidade?
Só pode haver 1 próxima cidade!
x12 = 1
x13 = 1
x12 + x13 + … +x110 = 1
Problema do Caixeiro Viajante
Restrições: Qual a próxima cidade?
Só pode haver 1 próxima cidade!
x12 = 1
x13 = 1
x12 + x13 + … +x110 = 1
Problema do Caixeiro Viajante
Restrições: Qual a próxima cidade?
Só pode haver 1 próxima cidade!
x12 = 1
x13 = 1
x12 + x13 + … +x110 = 1
Problema do Caixeiro Viajante
Restrições: Qual a cidade anterior?
Só pode haver 1 cidade anterior!
x21 = 1
x31 = 1
x21 + x31 + … +x101 = 1
Problema do Caixeiro Viajante
Restrições: Qual a cidade anterior?
Só pode haver 1 cidade anterior!
x21 = 1
x31 = 1
x21 + x31 + … +x101 = 1
Problema do Caixeiro Viajante
Restrições: Qual a cidade anterior?
Só pode haver 1 cidade anterior!
x21 = 1
x31 = 1
x21 + x31 + … +x101 = 1
Problema do Caixeiro Viajante
Restrições: Eliminação de sub-rotas
Sub-rotas de tamanho 2!
x21 = 1
x12 = 1
x12 + x21 = 1
Problema do Caixeiro Viajante
Restrições: Eliminação de sub-rotas
Sub-rotas de tamanho 2!
x21 = 1
x12 = 1
x12 + x21 = 1
x12 + x21 ≤ 1
Problema do Caixeiro Viajante
Restrições: Eliminação de sub-rotas
Sub-rotas de tamanho 2!
x21 = 1
x12 = 1
x12 + x21 = 1
x12 + x21 ≤ 1
x12 = 1
x21 = 0
Problema do Caixeiro Viajante
Restrições: Eliminação de sub-rotas
Sub-rotas de tamanho 2!
x21 = 1
x12 = 1
x12 + x21 = 1
x12 + x21 ≤ 1
x12 = 0
x21 = 1
x12 = 1
x21 = 0
Problema do Caixeiro Viajante
Restrições: Eliminação de sub-rotas
Sub-rotas de tamanho 2!
x21 = 1
x12 = 1
x12 + x21 = 1
x13 + x31 = 1
x110 + x101 = 1
…
Problema do Caixeiro Viajante
Restrições: Eliminação de sub-rotas
Sub-rotas de tamanho 3, 4, …, (m-1)!
x12 = 1
x23 = 1
x12 + x23 + x31 = 1
x31 = 1
x12 + x23 +... xm-11 = 1
…
Problema do Caixeiro Viajante
Restrições: Eliminação de sub-rotas
Sub-rotas de tamanho 3, 4, …, (m-1)!
x12 = 1
x23 = 1
x12 + x23 + x31 = 1
x31 = 1
x12 + x23 +... xm-11 = 1
…
PCV - Modelo 1
Modelo Geral e Completo
Porém, extremamente ineficiente!
Qual a próxima cidade j?
Qual a cidade i anterior?
Eliminação de Sub-rotas!
Minimizar distância percorrida
PCV - Modelos Possíveis
Artigo de revisão de modelos
Lidando com as restrições de sub-rotas
http://eprints.lse.ac.uk/9349/1/WP67_A_Survey_of_DifferentFormulationsoftheTSPJuly20051LSEROVERSION.pdf
Eliminação de Sub-rotas!
PCV - Modelo 2
Modelo Geral e Completo
Formulação sequencial: MTZ, 1960
+Variável ui contínua: sequência da cidade i
Qual a próxima cidade j?
Qual a cidade i anterior?
Sequência na qual
a cidade i é visitada (i≠1)
Minimizar distância percorrida
Próxima aula…
Práticas com Google Colab