arq0067_0

Prévia do material em texto

Modelos Matemáticos para o Modelos Matemáticos para o 
Planejamento Estratégico Planejamento Estratégico 
em Logísticaem Logística
Roberto Roberto DiéguezDiéguez GalvãoGalvão
PPrograma de Engenharia de Produção
COPPE/UFRJ
SPOLM’2004 (Dez. 2004)
Tópicos AbordadosTópicos Abordados
IntroduçãoIntrodução
Logística EmpresarialLogística Empresarial
Problemas Estratégicos, Táticos e Problemas Estratégicos, Táticos e 
OperacionaisOperacionais
Métodos Quantitativos em LogísticaMétodos Quantitativos em Logística
Localização de InstalaçõesLocalização de Instalações
Problemas de DistribuiçãoProblemas de Distribuição
IntroduçãoIntrodução
Aumentar EficiênciaAumentar Eficiência
Agregar ValorAgregar Valor
Reduzir CustosReduzir Custos
Focar no ClienteFocar no Cliente
LogísticaLogística
Gerenciamento da Cadeia de Gerenciamento da Cadeia de 
SuprimentosSuprimentos
EstratégiaEstratégia
Definições de LogísticaDefinições de Logística
É o ramo da ciência militar relacionado à obtenção, É o ramo da ciência militar relacionado à obtenção, 
manutenção e transporte de material, pessoas e manutenção e transporte de material, pessoas e 
facilidades (Dicionário facilidades (Dicionário WebsterWebster, 1993)., 1993).
É o processo de planejar, implementar e controlar o É o processo de planejar, implementar e controlar o 
fluxo e a armazenagem, fluxo e a armazenagem, a custos competitivosa custos competitivos, de , de 
matérias primas, produtos intermediários, produtos matérias primas, produtos intermediários, produtos 
acabados e informação, do ponto de origem ao acabados e informação, do ponto de origem ao 
ponto de consumo (ponto de utilização), ponto de consumo (ponto de utilização), com o com o 
objetivo deobjetivo de atender às necessidades do clienteatender às necessidades do cliente
((Council of Logistics ManagementCouncil of Logistics Management, 1962)., 1962).
Missão da LogísticaMissão da Logística
A missão da Logística é colocar as A missão da Logística é colocar as 
mercadorias e serviços desejados no mercadorias e serviços desejados no 
local apropriado, no instante correto e local apropriado, no instante correto e 
nas condições desejadas pelo nas condições desejadas pelo 
clientecliente, , da forma mais eficiente da forma mais eficiente 
possível para a empresapossível para a empresa..
Exemplo de um Sistema LogísticoExemplo de um Sistema Logístico
Fontes
Fábricas
Depósitos
C o n s u m i d o r e s
Suprimento
Distribuição
Transferência
Entrega
Logística EmpresarialLogística Empresarial
É uma área de estudos relativamente nova, se É uma área de estudos relativamente nova, se 
comparada com áreas tradicionais como finanças, comparada com áreas tradicionais como finanças, 
marketing marketing e produção.e produção.
Empresas tradicionalmente se ocupam, há muito Empresas tradicionalmente se ocupam, há muito 
tempo, das atividades de transporte e estocagem tempo, das atividades de transporte e estocagem 
de mercadorias.de mercadorias.
A novidade trazida pela A novidade trazida pela Logística Empresarial Logística Empresarial é o é o 
conceito do conceito do Gerenciamento CoordenadoGerenciamento Coordenado dessas dessas 
atividades.atividades.
Modelo de Logística EmpresarialModelo de Logística Empresarial
JI
T 
II
M
R
P 
/ D
RP B
2BQ
R
C
PF
R
D
R
P
M
R
P
V
M
I
JI
T
D
R
P/
D
R
P
C
ro
ss
 D
oc
ki
ng
B
2B
/E
C
RF
O
R
N
E
C
E
D
O
R
E
S
F
O
R
N
E
C
E
D
O
R
E
S
C
L
I
E
N
T
E
S
C
L
I
E
N
T
E
S
Previsão de 
Demanda
Previsão de 
Demanda ComprasCompras OperaçõesOperações
Gestão de 
Estoques
Gestão de 
Estoques DistribuiçãoDistribuição
Serviço ao 
Cliente
Serviço ao 
Cliente
Medidas de 
Performance
Medidas de 
Performance
Fluxo do ProdutoFluxo do Produto
Fluxo de InformaçãoFluxo de Informação
EstratégiaEstratégia LogísticaLogística
JI
T 
II
M
R
P 
/ D
RP B
2BQ
R
C
PF
R
D
R
P
M
R
P
V
M
I
JI
T
D
R
P/
D
R
P
C
ro
ss
 D
oc
ki
ng
B
2B
/E
C
RF
O
R
N
E
C
E
D
O
R
E
S
F
O
R
N
E
C
E
D
O
R
E
S
C
L
I
E
N
T
E
S
C
L
I
E
N
T
E
S
Previsão de 
Demanda
Previsão de 
Demanda ComprasCompras OperaçõesOperações
Gestão de 
Estoques
Gestão de 
Estoques DistribuiçãoDistribuição
Serviço ao 
Cliente
Serviço ao 
Cliente
Medidas de 
Performance
Medidas de 
Performance
Fluxo do ProdutoFluxo do Produto
Fluxo de InformaçãoFluxo de Informação
EstratégiaEstratégia LogísticaLogística
AtividadesAtividades--Chave em Logística:Chave em Logística:
Problemas EstratégicosProblemas Estratégicos
Níveis de serviço para os clientesNíveis de serviço para os clientes
Localização de Fábricas e DepósitosLocalização de Fábricas e Depósitos
Gerência de EstoquesGerência de Estoques
TransporteTransporte
Seleção do modo e serviço de transporteSeleção do modo e serviço de transporte
Número e tamanho dos veículosNúmero e tamanho dos veículos
Roteamento de veículosRoteamento de veículos
Atividades de Apoio em Logística: Atividades de Apoio em Logística: 
Problemas Táticos e OperacionaisProblemas Táticos e Operacionais
ArmazenamentoArmazenamento
LayLay--out de facilidadesout de facilidades
Manuseio de MateriaisManuseio de Materiais
ComprasCompras
EmpacotamentoEmpacotamento
Manutenção do Sistema de InformaçõesManutenção do Sistema de Informações
Projeto de um Sistema LogProjeto de um Sistema Logíísticostico
Níveis de Serviço ao Cliente
Níveis de Serviço ao Cliente
Decisões sobre Localização
Número, tamanho e localização das 
instalações.
Posicionamento dos estoques na 
cadeia de suprimentos.
Alocação de instalações a pontos de 
suprimentos e demanda.
Armazéns próprios ou de terceiros.
Decisões sobre Estoque
Definição do giro dos itens
Definição dos níveis de estoque de 
segurança
Estratégia puxada ou empurrada
Seleção de métodos de controle
Decisões sobre Transporte
Definição dos modais de transporte.
Programação e roteamento de 
veículos.
Consolidação dos embarques.
Tamanho da frota.
Níveis de Serviço ao Cliente
Níveis de Serviço ao Cliente
Decisões sobre Localização
Número, tamanho e localização das 
instalações.
Posicionamento dos estoques na 
cadeia de suprimentos.
Alocação de instalações a pontos de 
suprimentos e demanda.
Armazéns próprios ou de terceiros.
Decisões sobre Estoque
Definição do giro dos itens
Definição dos níveis de estoque de 
segurança
Estratégia puxada ou empurrada
Seleção de métodos de controle
Decisões sobre Transporte
Definição dos modais de transporte.
Programação e roteamento de 
veículos.
Consolidação dos embarques.
Tamanho da frota.
Técnicas de SoluçãoTécnicas de Solução
Métodos Exatos (Soluções Ótimas)Métodos Exatos (Soluções Ótimas)
Programação Linear (PL)Programação Linear (PL)
Programação Inteira (PI)Programação Inteira (PI)
Outros métodos para a solução de problemas de Outros métodos para a solução de problemas de 
otimização combinatóriaotimização combinatória
Métodos Heurísticos (Soluções Aproximadas)Métodos Heurísticos (Soluções Aproximadas)
Métodos apropriados a problemas específicosMétodos apropriados a problemas específicos
Métodos análogos a processos físicos/da natureza; Métodos análogos a processos físicos/da natureza; 
Metaheurísticas:Metaheurísticas:
Simulated AnnealingSimulated Annealing, Algoritmos Genéticos; Busca Tabu; , Algoritmos Genéticos; Busca Tabu; 
Busca DispersaBusca Dispersa
Ferramentas UtilizadasFerramentas Utilizadas
“Pacotes” computacionais desenvolvidos para uso “Pacotes” computacionais desenvolvidos para uso 
comercial:comercial:
CPLEX, LINDO (Programação Linear, Inteira, Quadrática)CPLEX, LINDO (Programação Linear, Inteira, Quadrática)
MINOS (Programação NãoMINOS (Programação Não--Linear)Linear)
Códigos computacionais desenvolvidos para Códigos computacionais desenvolvidos para 
problemas específicosproblemas específicos
Desenvolvidos em universidades e centros de pesquisaDesenvolvidos em universidades e centros de pesquisa
Desenvolvidos em empresas de grande porteDesenvolvidos em empresas de grande porte
A Localização em Sistemas LogísticosA Localização em Sistemas LogísticosAplicações nos Setores Público e PrivadoAplicações nos Setores Público e Privado
No Setor PúblicoNo Setor Público
Localização de Escolas, HospitaisLocalização de Escolas, Hospitais
Localização de Serviços de EmergênciaLocalização de Serviços de Emergência
No Setor PrivadoNo Setor Privado
Localização de Fábricas (quantas, onde?)Localização de Fábricas (quantas, onde?)
Localização de Depósitos de Distribuição (idem)Localização de Depósitos de Distribuição (idem)
Determinação de Áreas de InfluênciaDeterminação de Áreas de Influência
Uso de Modelos Matemáticos para Redução de CustosUso de Modelos Matemáticos para Redução de Custos
Localização de InstalaçõesLocalização de Instalações
Decisões de localização envolvem determinar :Decisões de localização envolvem determinar :
Quantas facilidades (fábricas, depósitos, armazéns, Quantas facilidades (fábricas, depósitos, armazéns, 
centros de serviço) deve a companhia possuir ?centros de serviço) deve a companhia possuir ?
De que tamanho e onde devem estar elas localizados ?De que tamanho e onde devem estar elas localizados ?
De tal forma a se alcançar o nível de serviço desejado ao De tal forma a se alcançar o nível de serviço desejado ao 
menor custo de distribuição.menor custo de distribuição.
AbordagensAbordagens
Modelado como um problema de programação matemática;Modelado como um problema de programação matemática;
Usando heurísticas e metaUsando heurísticas e meta--heurísticas;heurísticas;
Através de estudos de cenários.Através de estudos de cenários.
Perspectiva HistóricaPerspectiva Histórica
Precursor: A. Weber, 1909Precursor: A. Weber, 1909
Localização de um centro de distribuição com o Localização de um centro de distribuição com o 
objetivo de minimizar as distâncias ponderadas (pelo objetivo de minimizar as distâncias ponderadas (pelo 
peso/volume transportado) percorridas em relação a peso/volume transportado) percorridas em relação a 
duas fontes de matéria prima e um mercado duas fontes de matéria prima e um mercado 
consumidor.consumidor.
Custos de transporte lineares com a distância e com o Custos de transporte lineares com a distância e com o 
peso transportado.peso transportado.
Fatores que Influenciam a LocalizaçãoFatores que Influenciam a Localização
Proximidade (Custo Logístico);Proximidade (Custo Logístico);
Oferta de mãoOferta de mão--dede--obra (e produtividade);obra (e produtividade);
Disponibilidade de insumos (energia, transporte, Disponibilidade de insumos (energia, transporte, 
comunicação, água, solo);comunicação, água, solo);
Disponibilidade de financiamentos;Disponibilidade de financiamentos;
Tamanho do mercado local;Tamanho do mercado local;
Fatores políticos, legais, ambientais e sociais.Fatores políticos, legais, ambientais e sociais.
Modelos Matemáticos de LocalizaçãoModelos Matemáticos de Localização
Recebem atenção de economistas, geógrafos, Recebem atenção de economistas, geógrafos, 
profissionais da Pesquisa Operacional (PO).profissionais da Pesquisa Operacional (PO).
Enfoque varia de acordo com a origem Enfoque varia de acordo com a origem 
profissional:profissional:
Enfoque macroeconômico: Economistas, Geógrafos;Enfoque macroeconômico: Economistas, Geógrafos;
Enfoque microeconômico: Modelos Normativos (PO).Enfoque microeconômico: Modelos Normativos (PO).
Modelos NormativosModelos Normativos
EnfoqueEnfoque: Suprimento de dada área geográfica a partir de : Suprimento de dada área geográfica a partir de 
centros de distribuição de mercadorias ou serviços.centros de distribuição de mercadorias ou serviços.
ObjetivoObjetivo: Determinar número e localização de centros : Determinar número e localização de centros 
supridores de clientes e respectivas áreas de influência, supridores de clientes e respectivas áreas de influência, 
minimizando custos ou maximizando o lucro, respeitadas minimizando custos ou maximizando o lucro, respeitadas 
restrições operacionais.restrições operacionais.
Necessário o uso de técnicas e ferramentas sofisticadas para Necessário o uso de técnicas e ferramentas sofisticadas para 
a solução dos modelos matemáticos.a solução dos modelos matemáticos.
Avanço das tecnologias computacionais vem permitindo o Avanço das tecnologias computacionais vem permitindo o 
desenvolvimento de sistemas de fácil utilização pelo usuário desenvolvimento de sistemas de fácil utilização pelo usuário 
leigo.leigo.
Exemplos de Modelos NormativosExemplos de Modelos Normativos
MODELOS MINISOMAMODELOS MINISOMA
Minimizam distância total percorrida no sistema de Minimizam distância total percorrida no sistema de 
distribuição (custo médio de entrega)distribuição (custo médio de entrega)
MODELOS MINIMAXMODELOS MINIMAX
Minimizam custo de entrega a clientes de localização Minimizam custo de entrega a clientes de localização 
menos favorecidamenos favorecida
MODELOS DE COBERTURA (EMERGÊNCIA)MODELOS DE COBERTURA (EMERGÊNCIA)
Maximizam número de usuários que podem ser Maximizam número de usuários que podem ser 
alcançados em tempo inferior a um valor crítico préalcançados em tempo inferior a um valor crítico pré--
determinadodeterminado
CentroCentro
Centros de emergência Centros de emergência -- MIN MIN --MAXMAX
Problemas Simples de LocalizaçãoProblemas Simples de Localização
AnticentroAnticentro
Atividades indesejáveis Atividades indesejáveis -- MAXMAX--MINMIN
MedianaMediana
Centros de distribuição Centros de distribuição -- MIN MIN -- SOMASOMA
 1 2 3 4 5 6 7 8 Min + Max + S+ 
1 0 18 45 27 81 54 36 90 18 90 351
2 42 0 21 49 35 28 14 56 14 56 245
3 15 35 0 50 20 25 55 30 15 55 230
4 32 64 40 0 16 56 24 48 16 64 280
5 30 42 54 18 0 24 48 36 18 54 252
6 24 44 36 48 32 0 56 28 24 56 268
7 21 36 48 72 42 57 0 24 21 72 300
8 96 48 88 72 40 80 64 0 40 96 488
Min 
+ 15 18 21 18 16 24 14 24 
Max 
+ 96 64 88 72 81 80 64 90 
S
+ 
260 287 332 336 266 324 297 312 
 
Modelos Minisoma: Problema das Modelos Minisoma: Problema das 
pp--MedianasMedianas
Encontrar a localização de Encontrar a localização de pp facilidades em uma facilidades em uma 
rede de modo que o custo total seja minimizado. rede de modo que o custo total seja minimizado. 
O custo de servir a demanda do cliente O custo de servir a demanda do cliente 
localizado no nó i é dado pelo produto da localizado no nó i é dado pelo produto da 
demanda do cliente i pela distância entre o nó i demanda do cliente i pela distância entre o nó i 
e a facilidade mais próxima a ele.e a facilidade mais próxima a ele.
Teorema (Hakimi, 1965): Pelo menos uma das Teorema (Hakimi, 1965): Pelo menos uma das 
soluções ótimas do problema das soluções ótimas do problema das pp--medianas medianas 
consiste em localizar as consiste em localizar as pp facilidades sobre os facilidades sobre os 
nós da rede.nós da rede.
{ } m. , ... 1,=j n; ..., 1,=i 0,1 ,
m , ... 1, =j n; ..., 1,=i ,0
 ,
n , ... 1, =i ,1
:
1
1
1 1
∈
≤−
=
=
=
∑
∑
∑∑
=
=
= =
jij
jij
m
j
j
m
j
ij
n
i
m
j
ijiji
yx
yx
py
x
asujeito
xdhZMinimizar
Problema das Problema das pp--Medianas: Medianas: 
Formulação MatemáticaFormulação Matemática
Problema das Problema das pp--medianas medianas –– Heurística:Heurística:
Algoritmo Guloso com MelhoriaAlgoritmo Guloso com Melhoria
Localize: primeira facilidade na localização ótima da 
1-mediana
Localize: próxima facilidade na localização ótima da 1-mediana 
(mantendo a localização das anteriores fixa)
Melhoria: Use um algoritmo de melhoramento (substituição 
de vértices, ou busca na vizinhança)
Foram localizadas as p 
facilidades ? 
Sim
Não
pp--Medianas: ExemploMedianas: Exemplo
pp--Medianas: Solução HeurísticaMedianas: Solução Heurística
{ } m. , ... 1,=j n; ..., 1,=i 0,1 ,
m , ... 1, =j n; ..., 1,=i ,0
m , ... 1, =j ,
n , ... 1, =i ,1
:
1
1
11 1
∈
≤−
≤
=
+=
∑
∑
∑∑∑
=
=
== =
jij
jij
j
n
i
iji
m
j
ij
m
j
jj
n
i
m
j
ijij
yx
yx
bxa
x
asujeito
yvxcZMinimizar
Problemade Localização Capacitado:Problema de Localização Capacitado:
Formulação MatemáticaFormulação Matemática
Modelos de Localização Modelos de Localização MiniMaxMiniMax ––
Problema dos Problema dos pp--centroscentros
Problema dos Problema dos pp--centros: minimizar a centros: minimizar a 
distância máxima do cliente (mais distância máxima do cliente (mais 
desfavorecido ) a um dos pdesfavorecido ) a um dos p--centros.centros.
Problema inverso (Cobertura): achar Problema inverso (Cobertura): achar 
o menor número de centros e sua o menor número de centros e sua 
localização de tal modo que todos os localização de tal modo que todos os 
clientes estejam localizados a uma clientes estejam localizados a uma 
distância menor que uma distância distância menor que uma distância 
crítica crítica -- prépré--estabelecida de pelo estabelecida de pelo 
menos um dos centros.menos um dos centros.
Aplicações práticas: centros de Aplicações práticas: centros de 
atendimento de emergênciaatendimento de emergência
( ){ }
( ) ( ){ }jidjSd
pS
jSdv
Min
MaxMin
p
p
Si
p
p
pj
JjS
,,
onde
,
∈
∈
=
=






6
6 4
8
2
2
Problemas de DistribuiçãoProblemas de Distribuição
ObjetivoObjetivo
Encontrar o melhor caminho que um veículo deve percorrer atravésEncontrar o melhor caminho que um veículo deve percorrer através de uma de uma 
rede de rodovias, ferrovias, hidrovias ou rotas aéreas.rede de rodovias, ferrovias, hidrovias ou rotas aéreas.
Tipos de problemasTipos de problemas
Uma única origem e um (ou vários) destinos diferentesUma única origem e um (ou vários) destinos diferentes
Problema do Caminho MínimoProblema do Caminho Mínimo
Várias origens e vários destinos diferentesVárias origens e vários destinos diferentes
Problema do TransporteProblema do Transporte
Origem e destino final coincidentesOrigem e destino final coincidentes
Problema do Caixeiro ViajanteProblema do Caixeiro Viajante
Problema de Roteamento de VeículosProblema de Roteamento de Veículos
O Problema do Caminho Mínimo O Problema do Caminho Mínimo -- PCMPCM
Uma distribuidora de jornais está se instalando na cidade 1 e goUma distribuidora de jornais está se instalando na cidade 1 e gostaria de saber qual a staria de saber qual a 
menor distância até cada uma das cidades bem como os percursos cmenor distância até cada uma das cidades bem como os percursos correspondentes.orrespondentes.
1
2
3
4
5
6
12
4
6 10
2
2
8
6
4
6
1
2
3
4
5
6
12
4
6 10
2
2
8
6
4
6
Solução do PCMSolução do PCM
Problema do Caixeiro Viajante Problema do Caixeiro Viajante -- PCVPCV
Seja um vendedor que tem que visitar Seja um vendedor que tem que visitar nn cidades. cidades. 
Ele começa na cidade 1 (cidadeEle começa na cidade 1 (cidade--base) e deve base) e deve 
visitar cada uma das (visitar cada uma das (nn--11) cidades restantes ) cidades restantes 
apenas uma vez, retornando à cidadeapenas uma vez, retornando à cidade--base.base.
O custo O custo cijcij da viagem entre qualquer par de da viagem entre qualquer par de 
cidades é conhecido (matriz de custos [cidades é conhecido (matriz de custos [cijcij]). O ]). O 
problema consiste em obter uma rota através das problema consiste em obter uma rota através das 
nn cidades que minimize o custo do trajeto total.cidades que minimize o custo do trajeto total.
Progresso na Solução do PCV Progresso na Solução do PCV 
(Métodos Exatos)(Métodos Exatos)
Dantzig/Fulkerson/Johnson (1954)Dantzig/Fulkerson/Johnson (1954) 4242
Karg/Thompson (1964)Karg/Thompson (1964) 5757
Held/Karp (1970)Held/Karp (1970) 6464
Miliotis (1975)Miliotis (1975) 9090
Smith (1977)Smith (1977) 6060
Grötschel (1977)Grötschel (1977) 120120
Crowder/Padberg (1977)Crowder/Padberg (1977) 318318
Padberg/Rinaldi (1986)Padberg/Rinaldi (1986) 532532
Grötschel/Holand (1986)Grötschel/Holand (1986) 666666
P/R; G/H (1987)P/R; G/H (1987) 10021002
Padberg/Rinaldi (1987)Padberg/Rinaldi (1987) 23922392
PCV PCV –– Métodos Heurísticos de SoluçãoMétodos Heurísticos de Solução
Karp (1972) provou que o PCV é um problema Karp (1972) provou que o PCV é um problema 
NPNP--Completo. Nesse contexto tornaCompleto. Nesse contexto torna--se se 
importante o desenvolvimento de métodos importante o desenvolvimento de métodos 
heurísticos eficientes para a solução do heurísticos eficientes para a solução do 
problema.problema.
Métodos heurísticos para o PCV podem ser Métodos heurísticos para o PCV podem ser 
classificados em 4 classes:classificados em 4 classes:
Métodos de construção de rotas;Métodos de construção de rotas;
Métodos de melhoramento de rotas;Métodos de melhoramento de rotas;
Procedimentos compostos;Procedimentos compostos;
MetaMeta--heurísticas.heurísticas.
PCV PCV -- Heurística do vizinho mais próximoHeurística do vizinho mais próximo
C id a d e s 1 2 3 4 5 6 7
1 X X X 4 0 4 2 7 0 4 9 0 4 9 0 3 3 8 2 8 8
2 4 0 4 X X X 6 1 8 8 9 0 8 9 0 4 6 0 3 2 0
3 2 7 0 6 1 8 X X X 3 6 0 3 6 0 2 1 0 2 4 0
4 4 9 0 8 9 0 3 6 0 X X X 7 8 3 9 0 3 3 0
5 4 9 0 8 9 0 3 6 0 7 8 X X X 3 9 0 3 3 0
6 3 3 8 4 6 0 2 1 0 3 9 0 3 9 0 X X X 2 7 0
7 2 8 8 3 2 0 2 4 0 3 3 0 3 3 0 2 7 0 X X X
1
2
3
7
54
6
2528
ComeçaComeça--se de um vértice se de um vértice 
arbitrário e formaarbitrário e forma--se o se o 
circuito unindocircuito unindo--se se 
sucessivamente, ao último sucessivamente, ao último 
vértice adicionado`a rota, vértice adicionado`a rota, 
seu vizinho mais próximo seu vizinho mais próximo 
ainda não pertencente à ainda não pertencente à 
mesma. É necessário mesma. É necessário 
evitar a formação de subevitar a formação de sub--
rotas a cada passo do rotas a cada passo do 
algoritmo.algoritmo.
PCV PCV –– Heurística de Melhoramento Heurística de Melhoramento 
rr--otimal de Linotimal de Lin
ComeçaComeça--se de uma solução inicial para o PCV, por se de uma solução inicial para o PCV, por 
exemplo obtida pela heurística VMP.exemplo obtida pela heurística VMP.
RemoveRemove--se se rr arcos dessa solução, o que produz arcos dessa solução, o que produz rr rotas rotas 
desconectadas. Essas rotas podem ser religadas de desconectadas. Essas rotas podem ser religadas de 
diferentes maneiras, produzindo nova solução para o diferentes maneiras, produzindo nova solução para o 
problema. Chamaproblema. Chama--se essa operação de uma se essa operação de uma rr--troca.troca.
A Solução é dita A Solução é dita rr--ótima se nenhuma ótima se nenhuma rr--troca produz uma troca produz uma 
solução de custo menor.solução de custo menor.
Essa heurística é de tempo polinomial em Essa heurística é de tempo polinomial em nn mas mas 
exponencial em exponencial em rr. A heurística na prática só é utilizada . A heurística na prática só é utilizada 
para para r r ≤≤3.3.
Ilustração da Heurística Ilustração da Heurística rr--otimal de otimal de LinLin
(r = 3)(r = 2)
O Problema do Roteamento de Veículos O Problema do Roteamento de Veículos -- PRVPRV
O Problema de Roteamento de Veículos (PRV) é um O Problema de Roteamento de Veículos (PRV) é um 
nome genérico dado a uma classe de problemas nos nome genérico dado a uma classe de problemas nos 
quais “clientes” são visitados por “veículos”.quais “clientes” são visitados por “veículos”.
Em algumas aplicações práticas a operação de entrega Em algumas aplicações práticas a operação de entrega 
((deliverydelivery) pode ser uma coleta, coleta e/ou entrega ou não ) pode ser uma coleta, coleta e/ou entrega ou não 
corresponder a nenhuma das duas operações. “Clientes”e corresponder a nenhuma das duas operações. “Clientes”e 
“Veículos” tomam diferentes formas, algumas das quais “Veículos” tomam diferentes formas, algumas das quais 
não representam transações físicas.não representam transações físicas.
Um grande número de objetivos e restrições podem ser Um grande número de objetivos e restrições podem ser 
utilizados para definir PRV’s de naturezas diversas.utilizados para definir PRV’s de naturezas diversas.
Aplicações de Problemas de Aplicações de Problemasde 
Roteamento de VeículosRoteamento de Veículos
Distribuição de mercadorias e serviços a partir de Distribuição de mercadorias e serviços a partir de 
depósitos centrais;depósitos centrais;
Coleta de correspondência de caixas coletoras dos Coleta de correspondência de caixas coletoras dos 
correios;correios;
Coleta e entrega de crianças por ônibus escolares;Coleta e entrega de crianças por ônibus escolares;
Roteamento de helicópteros na indústria do petróleo Roteamento de helicópteros na indústria do petróleo 
(exploração (exploração offshore offshore na Bacia de Campos);na Bacia de Campos);
Roteamento de manutenção preventiva em fábricas.Roteamento de manutenção preventiva em fábricas.
O Problema de Roteamento de VeO Problema de Roteamento de Veíículos culos 
ClCláássico (PRV): Caracterssico (PRV): Caracteríísticas Principaissticas Principais
VeVeíículos iniciam o roteamento a partir de um depculos iniciam o roteamento a partir de um depóósito sito 
central; hcentral; háá restrirestriçõções de capacidade [vees de capacidade [veíículos] e tempo culos] e tempo 
(dist(distâância) mncia) mááximo(a) [rotas];ximo(a) [rotas];
Cada cliente tem sua demanda totalmente suprida Cada cliente tem sua demanda totalmente suprida 
exatamente por um veexatamente por um veíículo e tempos de serviculo e tempos de serviçço so sãão o 
levados em consideralevados em consideraçãção;o;
O objetivo consiste na definiO objetivo consiste na definiçãção de rotas de entrega o de rotas de entrega 
(coleta) de custo m(coleta) de custo míínimo, para uma frota de venimo, para uma frota de veíículos culos 
homoghomogêênea, definida a priori.nea, definida a priori.
Heurísticas para o PRV Clássico com Heurísticas para o PRV Clássico com 
Base no Cálculo de EconomiasBase no Cálculo de Economias
Introduzidàs por Clarke e Wright (1964). Modificações/extensõesIntroduzidàs por Clarke e Wright (1964). Modificações/extensões
propostas com base no conceito de economias definido pelos autorpropostas com base no conceito de economias definido pelos autores.es.
Seja um depósito supridor de Seja um depósito supridor de n n clientes. Se cada cliente for suprido clientes. Se cada cliente for suprido 
de forma exclusiva por 1 veículo, a distância total viajada pelade forma exclusiva por 1 veículo, a distância total viajada pela frota é frota é 
22ΣΣi=1,ni=1,nddoioi, d, doioi distdistâância entre o depncia entre o depóósito e o cliente sito e o cliente ii..
Se for possSe for possíível interligar os clientes vel interligar os clientes i i e e j j sem violar as restrisem violar as restriçõções do es do 
problema, isto produz uma economiaproblema, isto produz uma economia
SSijij=2d=2doioi+2d+2dojoj--(d(doioi+d+dojoj+d+dijij)=d)=doioi+d+dojoj--ddij.ij.
SSij ij é nãoé não--negativa e corresponde à economia obtida ao se alocar os negativa e corresponde à economia obtida ao se alocar os 
clientes clientes i i e e jj a uma mesma rota.a uma mesma rota.
Quanto maior SQuanto maior Sijij, mais desejável a interligação dos clientes , mais desejável a interligação dos clientes ii e e jj..
Ilustração da Idéia de Clarke e WrightIlustração da Idéia de Clarke e Wright
Clientes i e j interligados:
Sij=dio+doj-dij
Clientes i e j atendidos separadamente
doi
dio
dij
doj
djo
O
i j
O
i j
doi
dij
djo
dio doj
O Algoritmo de Clarke e WrightO Algoritmo de Clarke e Wright
1. Calcule as economias 1. Calcule as economias SSijij para todos os possíveis pares de clientes para todos os possíveis pares de clientes ((ii,,jj));;
2. Ordene as economias em uma lista, em ordem decrescente de val2. Ordene as economias em uma lista, em ordem decrescente de valor;or;
3. Começando do topo da lista:3. Começando do topo da lista:
(3i) Utilize o arco correspondente à primeira economia da lista (3i) Utilize o arco correspondente à primeira economia da lista para expandir para expandir 
uma das 2 extremidades das rotas em construção ou para interligauma das 2 extremidades das rotas em construção ou para interligar r 
rotas;rotas;
(3ii) Se o conjunto de rotas estiver vazio, ou se as rotas em co(3ii) Se o conjunto de rotas estiver vazio, ou se as rotas em construção não nstrução não 
puderem ser expandidas ou interligadas através desse arco, se popuderem ser expandidas ou interligadas através desse arco, se possível ssível 
utilizeutilize--o para iniciar uma nova rota. Caso contrário despreze o arco o para iniciar uma nova rota. Caso contrário despreze o arco 
corrente e considere o arco correspondente à próxima economia;corrente e considere o arco correspondente à próxima economia;
(3iii) Repita (3i) e (3ii) até esgotar a lista de economias.(3iii) Repita (3i) e (3ii) até esgotar a lista de economias.
4. As rotas formadas no Passo 3 constituem uma solução viável pa4. As rotas formadas no Passo 3 constituem uma solução viável para o PRV.ra o PRV.
Problemas de Roteamento de VeículosProblemas de Roteamento de Veículos
Tipos de restriçõesTipos de restrições
Restrições de frotaRestrições de frota
Restrições de precedênciaRestrições de precedência
Restrições temporaisRestrições temporais
GeneralizaçõesGeneralizações
Múltiplos depósitosMúltiplos depósitos
Frota não homogêneaFrota não homogênea
Demanda incerta dos clientesDemanda incerta dos clientes
Múltiplos objetivosMúltiplos objetivos
O PRV Clássico O PRV Clássico –– Formulação MatemáticaFormulação Matemática
Min c xij ij
k
k
M
j
n
i
n
===
∑∑∑
100
x j nij
k
k
M
i
n
==
∑∑ = =
10
1 1 2, ,...,
( )x x j n k Mijk jik
i
n
− = = =
=
∑
0
0 01 2 1 2, , ,..., ; , , ...
x k Mj
k
j
n
0
0
1 1 2
=
∑ ≤ = , , ...
q x Q k Mi ij
k
j
n
i
n
==
∑∑ ≤ =
01
1 2, ,...
c x L k Mij ij
k
i
n
j
n
==
∑∑ ≤ =
00
1 2, ,...,
{ }x i j n k Mijk ∈ = =0 1 0 1 2 1 2, , , , , ..., ; , , ...
Min c xij ij
k
k
M
j
n
i
n
===
∑∑∑
100
x j nij
k
k
M
i
n
==
∑∑ = =
10
1 1 2, ,...,
( )x x j n k Mijk jik
i
n
− = = =
=
∑
0
0 01 2 1 2, , ,..., ; , , ...
x k Mj
k
j
n
0
0
1 1 2
=
∑ ≤ = , , ...
q x Q k Mi ij
k
j
n
i
n
==
∑∑ ≤ =
01
1 2, ,...
c x L k Mij ij
k
i
n
j
n
==
∑∑ ≤ =
00
1 2, ,...,
{ }x i j n k Mijk ∈ = =0 1 0 1 2 1 2, , , , , ..., ; , , ...
Problemas de Roteamento de Veículos Problemas de Roteamento de Veículos 
(PRV’s) com Serviço de Entrega e Coleta(PRV’s) com Serviço de Entrega e Coleta
PRV com Cargas de Retorno (“backhaul”) PRV com Cargas de Retorno (“backhaul”) 
[PRV_BH] [PRV_BH] 
PRV com Serviço de Entrega e Coleta (PRV_PDS)PRV com Serviço de Entrega e Coleta (PRV_PDS)
Problema “DialProblema “Dial--aa--Ride” Múltiplo (mRide” Múltiplo (m--DRP)DRP)
Problema de Entrega Expressa (EDP)Problema de Entrega Expressa (EDP)
PRV com Serviços de Entrega e Coleta PRV com Serviços de Entrega e Coleta 
Simultâneos(VRP_SPDS)Simultâneos(VRP_SPDS)
PRV com Cargas de Retorno (VRP_BH)PRV com Cargas de Retorno (VRP_BH)
Delivery Route 
Depot 
Delivery Client
Pick-up Client 
Pick-up Route 
PRV com Serviço de Entrega e ColetaPRV com Serviço de Entrega e Coleta
(VRP_PDS)(VRP_PDS)
 Pick-up & 
Delivery Route
Depot 
Delivery Client
Pick-up Client 
Problema “Multiple DialProblema “Multiple Dial--aa--Ride” (mRide” (m--DRP)DRP)
 
1
2
3
4
1
2
3
4
Pick-up & 
Delivery Route
Depot
Client 1 Delivery 
Client 1 Pick-up 1 
1
Problema de Entrega Expressa (EDP)Problema de Entrega Expressa (EDP)
 
Pick-up Phase Delivery Phase
Depot 
Pick-up & Delivery Client
PRV com Entrega e Coleta SimultâneasPRV com Entrega e Coleta Simultâneas
(VRP_SPDS)(VRP_SPDS)
 
Pick-up & 
Delivery Route 
Depot 
Pick-up & Delivery Client
MetaheurMetaheuríísticas para PRVsticas para PRV’’ss
Simulated Annealing: Osman (1993);Simulated Annealing: Osman (1993);
Busca Tabu: Taillard (1993) e Rochat e Busca Tabu: Taillard (1993) e Rochat e 
Taillard (1995);Taillard (1995);
Algoritmos GenAlgoritmos Genééticos: Baker e Ayechew ticos: Baker e Ayechew 
(2003) e Prins (2003);(2003) e Prins (2003);
Outras (GRASP, ColOutras (GRASP, Colôônia de Formigas).nia de Formigas).
FormulaçãoMatemática de VRP_SPDS (1)Formulação Matemática de VRP_SPDS (1)
Notação:
V: conjunto de clientes (Nós de demanda), onde N=|V| é o número total de clientes;
V0: conjunto de clientes mais depósito (cliente 0): V0=V∪{0};
VD (VP): conjunto de clientes de entrega (coleta), onde ND=|VD| e NP=|VP| são 
respectivamente o número de clientes de entrega e coleta;
cij: custo da viagem (distância) entre os clientes i e j;
pi: demanda de coleta do cliente i∈V, pi≥0;
di: demanda de entrega do cliente i∈V, di≥0;
Q: Capacidade do veículo;
NV: Número máximo de veículos.
Variáveis de Decisão
xij=1 se o arco (i,j) pertence ao conjunto ótimo de rotas, xij=0 caso contrário;
yij: demanda coletada em clientes roteados até o nó i (incluindo o nó i) e transportada 
utilizando o arco (i,j);
zij: demanda a ser entregue a clientes roteados após o nó i e transportada utilizando o 
arco (i,j).
Formulação Matemática de VRP_SPDS (2)Formulação Matemática de VRP_SPDS (2)
∑∑
= =
N
i
N
j
iji j xcM in 
0 0
 (1)
Subject to :
N1 ,.. . ,j ,1 
0
==∑
=
N
i
ijx (2)
N1 ,.. . ,i ,1 
0
==∑
=
N
j
ijx (3)
N V 
1
0 ≤∑
=
N
j
jx , (4)
∑ ∑
= =
≠∀=
N
0
j
0
ijj i 0j ,p y - y 
i
N
i
(5)
∑ ∑
= =
≠∀=
N
i
j
N
i0 0
j ii j 0j ,d z - z (6)
N0 ,.. .,ji , ,Q x z y iji ji j =≤+ (7)
{ } N0 ,.. . , ji , ,1 0 , x ij =∈ (8)
N0 ,.. . , ji , 0 , y ij =≥ (9)
N0 ,. . . , ji , 0 . z ij =≥ (10)