L’attività di distribuzione e/o di raccolta di merci dai luoghi (“sorgente”) alle destinazioni che le richiedono è economicamente importante sia a livello aziendale che nazionale.
In generale la funzione costo di distribuzione è una combinazione di diversi elementi; elemento fondamentale della funzione costo è il costo di distribuzione dei prodotti finiti dagli impianti ai depositi e dai depositi ai clienti finali. Nella sua versione base, il Vehicle Routing Problem (VRP) richiede di soddisfare le richieste di un insieme di clienti, utilizzando una flotta di veicoli localizzata in uno o più depositi.
I problemi reali di un VRP possono essere di diversa tipologia e applicati a svariati campi della vita quotidiana:
• Distribuzione a supermercati;
• Distribuzione di snack e bevande a distributori; • Distribuzione di prodotti petroliferi;
• Distribuzione/raccolta posta;
111
• Movimentazione autovetture fra concessionarie e punti di produzione e stoccaggio;
• Distribuzione prodotti finiti e raccolta materie prime;
• Raccolta di rifiuti solidi urbano e smistamenti verso impianti di trattamento e/o smaltimento;
• Routing di “scuola-bus”
• Movimentazione merci all’interno di un magazzino;
• …
Il costo di una soluzione al VRP nei casi reali può risultare una combinazione di: 1. Numero e tipo di ordini non evasi;
2. Costo dei veicoli e degli autisti utilizzati; 3. Distanza percorsa dagli automezzi; 4. Tempo impiegato dagli autisti;
5. Costo secondo tariffe di legge o contratti con ditte di trasporto; 6. …
Altri costi non direttamente quantificabili ma che guidano il processo di risoluzione sono:
1. Qualità del servizio offerto ai clienti; 2. Assegnazione di viaggi ai trasporti privati; 3. …
I problemi reali sono spesso caratterizzati da vincoli e complicazioni di diversa natura, legati alla tipologia di servizio da effettuare, alle modalità di viaggio etc…
Si riportano di seguito, a titolo esemplificativo alcuni dei vincoli che si possono riscontrare durante le attività di trasporto reali:
• giorni ed orari di visita ai clienti (es.: lunedì 8.00-13.00 e 14.00-17.00, martedì 10.00-13.00 e 17.00-18.00);
• raccolta e consegne (lo stesso mezzo che effettua le consegne raccoglie anche i vuoti);
• distribuzione di più prodotti con veicoli scompartati (es.: distribuzione di prodotti petroliferi);
• incompatibilità veicolo-cliente (es.: attrezzature di scarico richieste, strade troppo piccole);
• incompatibilità prodotto-veicolo (es.: interazione con i prodotti);
• layout di carico (es. : combinazione oggetti o pallet che possono essere caricati in un veicolo);
• viaggi che durano più giorni;
• veicoli che effettuano più viaggi al giorno;
• precedenze nelle consegne (es.: al cliente va lasciato il rimorchio che sarà ripreso prima di rientrare al deposito. Trasporto da cliente a cliente); • più depositi interdipendenti (divisone netta dei clienti o integrazione). VRP base: distribuzione da un deposito
Il VRP base è il problema in cui da un deposito (o impianto) centrale una flotta di automezzi deve rifornire un insieme di clienti. L’obiettivo è quello di pianificare un insieme di viaggi per gli automezzi al fine di soddisfare la domanda di distribuzione, minimizzando i costi dei viaggi.
112
Il Capacitated VRP (CVRP) è caratterizzato da automezzi tutti uguali e con capacità massima di trasporto (in peso o in volume).
Figura 23: Schema di VRP
VRP con Time Windows (VRPTW)
Il VRPTW è una generalizzazione del VRP in cui il servizio di consegna e/o raccolta merce deve essere effettuato all’interno di un intervallo di tempo (TW, time window) definita da un tempo di inizio e un tempo di fine durante il quale il cliente deve essere servito (es: dalle 9.00 alle 12.00).
113 VRP con Backhauls (VRPB)
Il VRPB è una generalizzazione del VRP in cui l’insieme dei clienti è partizionato in due sottosistemi: clienti ai quali deve essere consegnata merce (delivery) e clienti dai quali deve essere raccolta merce (puckup). Inoltre in ogni viaggio tutte le delivery devono essere effettuare prima delle collection. (Es: trasporto cibo).
Figura 25: Schema di un VRPB
VRP con consegne e raccolte (VRPDP)
Nel VRP con consegne e raccolte (pickup and delivery) l’insieme dei clienti è partizionato in clienti di consegna e clienti di raccolta. A differenza del VRPB, non vi è alcuna precedenza fra le consegne e le raccolte di viaggio. Nel Last-In-First-Out VRP si possono consegnare le merci raccolte solo in ordine LIFO).
114
Figura 26: Schema di un VRPDP
Capacitated Arc Routing Problem (CARP)
Il CARP è il problema in cui da un deposito (o impianto) centrale una flotta di automezzi deve soddisfare le richieste associate ad un insieme di strade del territorio. L’obiettivo è quello di pianificare un insieme di viaggi per la flotta degli automezzi per soddisfare la domanda associata alle strade, minimizzando i costi di viaggio (esempio tipico: consegna del latte).
115
Periodic Vehicle Routing Problem (PVRP)
Il PVRP consiste nel pianificare, per un determinato periodo di tempo, l'insieme di viaggi che una flotta di veicoli localizzata ad un deposito deve effettuare in modo da soddisfare il livello di servizio di ogni cliente, minimizzando il costo di distribuzione.
Formulazione del VRP
È dato un grafo G = (V, A), dove il vertice O rappresenta il deposito, ed i vertivi V’ = {1,….., n} rappresentano i clienti.
• ad ogni cliente i ϵ V’ è associata una domanda positiva qi. • ad ogni arco (i, j) ϵ A è associato un costo non negativo cij. • M veicoli identici di capacità Q sono localizzati al deposito.
• costo di un viaggio (o route): somma dei costi degli archi che compongono il viaggio.
Caratteristiche del problema:
- ogni veicolo deve effettuare un viaggio (route) partendo con carico minore o al più uguale alla capacità Q;
- ogni viaggio deve iniziare e terminare al deposito;
- ogni cliente deve essere visitato una ed una sola volta da un solo veicolo.
Obiettivo:
Disegnare M route, una per ogni veicolo in modo tale che tutti i clienti siano visitati e la somma dei costi della route sia minima.
116