Figura 1. Representação esquemática de um PEV simples, com um centro de distribuição e três rotas (preto, azul e vermelho).
O problema de escala de veículos (PEV) pode ser definido num gráfico
(Dorronsoro, 2007b), como o que se pode observar na Figura 1.
A notação utilizada é:
é um conjunto de vértices, onde:
- considerando um centro de distribuição localizado em
,
- então,
é o conjunto de
cidades.
é um conjunto de arcos.
é uma matriz de custos ou distâncias não-negativas
entre os clientes
e
.
é vector das encomendas dos clientes.
é a rota do veiculo
.
é o número de veículos (todos idênticos), em que a cada veículo é afectada uma rota.
Quando
para todos os
o problema é simétrico e é comum substituir
por
.
A cada vértice
em
está associada uma quantidade
de alguns produtos a entregar por um veículo.
O PEV consiste em determinar um conjunto de
rotas de veículos com o custo total mínimo, começando e terminando no centro de distribuição, tais que cada vértice de
seja visitado exactamente uma vez por um veículo.
Para um cálculo mais fácil em computador, pode-se definir
, um limite inferior do número de veículos necessários para atender os clientes do conjunto
.
Considerando
o tempo necessário para descarregar a quantidade
do veículo em
, a duração total de qualquer rota (deslocação mais tempo de serviço) não pode ultrapassar um limite
. Neste contexto, o custo
representa o tempo de deslocação entre cidades.
Uma solução viável é dada por:
- uma partição
de
;
- uma permutação
de
especificando a ordem dos clientes na rota
.
O custo de uma dada rota (
), onde
e
(
denomina o centro de distribuição), é dado por:
.
A rota
é viável se o veículo parar uma única vez em cada cliente e a duração total da rota não exceder um limite pré definido
:
.
O custo da solução
do problema é:
.