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

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 $\ G(V,E)$ (Dorronsoro, 2007b), como o que se pode observar na Figura 1.

A notação utilizada é:

$\ V=\{v_{0},v_{1},\ ...\ ,v_{n}\}$ é um conjunto de vértices, onde:

considerando um centro de distribuição localizado em $\ v_{0}$ ,

então, $\ V'=V\backslash \{v_{0}\}$ é o conjunto de $\ n$ cidades.

$\ A={\big \{}{(v_{i},v_{j})}\ |\ {(v_{i},v_{j})}\in V;\ i\neq j{\big \}}$ é um conjunto de arcos.

$\ C$ é uma matriz de custos ou distâncias não-negativas $\ c_{ij}$ entre os clientes $\ v_{i}$ e $\ v_{j}$ .

$\ d$ é vector das encomendas dos clientes.

$\ R_{i}$ é a rota do veiculo $\ i$ .

$\ m$ é o número de veículos (todos idênticos), em que a cada veículo é afectada uma rota.

Quando $\ c_{ij}=c_{ji}$ para todos os $\ (v_{i},v_{j})\in A$ o problema é simétrico e é comum substituir $\ A$ por

$\ E={\big \{}{(v_{i},v_{j})}\ |\ v_{i},v_{j}\in V;\ i<j{\big \}}$ .

A cada vértice $\ v_{i}$ em $\ V'$ está associada uma quantidade $\ q_{i}$ de alguns produtos a entregar por um veículo.

O PEV consiste em determinar um conjunto de $\ m$ 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 $\ V'$ seja visitado exactamente uma vez por um veículo.

Para um cálculo mais fácil em computador, pode-se definir $\ b(V)=\textstyle \sum _{v_{i}\in V}d_{i}/{C}$ , um limite inferior do número de veículos necessários para atender os clientes do conjunto $\ V$ .

Considerando $\ \delta _{i}$ o tempo necessário para descarregar a quantidade $\ q_{i}$ do veículo em $\ v_{i}$ , a duração total de qualquer rota (deslocação mais tempo de serviço) não pode ultrapassar um limite $\ D$ . Neste contexto, o custo $\ c_{ij}$ representa o tempo de deslocação entre cidades.

Uma solução viável é dada por:

uma partição $\ {R_{1},\ ...\ ,R_{m}}$ de $\ V$ ;

uma permutação $\ \sigma _{i}$ de $\ R_{i}\cup {0}$  especificando a ordem dos clientes na rota $\ i$ .

O custo de uma dada rota ($\ R_{i}={\big \{}{v_{0},v_{1},\ ...\ ,v_{m+1}}{\big \}}$), onde $\ v_{i}\in V$ e $\ v_{0}=v_{m+1}=0$  ($\ 0$ denomina o centro de distribuição), é dado por:

$\ C(R_{i})=\sum _{i=0}^{m}c_{i,i+1}+\sum _{i=1}^{m}\delta _{i}$ .

A rota $\ R_{i}$ é 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 $\ D$ :

$\ C(R_{i})\leqslant D$ .

O custo da solução $\ S$ do problema é:

$\ F_{PEV}(S)=\sum _{i=1}^{m}C(R_{i})$ .