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 frota; distribuição e

recolhimento de produtos; coleta de lixo;

planejamento de rotas aéreas.

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 / Capacitado

• 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 Qk = 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

VTXZ −

=