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^{\prime }=V\mathrm{\setminus }\{v_0\}$ é o conjunto de $n$ cidades.

$A=\{(v_i,v_j)|(v_i,v_j)\in V;i\ne j\}$ é 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=\{(v_i,v_j)|v_i,v_j\in V;i<j\}$ .

A cada vértice $v_i$ em $V^{\prime }$ 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^{\prime }$ seja visitado exactamente uma vez por um veículo.

Para um cálculo mais fácil em computador, pode-se definir $b(V)=\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=\left\{v_0,v_1,...,v_{m+1}\right\}$), 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)⩽D$ .

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

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