Vehicle routing problem

Una figura che illustra il problema del percorso del veicolo

Il problema del Vehicle Routing (VRP) è un problema di ottimizzazione combinatoria e programmazione intera che chiede "Qual è l'insieme ottimale di percorsi che una flotta di veicoli deve attraversare per consegnare a un dato insieme di clienti?" Generalizza il problema del commesso viaggiatore (TSP). Apparve per la prima volta in un articolo di George Dantzig e John Ramser nel 1959, in cui fu scritto il primo approccio algoritmico applicato alle consegne di benzina. Spesso il contesto è quello della consegna di merci situate in un deposito centrale a clienti che hanno effettuato ordini per tali merci. L'obiettivo del VRP è ridurre al minimo il costo totale del percorso. Nel 1964 Clarke e Wright migliorarono l'approccio di Dantzig e Ramser utilizzando un efficace algoritmo greedy chiamato algoritmo di risparmio ("avido").

Determinare la soluzione ottimale per VRP è NP-hard, quindi la dimensione dei problemi che possono essere risolti in modo ottimale utilizzando la programmazione matematica o l'ottimizzazione combinatoria può essere limitata. Pertanto, i risolutori commerciali tendono a utilizzare le euristiche a causa delle dimensioni e della frequenza dei VRP del mondo reale che devono risolvere.

Il VRP ha molte applicazioni dirette nell'industria. I fornitori di strumenti di routing VRP spesso affermano di poter offrire risparmi sui costi dal 5% al 30%.

Impostazione del problema

Il VRP riguarda il servizio di una società di consegna. Come le cose vengono consegnate da uno o più depositi che hanno un insieme dato di veicoli e sono gestiti da un insieme di autisti che possono muoversi su una data rete stradale verso un insieme di clienti. Richiede la determinazione di un insieme di percorsi, S, (un percorso per ogni veicolo che deve partire e terminare al proprio deposito) in modo che siano soddisfatte tutte le esigenze dei clienti e i vincoli operativi e il costo globale di trasporto sia minimizzato. Questo costo può essere monetario, di distanza o altro.

La rete stradale può essere descritta utilizzando un grafico in cui gli archi sono strade e i vertici sono incroci tra di loro. Gli archi possono essere orientati o non orientati per la possibile presenza di sensi unici o costi diversi in ogni direzione. Ogni arco ha un costo associato che è generalmente la sua lunghezza o il tempo di percorrenza che può dipendere dal tipo di veicolo.

Per conoscere il costo globale di ogni tratta, è necessario conoscere il costo del viaggio e il tempo di viaggio tra ciascun cliente e il deposito. Per fare questo il nostro grafo di origine viene trasformato in uno in cui i vertici sono i clienti e il deposito, e gli archi sono le strade tra di loro. Il costo su ciascun arco è il costo più basso tra i due punti sulla rete stradale originaria. Questo è facile da fare poiché i problemi di cammino minimo sono relativamente facili da risolvere. Questo trasforma il grafo originale sparso in un grafo completo. Per ogni coppia di vertici i e j, esiste un arco (i,j) del grafo completo il cui costo si scrive come $C_{ij}$ ed è definito come il costo del cammino minimo da i a j. Il tempo di viaggio $t_{ij}$ è la somma dei tempi di percorrenza degli archi sul percorso più breve da i a j sul grafico stradale originale.

A volte è impossibile soddisfare tutte le richieste di un cliente e in tali casi i risolutori possono ridurre le richieste di alcuni clienti o lasciare alcuni clienti non serviti. Per far fronte a queste situazioni può essere introdotta una variabile di priorità per ciascun cliente o associate penali per il servizio parziale o mancato per ciascun cliente dato

La funzione obiettivo di un VRP può essere molto diversa a seconda della particolare applicazione del risultato, ma alcuni degli obiettivi più comuni sono:

• Ridurre al minimo il costo di trasporto globale in base alla distanza globale percorsa, nonché i costi fissi associati ai veicoli e ai conducenti usati
• Ridurre al minimo il numero di veicoli necessari per servire tutti i clienti
• Minima variazione nel tempo di viaggio e nel carico del veicolo
• Ridurre al minimo le sanzioni per un servizio di bassa qualità
• Massimizza un profitto/punteggio raccolto.

Varianti VRP

Una mappa che mostra la relazione tra sottoproblemi VRP comuni.

Esistono diverse varianti e specializzazioni del problema del Vehicle Routing:

• Vehicle Routing Problem with Profits (VRPP): un problema di massimizzazione in cui non è obbligatorio visitare tutti i clienti. L'obiettivo è visitare una volta i clienti massimizzando la somma dei profitti raccolti rispettando un limite di tempo del veicolo. I veicoli devono iniziare e finire al deposito. Tra i VRPP più conosciuti e studiati, citiamo:
  • Il Team Orienteering Problem (TOP) che è la variante più studiata del VRPP,
  • Il Problema di Team Orienteering Capacitato (CTOP),
  • Il TOP con finestre temporali (TOPTW).
• Problema di Vehicle Routing con ritiro e consegna (VRPPD): un certo numero di merci deve essere spostato da determinate località di ritiro ad altre località di consegna. L'obiettivo è trovare percorsi ottimali per una flotta di veicoli per visitare i luoghi di ritiro e riconsegna.
• Problema di Vehicle Routing con LIFO: simile al VRPPD, tranne per il fatto che viene posta un'ulteriore restrizione sul carico dei veicoli: in qualsiasi luogo di consegna, l'articolo consegnato deve essere l'articolo ritirato più di recente. Questo schema riduce i tempi di carico e scarico nei luoghi di consegna perché non è necessario scaricare temporaneamente articoli diversi da quelli che dovrebbero essere lasciati.
• Vehicle Routing Problem con Time Windows (VRPTW): i luoghi di consegna hanno finestre temporali entro le quali devono essere effettuate le consegne (o le visite).
• Problema di instradamento del veicolo capacitato: CVRP o CVRPTW. I veicoli hanno una capacità di carico limitata della merce che deve essere consegnata.
• Problema di Vehicle Routing con viaggi multipli (VRPMT): i veicoli possono fare più di un percorso.
• Open Vehicle Routing Problem (OVRP): i veicoli non sono tenuti a tornare al deposito.
• Inventory Routing Problem (IRP): i veicoli sono responsabili di soddisfare le richieste in ogni punto di consegna
• Problema di instradamento dei veicoli multi-deposito (MDVRP): esistono più depositi da cui i veicoli possono iniziare e terminare.

Diversi fornitori di software hanno creato prodotti software per risolvere vari problemi VRP. Numerosi articoli sono disponibili per maggiori dettagli sulla loro ricerca e sui risultati.

Sebbene la VRP sia correlata al problema di programmazione dell'officina, i due problemi vengono in genere risolti utilizzando tecniche diverse.

Metodi risolutivi esatti

Esistono tre principali approcci diversi alla modellazione del VRP

1. Formulazioni del flusso del veicolo: 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 i VRP di base. Ciò è utile nei casi in cui il costo della soluzione può essere espresso come somma di tutti i costi associati agli archi. Tuttavia non può essere utilizzato per gestire molte applicazioni pratiche.
2. Formulazioni del flusso di merci: ulteriori variabili intere sono associate agli archi o ai bordi che rappresentano il flusso di merci lungo i percorsi seguiti dai veicoli. Questo è stato utilizzato solo di recente per trovare una soluzione esatta.
3. Problema di partizionamento degli insiemi: questi hanno un numero esponenziale di variabili binarie, ciascuna associata a un diverso circuito ammissibile. Il VRP è quindi invece formulato come un problema di partizionamento di insiemi che chiede quale sia l'insieme di circuiti a costo minimo che soddisfano i vincoli di VRP. Ciò consente costi di percorso molto generali.

Formulazioni di flusso del veicolo

La formulazione del TSP di Dantzig, Fulkerson e Johnson è stata estesa per creare le due formulazioni di flusso del veicolo indice per il VRP

${\text{min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}$

soggetto a

$\sum _{i\in V}x_{ij}=1\quad \forall j\in V\backslash \left\{0\right\}$

(1)

$\sum _{j\in V}x_{ij}=1\quad \forall i\in V\backslash \left\{0\right\}$

(2)

$\sum _{i\in V\setminus \{0\}}x_{i0}=K$

(3)

$\sum _{j\in V\setminus \{0\}}x_{0j}=K$

(4)

$\sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S),~~\forall S\subseteq V\setminus \{0\},S\neq \emptyset$

(5)

$x_{ij}\in \{0,1\}\quad \forall i,j\in V$

(6)

In questa formulazione $c_{ij}$ rappresenta il costo per passare dal nodo $i$ al nodo $j$, $x_{ij}$ è una variabile binaria che ha valore $1$ se l'arco va da $i$ a $j$ è considerato come parte della soluzione e $0$ altrimenti, $K$ è il numero di veicoli disponibili e $r(S)$ corrisponde al numero minimo di veicoli necessari per servire il set $S$. Supponiamo inoltre che $0$ è il nodo del deposito.

I vincoli 1 e 2 stabiliscono che esattamente un arco entra ed esattamente uno esce da ciascun vertice associato a un cliente, rispettivamente. I vincoli 3 e 4 dicono che il numero di veicoli in uscita dal deposito è uguale al numero in entrata. Il vincolo 5 è il vincolo di riduzione della capacità, che impone che le rotte siano collegate e che la domanda su ciascuna rotta non superi la capacità del veicolo. Infine, il vincolo 6 è il vincolo di integralità.

Un vincolo arbitrario tra i $2|V|$ vincoli è in realtà implicito nel rimanente $2|V|-1$ quelli in modo che possa essere rimosso. Ogni taglio definito da un set di clienti $S$ è attraversato da un numero di archi non inferiore a $r(S)$ (numero minimo di veicoli necessari per servire il set $S$).

Una formulazione alternativa può essere ottenuta trasformando i vincoli di riduzione della capacità in vincoli di eliminazione del sottogiro generalizzati (GSEC).

$\sum _{i\in S}\sum _{j\in S}x_{ij}\leq |S|-r(S)$

che impongono che almeno $r(S)$ archi lascino ogni insieme di clienti $S$.

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

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

$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\leq u_{i}\leq C-d_{i}~~~~~~\forall i\in V\backslash \{0\}$

Dove $u_{i},~i\in V\backslash \{0\}$ è una variabile continua aggiuntiva che rappresenta il carico lasciato nel veicolo dopo aver visitato il cliente $i$ e $d_{i}$ è la domanda del cliente $i$. Questi impongono sia i requisiti di connettività che i requisiti di capacità. Quando vincoliamo $x_{ij}=0$ allora $i$ non è vincolante poiché $u_{i}\leq C$ e $u_{j}\geq d_{j}$ mentre $x_{ij}=1$ lo impongono $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 somma dei costi dell'arco. Non possiamo nemmeno sapere quale veicolo attraversa ciascun arco. Quindi non possiamo usarlo per modelli più complessi in cui il costo e/o la fattibilità dipendono dall'ordine dei clienti o dai veicoli utilizzati.

Instradamento ottimale manuale e automatico

Esistono molti metodi per risolvere manualmente i problemi di vehicle routing. 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: Largest gap, S-shape, Aisle-by-aisle, Combined and Combined +. Sebbene il metodo Combined + sia il più complesso, quindi il più difficile da utilizzare per gli operatori di carrelli elevatori, è il metodo di routing più efficiente. Tuttavia, la differenza percentuale tra il metodo di routing ottimale manuale e il reale percorso ottimale era in media del 13%.

Metaeuristica

A causa della difficoltà di risolvere in modo ottimale istanze su larga scala di problemi di vehicle routing, uno sforzo di ricerca significativo è stato dedicato a metaeuristica come algoritmi genetici, Tabu search, Simulated annealing e Adaptive Large Neighbourhood Search (ALNS). Alcune delle metaeuristiche più recenti ed efficienti per i problemi di instradamento dei veicoli raggiungono soluzioni entro lo 0,5% o l'1% dell'ottimale per istanze di problemi che contano centinaia o migliaia di punti di consegna. Questi metodi sono anche più robusti, nel senso che possono essere adattati più facilmente per far fronte a una varietà di vincoli secondari. Pertanto, l'applicazione di tecniche metaeuristiche è spesso preferita per applicazioni su larga scala con vincoli e insiemi decisionali complicati.

Bibliografia

• Oliveira, H.C.B.de e Vasconcelos, G.C., A hybrid search method for the vehicle routing problem with time windows, in Annals of Operations Research, vol. 180, 2008, pp. 125–144, DOI:10.1007/s10479-008-0487-y.
• Frazzoli, E. e Bullo, F., Decentralized algorithms for vehicle routing in a stochastic time-varying environment, in 43rd IEEE Conference on Decision and Control, 14-17 Dec. 2004, Nassau, Bahamas, Proceedings of the ... IEEE Conference on Decision & Control, vol. 4, IEEE, 2004, DOI:10.1109/CDC.2004.1429220, ISBN 0-7803-8682-5, ISSN 0191-2216.
• Psaraftis, H.N., Dynamic vehicle routing problems (PDF), in Vehicle Routing: Methods and Studies, vol. 16, 1988, pp. 223–248.
• Bertsimas, D.J. e Van Ryzin, G., A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane, in Operations Research, vol. 39, n. 4, 1991, pp. 601–615, DOI:10.1287/opre.39.4.601, JSTOR 171167.
• Vidal T, Crainic TG, Gendreau M, Prins C, Heuristics for multi-attribute vehicle routing problems: A survey and synthesis, in European Journal of Operational Research, vol. 231, n. 1, 2013, pp. 1–21, DOI:10.1016/j.ejor.2013.02.053.

Voci correlate

• Problema del postino cinese
• Problema di riprogrammazione del veicolo
• Instradamento dell'arco
• Elenco degli argomenti di teoria dei grafi