O Problema do Caixeiro Viajante
Maria do Socorro Nogueira Rangel
DCCE
Departamento de Ciências da Computação e Estatística
e-mail: [email protected]
Apoio
:
http://www.dcce.ibilce.unesp.br/~socorro/
O Problema do Caixeiro Viajante
O Presidente, Antônio Castor, da Companhia Ramos de Carvalho quer
fazer uma visita às reservas florestais situadas nos estados do
Amazonas e Pará, aos depósitos situados nos estados de São Paulo,
Bahia, Minas Gerais e Rio de Janeiro. É possível determinar um roteiro
de viagem tal que cada reserva e cada depósito sejam visitados apenas
uma vez, saindo e retornando à sede da empresa no Rio de Janeiro, e
que minimize a distância total percorrida?
Be
Sal
Circuito Hamiltoniano
Ma
RJ
Go
SP
Figura 1 – Reservas e Depósitos a serem visitados
Quantos roteiros
existem?
• Se o problema considerar n cidades teremos
que o número total de roteiros é (n-1)!
n
n!
Tempo
8
40320
1s
10
3628800
54s
11
39916800
12 min
12
479001600
1h 25 min
30
2 . 1032*
9 . 1021 milênios*
*Da ordem de
50
3 . 1064*
9 . 1053 milênios*
Assim, fica inviável analisar todos
os circuitos manualmente!
Construção do Modelo:
Variáveis
Índices
i,j = 1,2,3, ...6 os locais onde as reservas (duas) e os depósitos
(quatro) estão situados (RJ,SP,Go,Ma,Be e Sal) respectivamente.
Variáveis de decisão:
xij 
1 se a cidade i é visitada antes da j
0 caso contrário.
Construção do Modelo:
Objetivo
OBJETIVO
Vamos chamar de
cij a distância entre os locais i e j.
O objetivo é encontrar o circuito hamiltonino de menor
custo.
6
6
min z   cij xij
i 1 j 1
Construção do Modelo:
Restrições
Cada local deve ser visitado apenas uma vez.
•Saídas da cidade i:
xi1  xi 2  xi3  xi 4  xi5  xi6  1, i  1,..., 6
•Chegadas à cidade j
x1 j  x2 j  x3 j  x4 j  x5 j  x6 j  1, j  1,..., 6
Problema do Caixeiro Viajante: Modelo I
Sintaxe MPL
TITLE
Caixeiro;
INDEX
no =(RJ,SP,Go,Ma,Be e Sal);
origem = no;
destino = no;
DATA
custo[origem, destino] :=
EXCELRANGE (“caixeiro.xls", custo);
DECISION VARIABLES
x[origem, destino]
WHERE(origem <> destino);
MODEL
MIN T_Cost = SUM(origem, destino: custo * x);
SUBJECT TO
partida[no] : SUM(origem=no, destino: x) =1;
chegada[no] : SUM(origem, destino=no: x) =1;
BINARY
x
END
Problema do Caixeiro Viajante: Modelo I
Caixeiro2.lp
\ Generated with the MPL Modeling System
\ Constraints:
37, \ Variables:
36, Integers:
30
\ Nonzeros:
135
\ Density:
10 %
MINIMIZE
TotalCos: xRJAm + xRJPa + xRJBa + xRJGo
+ xRJSP + xAmRJ + xAmPa + xAmBa + xAmGo + xAmSP
+ xPaRJ + xPaAm + xPaBa + xPaGo + xPaSP + xBaRJ
+ xBaAm + xBaPa + xBaGo + xBaSP + xGoRJ + xGoAm
+ xGoPa + xGoBa + xGoSP + xSPRJ + xSPAm
+ xSPPa + xSPBa + xSPGo
SUBJECT TO
partidRJ: xRJAm + xRJPa + xRJBa + xRJGo + xRJSP = 1
partidAm: xAmRJ + xAmPa + xAmBa + xAmGo + xAmSP = 1
partidPa: xPaRJ + xPaAm + xPaBa + xPaGo + xPaSP = 1
partidBa: xBaRJ + xBaAm + xBaPa + xBaGo + xBaSP = 1
partidGo: xGoRJ + xGoAm + xGoPa + xGoBa + xGoSP = 1
partidSP: xSPRJ + xSPAm + xSPPa + xSPBa + xSPGo = 1
chegadRJ: xAmRJ + xPaRJ + xBaRJ + xGoRJ + xSPRJ = 1
chegadAm: xRJAm + xPaAm + xBaAm + xGoAm + xSPAm = 1
chegadPa: xRJPa + xAmPa + xBaPa + xGoPa + xSPPa = 1
chegadBa: xRJBa + xAmBa + xPaBa + xGoBa + xSPBa = 1
chegadGo: xRJGo + xAmGo + xPaGo + xBaGo + xSPGo = 1
chegadSP: xRJSP + xAmSP + xPaSP + xBaSP + xGoSP = 1
Optimal solution found
MIN Z
=
170.0000
MACROS
Macro Name
Values
----------------------------------------------Custo_Total
170.0000
----------------------------------------------DECISION VARIABLES
VARIABLE x[origem,destino] :
origem destino
Activity
----------------------------------------------------Rio
SP
1.0000
SP
Go
1.0000
Go
Rio
1.0000
Ma
Be
1.0000
Be
Sal
1.0000
Sal
Ma
1.0000
-----------------------------------------------------
Construção do Modelo:
Restrições
As restrições do problema da designação permitem a seguinte solução:
Qual é o problema desta solução?
Be
Ba
Subrotas!!!!
Ma
RJ
Go
SP
Com este roteiro
não conseguimos
passar por todas
as cidades apenas
uma vez!
Reformulação I - Eliminação de subrotas:
Miller,Tucker e Zemlin
Para eliminar as subrotas, vamos acrescentar as seguintes variáveis:
u i = ordem em que a cidade i será visitada
i  2,...n
e as seguintes restrições:
ui  u j  nxij  n  1
i, j  2,...,6; i  j.
Existem
(n  1)
2
restrições para eliminação de subrotas.
Reformulação I :
Modelo de otimização inteiro misto:
6
6
min z   cij xij
i 1 j 1
sujeito a
xi1  xi 2  xi 3  xi 4  xi 5  xi 6  1,
i  1,...,6
x1 j  x2 j  x3 j  x4 j  x5 j  x6 j  1,
j  1,...,6
ui  u j  6 xij  5,
i  j; i  2,...,6;
j  2,...,.6;
xij  0 / 1, i, j
1  ui  5, i  2,...,6
Reformulação II - Eliminação de subrotas:
Dantzig, Fulkerson e Johnson
Vamos considerar o conjunto de cidades incluídas em uma das subrotas
obtidas na solução do Modelo I:
S={Ma, Be, Sal}
Se limitarmos o número de variáveis associadas a essas cidades que
podem receber valor diferente de zero a 2, temos a seguinte
restrição:
xMa,Be + xMa,Sal + xBe,Ma + xBe,Sal + xSal,Ma + xSal,Be <= 2
Se incluirmos esta restrição ao Modelo I, eliminamos a sub-rota que
inclui as cidades acima, pois a solução anterior não é viável para o novo
modelo.
Reformulação II - Eliminação de subrotas:
Dantzig, Fulkerson e Johnson
Como fazer no caso geral?
Dado um subconjunto de cidades S
N
.
Podemos limitar o número de variáveis associadas a essas
cidades que podem receber valor diferente de zero a:
S 1
se incluirmos a seguinte restrição ao Modelo I:
 x
iS jS
ij
 S  1.
Impedimos assim soluções associadas a sub-rotas.
Reformulação II :
Modelo de otimização binária
min z    c x
n
n
i 1 j 1
ij
ij
sujeit o a
n
x
j 1
ij
n
x
i 1
ij
1
i  1,...,n
1
j  1,...,n
 x
iS jS
ij
 S 1
xij  0 / 1, i, j
S  {1...n}
Existem (2n  2) restrições
para eliminação de subrotas.
Reformulação II :
Modelo de otimização binária
•
Número exponencial de restrições para eliminação de
subrotas. O que fazer? (2n  2)
•
Gerar apenas as que são estritamente necessárias!
Algoritmo de Planos de Corte
•
Resolve o Problema da Designação associado(Relaxação)
•
Se a solução ótima é um circuito hamiltoniano (CH),
PARE.
•
Enquanto (it <nmax) ou (solução é um CH) faça:
•
Gere inequações para eliminar sub-rotas e
acrescente ao Problema Atual.
•
Resolva o novo Problema.
Problema do Caixeiro Viajante
Applegate, Bixby, Chvátal, Cook, 2003
(um milhão de Cidades)
Branch and Cut
Optima, v. 61, pg21
http://www.ise.ufl.edu/~optima/