Algoritmi metaeuristici per il problema del VRP

Algoritmi metaeuristici per il problema del vrp - Introduzione
 Introduzione
La distribuzione di merci sul territorio è di vitale importanza per tutte le imprese 
manifatturiere poichè permette l’ingresso fisico dei prodotti sul mercato e il loro acquisto da 
parte dei clienti. Altrettanto vero è che il processo di distribuzione sia estremamente costoso 
poichè condizionato da numerosi fattori. Si capisce dunque che tale aspetto sia di importanza 
critica per l’azienda e che debba essere pianificato e monitorato con attenzione. Obiettivo di 
questo elaborato è quello di presentare i principali modelli matematici che permettono di 
rappresentare la distribuzione di merce all’interno di una realtà aziendale e descrivere alcuni 
algoritmi risolutivi per la minimizzazione dei costi di trasporto. 
Alcuni dei fattori che influenzano tali costi sono [1]:
la geografia del territorio;
•
la tipologia del prodotto trasportato;
•
le economie di scala;
•
la dotazione infrastrutturale;
•
le modalità di trasporto utilizzate per effettuare la spedizione.
•
Nello specifico, dire che il costo di trasporto è condizionato dalla geografia del territorio 
significa che il costo stesso è funzione delle distanze da percorrere e dell’accessibilità alle 
varie zone da collegare. Per quanto riguarda la tipologia del prodotto trasportato, molti 
prodotti richiedono tecniche e modalità di trasporto particolari: si pensi, ad esempio, al 
trasporto di materiali infiammabili che richiede adeguate misure di sicurezza, oppure si 
consideri il trasporto di prodotti alimentari che necessita di rimorchi refrigerati. I costi di 
trasporto dipendono inoltre dalle economie di scala: più grandi sono le quantità da trasportare, 
minore sarà il costo ti trasporto unitario.
L’efficienza e la capacità delle infrastrutture ha un effetto diretto sui costi di trasporto, 
infatti infrastrutture non efficienti implicano più alti costi, determinano ritardi nelle consegne 
condizionando in maniera negativa l’economia dell’azienda. Infine anche la modalità di 
5
Algoritmi metaeuristici per il problema del vrp - Introduzione
trasporto scelta per la realizzazione della spedizione concorre in maniera significativa alla 
determinazione del costo di trasporto in quanto modi di trasporto differenti sono caratterizzati 
da differenti condizioni di funzionamento ed hanno differenti limitazioni di capacità: si 
confrontino, ad esempio, il funzionamento e la capacità del trasporto su gomma e via nave.
Il costo di trasporto rappresenta una fetta molto importante del prezzo finale del 
prodotto trasportato: da un’indagine svolta da TRT nel 2005 è emerso che mediamente il 
trasporto incide sul prezzo finale per il 57% nel caso di granaglie, per il 10.5% nel caso di 
petroli, per il 15.6 % nel caso di acciaio, per il 63% nel caso di minerali ferrosi, per il 4% nel 
caso di automobili e sempre del 4% per il caffè [1].
70
53
35
18
0
GranagliePetroliAcciaioMinerali ferrosiAutomobiliCaffè
Prodotti
Tabella 1: Incidenza costo di trasporto sul prezzo finale. TRT, 2005
Altri esempi di grande incidenza dei costi di trasporto sul prezzo finale sono nel caso di 
libri e giornali: in [2] viene riportato, in merito all’attività editoriale che la distribuzione 
rappresenta attualmente la fase più critica dell’attività e i suoi costi arrivano ad incidere fino 
al 55% del prezzo di copertina. E ancora, riguardo la distribuzione dei giornali nell’arco di 
una notte, si legge che nel mercato dei lettori la fase di distribuzione ha un’importanza 
rilevante e complessivamente presenta dei costi che arrivano al 50% del prezzo di copertina 
analogamente a quanto succede nell’editoria libraria.
6
Costo trasporto tot/prezzo finale*100
Algoritmi metaeuristici per il problema del vrp - Introduzione
Negli ultimi anni un numero sempre crescente di aziende si è posto il problema di 
controllare i costi di trasporto e tentare di ridurli: ciò che ancora non è molto chiaro è quale 
risorsa può essere sfruttata al meglio per effettuare tale riduzione. I clienti con i loro ordini di 
ritiro e consegna della merce, le relative finestre temporali sempre più rigide e vincolanti e le 
limitazioni degli accessi che si hanno di frequente nei centri urbani, a causa dell’elevata 
congestione, rappresentano una leva difficile da manovrare. La soluzione è quindi ottimizzare. 
Ottimizzare i trasporti significa minimizzare la distanza e il tempo totale percorsi da un 
mezzo, minimizzare il numero di mezzi circolanti, massimizzare il riempimento di ogni 
mezzo, bilanciare il carico della flotta. In altre parole occorre ottimizzare una funzione di 
costo.
Nel tempo, il notevole interesse pratico per questi problemi, ha stimolato la nascita di 
studi sempre più approfonditi e dettagliati sull’argomento: in particolare una famosa classe di 
problemi, conosciuta col nome di Vehicle Routing Problem (VRP) è stata introdotta a fine 
anni 50 per tentare di ottimizzare le questioni legate al carico dei veicoli e alla determinazione 
delle rotte più efficienti per il raggiungimento dei clienti. Nella prima sezione di questo 
elaborato si procederà infatti alla presentazione generale del problema del VRP e dei concetti 
principali utilizzati per la sua descrizione. Dopo una discussione iniziale sulle modalità di 
rappresentazione della rete stradale attraverso grafi orientati e non, si procederà alla 
descrizione delle modalità attraverso le quali vengono modellati i clienti e i vincoli da loro 
imposti, come finestre temporali, tempi di carico/scarico, priorità etc. Si terminerà infine il 
primo capitolo con una breve presentazione dei vincoli introdotti in seguito all’utilizzo di 
veicoli per il trasporto delle merci, oltre ad un elenco dei vincoli operativi presenti nei 
principali modelli. 
Nel secondo capitolo si procederà dunque alla presentazione dei principali modelli 
matematici utilizzati per la risoluzione dei più comuni problemi di vehicle routing: oltre al 
tradizionale problema del VRP con vincolo sulla capacità di trasporto dei veicoli (Capacitated 
VRP) verranno riportati modelli che tengono conto della presenza di time windows per il 
carico e lo scarico della merce (VRP con time windows), della possibilità di dividere il carico 
di ogni cliente su più veicoli (VRP con split pickups) ed infine della possibilità di effettuare 
contemporaneamente carichi e scarichi di merce presso il medesimo cliente (VRP con pickup 
7
Algoritmi metaeuristici per il problema del vrp - Introduzione
e delivery). Per ogni modello matematico verrà riportata anche una breve descrizione di ogni 
vincolo utilizzato.
Il grande successo dell’applicazione di tali modelli alla realtà aziendale è dovuto in 
particolar modo allo sviluppo hardware e software nel campo dell’informatica negli ultimi 
anni e alla crescente integrazione dei sistemi informativi in tutti gli ambiti aziendali, in 
particolar modo nel processo produttivo, nell’area commerciale e della pianificazione. Ciò ha 
portato il passaggio dall’utilizzo di team di pianificazione, che necessitavano svariate ore per 
proporre una buona strategia riguardante i carichi dei veicoli e le rotte da seguire, a software 
che richiedono molto meno 
tempo per produrre la 
medesima soluzione. Come 
si vede infatti dalla tabella 
2, un’azienda potrebbe 
aumentare il rendimento 
della propria flotta di circa il 
10% rispetto alla soluzione 
manuale, con un notevole 
Tabella 2: Confronto rendimenti flotta, Logistica Management, 
risparmio in termini di costi 
Giugno-Luglio 2004
distributivi[3].
Nonostante lo sviluppo dell’informatica dal punto di vista dell’hardware e del software, 
problemi complessi come il VRP richiedono tutt’ora troppo tempo per il calcolo della 
soluzione ottima, anche nel caso di computer di nuova generazione. Si veda la tabella 3 a 
pagina seguente tratta da [4] che riporta i tempi di calcolo e il numero di operazioni necessarie 
per risolvere in maniera ottima un classico problema di VRP.
8
Algoritmi metaeuristici per il problema del vrp - Introduzione
N° ClientiTempo di calcoloN° di Operazioni
50Meno di 10 sec.1.000.000.000.000.000
561 ora60.000.000.000.000.000
621 giorno3.600.000.000.000.000.000
701 anno1.281.600.000.000.000.000.000
77100 anni128.160.000.000.000.000.000.000
801000 anni1.281.600.000.000.000.000.000.000
Tabella 3: Tempi di calcolo e numero di operazioni per un classico problema di VRP.
Questa problematica ha portato allo sviluppo di nuovi algoritmi euristici e metaeuristici 
che non assicurano di trovare la miglior soluzione di un problema, ma sono in grado di 
proporre una buona soluzione in tempi di calcolo ragionevoli. Per problemi di grandi 
dimensioni, mediamente i tempi di calcolo di un algoritmo metaeuristico sono dell’ordine dei 
minuti. Si veda sotto l’evoluzione nel tempo degli algoritmi risolutivi per il problema del 
VRP e si noti come in anni recenti gli studiosi stiano tentando di ricavare algoritmi sempre 
più efficienti dal punto di vista computazionale e in grado di ottenere soluzioni sempre più 
vicine a quella ottima [5].
Figura 1: Evoluzione nel tempo degli algoritmi risolutivi per il VRP .
La ricerca scientifica affronta questa problematica ispirandosi al comportamento dei 
sistemi naturali definendo una nuova classe di algoritmi veloci ed efficaci nel calcolo, robusti, 
9