Existem três abordagens principais diferentes para modelar as formulações de fluxo do veículo VRP

1. —isto usa variáveis inteiras associadas a cada arco que contam o número de vezes que a aresta é atravessada por um veículo. É geralmente usado para VRPs básicos. Isto é bom para os casos em que o custo da solução pode ser expresso como a soma de quaisquer custos associados com os arcos. No entanto, não pode ser usado para lidar com muitas aplicações práticas. formulações de fluxo de mercadorias-variáveis inteiras adicionais estão associadas aos arcos ou arestas que representam o fluxo de mercadorias ao longo dos caminhos percorridos pelos veículos. Isto só recentemente foi usado para encontrar uma solução exata.
2. problema de particionamento de Conjuntos-estes têm um número exponencial de variáveis binárias que são cada um associado com um circuito viável diferente. The VRP is then instead formulated as a set partitioning problem which asks what is the collection of circuits with minimum cost that satisfy the VRP constraints. Isto permite custos de rota muito gerais.

Veículo do fluxo de formulationsEdit

A formulação de uma colher de chá por Dantzig, Fulkerson e Johnson foi estendido para criar dois índices de veículo fluxo de formulações para o VRP

min ∑ i ∈ V ∑ j ∈ V c i, j x i j {\displaystyle {\text{min}}\sum _{i\V}\sum _{j\V}c_{ij}x_{ij}}

assunto para

∑ i ∈ V x i j = 1 ∀ j ∈ V ∖ { 0 } {\displaystyle \sum _{i\no V}x_{ij}=1\quad \forall j\in V\backslash \left\{0\right\}}

(1)

∑ j ∈ V x i j = 1 ∀ i ∈ V ∖ { 0 } {\displaystyle \sum _{j\in V}x_{ij}=1\quad \forall i\in V\backslash \left\{0\right\}}

(2)

∑ i ∈ V x i 0 = K {\displaystyle \sum _{i\in V}x_{i0}=K}

(3)

∑ j ∈ V x 0 j = K {\displaystyle \sum _{j\in V}x_{0j}=K}

(4)

∑ i ∉ S ∑ j ∈ S x i j ≥ r ( S ) , ∀ S ⊆ V ∖ { 0 } , S ≠ ∅ {\displaystyle \sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S),~~\forall S\subseteq V\setminus \{0\},S\neq \emptyset }

(5)

x i j ∈ { 0 , 1 } ∀ i , j ∈ V {\displaystyle x_{ij}\in \{0,1\}\quad \forall i,j\in V}

(6)

In this formulation c i j {\displaystyle c_{ij}}

represents the cost of going from node i {\displaystyle i}

to node j {\displaystyle j}

, x i j {\displaystyle x_{ij}}

is a binary variable that has value 1 {\displaystyle 1}

if the arc going from i {\displaystyle i}

j {\displaystyle j}

é considerada como parte da solução e 0 {\displaystyle 0}

caso contrário, K {\displaystyle K}

é o número de veículos disponíveis e r ( S ) {\displaystyle r(S)}

corresponde ao número mínimo de veículos necessários para servir o conjunto S {\displaystyle S}

. Nós também estamos assumindo que 0 {\displaystyle 0}

é o nó de depósito.

Constraints 1 and 2 state that exactly one arc enters and exactly one leaves each vertex associated with a customer, respectively. Restrições 3 e 4 dizem que o número de veículos que saem do depósito é o mesmo que o número que entra. Os condicionalismos 5 são os condicionalismos de redução da capacidade, que impõem que as rotas devem ser ligadas e que a procura em cada rota não deve exceder a capacidade do veículo. Por último, as restrições 6 são as restrições de integralidade.

Um arbitrária restrição entre os 2 | V | {\displaystyle 2|V|}

restrições, na verdade, é expressa pelos restantes 2 | V | − 1 {\displaystyle 2|V|-1}

assim ele pode ser removido. Cada corte definido por um cliente do conjunto S {\displaystyle S}

é atravessado por uma série de arcos que não seja menor que r ( s ) {\displaystyle r(s)}

(número mínimo de veículos necessários para servir o conjunto S {\displaystyle S}

). pode obter-se uma formulação alternativa, transformando as restrições de redução da capacidade em restrições generalizadas de eliminação de subtour (GSECs). ∑ i ∈ S ∑ j ∈ S x i j ≤ | S | − r ( s ) {\displaystyle \sum _{i\S}\sum _{j\S}x_{ij}\leq |S|-r(s)}

o que impõe que, no mínimo, r ( s ) {\displaystyle r(s)}

arcos deixar de cada cliente conjunto S {\displaystyle S}

.

GCECs e CCCs têm um número exponencial de restrições por isso é praticamente impossível resolver o relaxamento linear. Uma maneira possível de resolver isso é considerar um subconjunto limitado dessas restrições e adicionar o resto, se necessário.

um método diferente novamente é usar uma família de restrições que têm uma cardinalidade polinomial que são conhecidas como as restrições MTZ, elas foram propostas pela primeira vez para o TSP e posteriormente estendidas por Christofides, Mingozzi e Toth.

u j − u i ≥ d j − C ( 1 − x i j), ∀ i , j ∈ V ∖ { 0 } , i ≠ j s.t. d i + d j ≤ C {\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})~~~~~~\forall i,j\V\barra invertida \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

0 ≤ u i ≤ C − d i ∀ i ∈ V ∖ { 0 } {\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~~\forall i\V\barra invertida \{0\}}

, onde u i , i ∈ V ∖ { 0 } {\displaystyle u_{i},~i\V\barra invertida \{0\}}

é uma variável contínua que representa a carga deixados no veículo, depois de visitar o cliente i {\displaystyle i}

e d i {\displaystyle d_{i}}

é a demanda do cliente i {\displaystyle i}

. Estes impõem tanto a conectividade como os requisitos de capacidade. Quando x i j = 0 {\displaystyle x_{ij}=0}

restrição, em seguida, eu {\displaystyle i}

não é vinculativo ” since u i ≤ C {\displaystyle u_{i}\leq C}

e u j ≥ d j {\displaystyle u_{j}\geq d_{j}}

considerando que x i j = 1 {\displaystyle x_{ij}=1}

impõem que u j ≥ u i + d j {\displaystyle u_{j}\geq u_{i}+d_{j}}

.

estes têm sido usados extensivamente para modelar o VRP básico (CVRP) e o VRPB. No entanto, o seu poder está limitado a estes problemas simples. Só podem ser utilizadas quando o custo da solução puder ser expresso como a soma dos custos do arc. Não podemos também saber que Veículo atravessa cada arco. Por conseguinte, não podemos utilizá-lo para modelos mais complexos, em que o custo e a viabilidade dependem da ordem dos clientes ou dos veículos utilizados.

Manual versus automatic optimum routingEdit

Existem muitos métodos como resolver os problemas de roteamento do veículo manualmente. Por exemplo, roteamento ideal é uma grande questão de eficiência para empilhadeiras em grandes armazéns. Alguns dos métodos manuais para decidir sobre a rota mais eficiente São: maior espaço, Forma S, corredor por corredor, combinado e combinado +. Enquanto o método combinado + é o mais complexo, portanto o mais difícil de ser usado pelos operadores de empilhadores, é o método de roteamento mais eficiente. Ainda assim, a diferença percentual entre o método manual de roteamento ideal e a Rota Real ideal era, em média, de 13%.