Logística/Sistemas de distribuição/Escala de veículos/Formulação e notação básica

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.

Figura 1. Representação esquemática de um PEV simples, com um centro de distribuição e três rotas (preto, azul e vermelho).

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 é:


.