Problema de Roteamento de Veículos (VRP)
1
Definição
• Um PRV consiste basicamente em estabelecer e
organizar rotas ou itinerários eficientes para veículos
realizarem entrega/captação de mercadorias.
• Dispondo de uma frota de k veículos idênticos ou não
e deseja-se atender um conjunto de n clientes, cada
um com uma demanda específica.
• Proposto por Golden e Wong em 1981, pertence à
classe dos problemas de otimização combinatória
NP-difíceis.
• Está associado a casos especiais como o problema do
carteiro rural (Rural Postman Problem- RPP) e o
problema do carteiro chinês com restrição de
capacidade (Capacitated Chinese Postman Problem CCPP).
• Também pode ser associado ao problema de
dimensionamento
de
recolhimento
produtos;
de
frota;
planejamento de rotas aéreas.
distribuição
coleta
de
e
lixo;
2
Definição
• Pode existir uma série de restrições:
o Restrições de unicidade: cada cliente só pode ser
servido por um e somente por um veículo.
o Restrições de capacidade da frota.
o Restrições de precedência.
o Restrições temporais.
• Outras características complicadoras:
o Múltiplos depósitos
o Frota não homogênea
o Demanda incerta dos clientes
o Múltiplos objetivos
• Rota ou percurso de veículo: seqüência de pontos
de entrega e/ou coleta que o veículo deve percorrer
ordenadamente,
iniciando
e
finalizando
num
depósito.
• Seqüenciamento (programação) de veículos numa
rota onde a cada ponto associa-se um tempo de
chegada e um tempo de partida, ou de início e fim do
serviço.
3
2
Tipos de problemas
• PRV (problema de roteamento de veículos) conjunto
de rotas que minimiza a distância percorrida pela
frota.
• PSV (problema de seqüenciamento de veículos)
veículos
devem
percorrer
os
pontos
numa
determinada ordem nos tempos especificados.
• PRSV (problema de seqüenciamento e roteamento de
veículos) quando os aspectos espacial e temporal se
combinam um não prevalece sobre o outro.
Caracterizado por:
o relação de precedência entre clientes;
o número de rotas inferior à frota de veículos,
o janelas de tempo, isto é, os clientes exigem o
atendimento dentro de um intervalo de tempo.
4
3
PRV-básico
• consiste em construir rotas que minimizem a
distância total percorrida pela frota de forma que:
o cada cliente deve ser visitado exatamente uma
vez e ter atendida a sua demanda,
o cada veículo inicia e termina sua rota no
depósito central,
o a demanda total de cada rota deve ser menor ou
igual a capacidade do veículo,
o o custo total (distância percorrida ou tempo de
viagem) de cada rota deve ser menor ou igual a
um determinado limite L dado.
5
Rotas, domicílios e frota
6
4
Modelagem
• O problema de roteamento de veículos pode ser
modelado como arcos de uma malha viária, com
restrição de capacidade;
• O objetivo é encontrar rotas que atendam todos os
clientes, satisfazendo a capacidade dos respectivos
veículos, e tais que os custos totais do transporte
sejam minimizados.
• Constantes:
o N = {0,..., n}, localidade 0 (zero) corresponde ao
vértice inicial, (ponto de partida dos veículos);
o A = {(i, j) | i ∈ N e j ∈ N}, possíveis ligações
entre as localidades (caminho entre paradas);
o cij = custo associado ao arco (i, j)
o qi = quantidade de pessoas em uma parada,
o Q = capacidade máxima de carga dos veículos
o k = 1, 2, 3,..., M, quantidade de veículos
disponíveis (tamanho da frota).
7
Modelagem
• Variáveis de decisão:
• Função objetivo:
• Restrições:
o parada j seja visitada por apenas um único
veículo, vindo de uma parada i,
o veículo saia da parada i vá em direção a uma
única parada j,
8
Modelagem
• Restrições:
o veículo não fique parado:
o cada veículo não percorrerá mais que uma rota:
o limita a quantidade de carga de cada,
o limita o custo da rota percorrida:
o evita a formação de círculos sem o nodo inicial.
ƒ S = o conjunto de todos os subciclos que
contém o depósito ‘0’.
9
Modelagem
10
5
Solução