Esistono tre approcci principali per modellare le formulazioni VRP

1. Vehicle flow—questo utilizza variabili intere associate a ciascun arco che contano il numero di volte in cui il bordo viene attraversato da un veicolo. Viene generalmente utilizzato per VRP di base. Questo è buono per i casi in cui il costo della soluzione può essere espresso come la somma di tutti i costi associati agli archi. Tuttavia non può essere utilizzato per gestire molte applicazioni pratiche.
2. Formulazioni del flusso di merci-variabili intere aggiuntive sono associate agli archi o ai bordi che rappresentano il flusso di merci lungo i percorsi percorsi dai veicoli. Questo è stato utilizzato solo di recente per trovare una soluzione esatta.
3. Set partitioning problem-Questi hanno un numero esponenziale di variabili binarie che sono ciascuna associata a un diverso circuito fattibile. Il VRP viene quindi formulato come un problema di partizionamento impostato che chiede quale sia la raccolta di circuiti con un costo minimo che soddisfi i vincoli VRP. Ciò consente costi di percorso molto generali.

il flusso dei Veicoli in formulationsEdit

La formulazione del CUCCHIAINO da Dantzig, Fulkerson e Johnson è stato esteso a creare due indici il flusso dei veicoli in formulazioni per il VRP

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

soggetto

∑ i ∈ V x i j = 1 ∀ j ∈ V ∖ { 0 } {\displaystyle \sum _{i\in 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}

è considerato come parte della soluzione e 0 {\displaystyle 0}

altrimenti, K {\displaystyle K}

è il numero di veicoli disponibili e r ( S ) {\displaystyle r(S)}

corrisponde al numero minimo di veicoli necessari per servire insieme S {\displaystyle S}

. Stiamo anche supponendo che 0 {\displaystyle 0}

sia il nodo depot.

I vincoli 1 e 2 affermano che esattamente un arco entra e esattamente uno lascia ogni vertice associato a un cliente, rispettivamente. I vincoli 3 e 4 dicono che il numero di veicoli che lasciano il deposito è lo stesso del numero che entra. Vincoli 5 sono i vincoli di riduzione della capacità, che impongono che le rotte devono essere collegate e che la domanda su ciascuna rotta non deve superare la capacità del veicolo. Infine, i vincoli 6 sono i vincoli di integralità.

Una arbitraria limitazione fra il 2 | V | {\displaystyle 2|V|}

vincoli è in realtà implicita per i restanti 2 | V | − 1 {\displaystyle 2|V|-1}

quelli così può essere rimosso. Ogni taglio definito da un gruppo di clienti S {\displaystyle S}

è attraversata da una serie di archi non inferiore a r ( s ) {\displaystyle r(s)}

(numero minimo di veicoli necessari per servire insieme S {\displaystyle S}

).

Una formulazione alternativa può essere ottenuta trasformando i vincoli di taglio della capacità in vincoli di eliminazione del sottotour generalizzato (GSEC).

∑ i ∈ S ∑ j ∈ S x i j ≤ | S | − r ( s ) {\displaystyle \sum _{i\in S}\sum _{j\in S}x_{ij}\leq |S|-r(s)}

che impone che almeno r ( s ) {\displaystyle r(s)}

archi lasciare ogni cliente insieme S {\displaystyle S}

.

GCECs e CCCS hanno un numero esponenziale di vincoli quindi è praticamente impossibile risolvere il rilassamento lineare. Un modo possibile per risolvere questo problema è considerare un sottoinsieme limitato di questi vincoli e aggiungere il resto se necessario.

Ancora una volta un metodo diverso è quello di utilizzare una famiglia di vincoli che hanno una cardinalità polinomiale che sono noti come i vincoli MTZ, sono stati prima proposti per il TSP e successivamente estesi da Christofides, Mingozzi e Toth.

u j u i ≥ d j − C ( 1 − x 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\in V\backslash \{0\},i\neq j~~~~{\text{s.t. }}d_{i}+d_{j}\leq C}

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

dove u i , i ∈ V ∖ { 0 } {\displaystyle u_{i},~i\in V\backslash \{0\}}

è un’ulteriore variabile continua che rappresenta il carico lasciati nel veicolo dopo la visita del cliente i {\displaystyle i}

e d i {\displaystyle d_{i}}

è la richiesta del cliente i {\displaystyle i}

. Questi impongono sia la connettività che i requisiti di capacità. Quando x i j = 0 {\displaystyle x_{ij}=0}

vincolo quindi i {\displaystyle i}

non è vincolante”, in quanto u i ≤ C {\displaystyle u_{i}\leq C}

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

mentre x i j = 1 {\displaystyle x_{ij}=1}

impongono che u j ≥ u i + d j {\displaystyle u_{j}\geq u_{i}+d_{j}}

.

Questi sono stati ampiamente utilizzati per modellare il VRP di base (CVRP) e il VRPB. Tuttavia, il loro potere è limitato a questi semplici problemi. Possono essere utilizzati solo quando il costo della soluzione può essere espresso come la somma dei costi dei costi arc. Non possiamo nemmeno sapere quale veicolo attraversa ogni arco. Quindi non possiamo utilizzare questo per modelli più complessi in cui il costo e o la fattibilità dipendono dall’ordine dei clienti o dai veicoli utilizzati.

Percorso ottimale manuale contro automaticomodifica

Esistono molti metodi per risolvere manualmente i problemi di instradamento dei veicoli. Ad esempio, il routing ottimale è un grosso problema di efficienza per i carrelli elevatori nei grandi magazzini. Alcuni dei metodi manuali per decidere il percorso più efficiente sono: Più grande gap, S-shape, Corridoio per corridoio, combinato e combinato +. Mentre il metodo combinato + è il più complesso, quindi il più difficile da utilizzare dagli operatori di carrelli elevatori, è il metodo di instradamento più efficiente. Tuttavia, la differenza percentuale tra il metodo di instradamento ottimale manuale e il percorso ottimale reale era in media del 13%.