10
1.3 Periodic Vehicle Routing Problem (PVRP)
Il Periodic Vehicle Routing Problem (PVRP) è una generalizzazione del classico
problema di VRP, che estende la costruzione delle rotte da un singolo giorno ad un
orizzonte temporale di piø giorni, durante il quale ciascun cliente deve essere
rifornito esattamente un determinato numero di volte, individuato dalla frequenza di
servizio, con il vincolo però di essere visitati al piø una sola volta per ciascun giorno.
Sono molte le applicazioni reali nelle quali la distribuzione deve essere pianificata su
un determinato periodo di tempo, durante il quale però i nodi non devono essere
serviti ogni giorno ma solo in alcuni. Ad esempio alcuni tipi di distribuzione della
posta, la rimozione della neve per le strade, la raccolta dei rifiuti e il rifornimento di
carburanti.
Queste ed altre applicazioni possono essere descritte utilizzando questo tipo di
modello.
I vincoli operativi ai quali in generale il problema può essere sottoposto sono i
seguenti:
1. in ciascun giorno ogni veicolo parte dal deposito centrale e vi ritorna alla fine
del suo servizio;
2. ogni cliente viene visitato al piø da un solo veicolo ogni giorno e al piø una
sola volta ogni giorno;
3. un veicolo può visitare piø clienti, ma la domanda totale da soddisfare non
può eccedere la sua portata massima;
4. il numero di veicoli utilizzati non può essere superiore al numero di veicoli
disponibili;
5. il tempo di utilizzo giornaliero di ogni veicolo non può eccedere dal limite
fissato;
6. ciascun cliente deve essere visitato esattamente un numero di volte fissato
come sua frequenza di servizio;
7. si tenta di minimizzare il costo totale dei viaggi.
Come vedremo successivamente associamo a ciascun cliente un indice numerico i
che consente di individuare esattamente quel cliente, in questo modo possiamo
indicare gli ulteriori parametri che riguardano il cliente associandogli tale indice.
Nel rispetto di questi vincoli il PVRP pianifica le rotte su un orizzonte temporale di t
giorni, associando a ciascun cliente i una combinazione di visita r scelta in un
11
insieme di combinazioni ammissibili
i
C assegnate allo specifico cliente, tenendo
conto della sua frequenza di servizio
i
f .
L’obiettivo è sempre quello di minimizzare il costo totale delle rotte.
Molte varianti del PVRP sono state descritte in letteratura; si differenziano ad
esempio in base alle diverse funzioni obiettivo che minimizzano la distanza percorsa,
il tempo di viaggio o il costo totale del servizio. Inoltre, parametri come la qualità del
servizio, il carico di lavoro dei veicoli o il numero stesso dei veicoli impiegati,
possono essere inseriti nella funzione obiettivo.
Ulteriori differenze possono riguardare i vincoli operativi a cui devono sottostare le
variabili del modello, come vincoli sul periodo delle visite (frequenza di visita,
restrizioni sui giorni…) , vincoli sul tipo di domanda (costante o variabile…) o sui
veicoli (portata…).
Possiamo avere inoltre modelli nei quali la frequenza di servizio è di tipo
deterministico, pertanto è già un parametro del problema, oppure altri in cui questa
sia variabile e quindi ottenuta come decisione del modello.
Una variante del PVRP in cui la frequenza di servizio è una scelta del modello è
proprio il Periodic Vehicle Routing Problem with Service Choice (PVRP-SC).
Ulteriori modelli presenti in letteratura sono:
- il Periodic Traveling Salesman Problem (PTSP) che estende il TSP, e costruisce
una sola rotta per ciascun giorno poichØ si considera un solo mezzo di trasporto;
- il Periodic Vehicle Routing Problem with Intermediate Facilities (PVRP-IF) nel
quale sono presenti attività intermedie durante le quali, attraverso carico e scarico dei
veicoli, può variare la loro capacità;
- il Periodic Vehicle Routing Problem with Time Windows (PVRPTW) nel quale
sono specificate delle finestre temporali sia di servizio nei vari clienti che di servizio
totale per i veicoli.
12
1.4 Periodicità
La rappresentazione dei vincoli di periodicità è uno dei problemi principali del
modello di PVRP e può essere formulata in diversi modi, che si differenziano per il
numero di combinazioni ammissibili che possono essere generate e dalle modalità
con cui esse si costruiscono.
Analizziamo le rappresentazioni che sono state proposte in letteratura.
Sequenza Predeterminata
In questo tipo di rappresentazione, per ciascun cliente si specificano esattamente tutte
le possibili alternative in cui può essere visitato e dunque si definisce direttamente
l’insieme delle possibili combinazioni
i
C . In questo caso quindi l’insieme delle
combinazioni ammissibili è dato come un parametro e non è necessaria una fase
costruttiva per definire tale insieme.
Sequenza Periodica
In questa formulazione ciascun cliente specifica il numero di visite
i
f di cui
necessita durante l’orizzonte temporale di t giorni, pertanto si considera che ogni
nodo deve essere visitato esattamente ogni
i
f t giorni e tale frazione definisce
esattamente la cardinalità dell’insieme
i
C . Ad esempio se t = 6 e
i
f = 3, il cliente i
dovrà essere visitato ogni
i
f t = 2 giorni. Pertanto le combinazioni ammissibili
possono essere il primo, il terzo e il quinto giorno, oppure il secondo, il quarto e il
sesto.
Sequenza Multistage Network
In questa rappresentazione si considera che ogni cliente deve essere visitato ogni
i
T
giorni e dunque la frequenza di visita è
i i
T t f = . Successivamente si impone che
almeno
i
l giorni e al massimo
i
u giorni devono trascorrere tra due visite successive.
A questo punto per ciascun cliente si costruisce una rete aciclica (Aciclic Multistage
Network) nella quale i nodi della fase k rappresentano i possibili giorni nei quali
effettuare la k-esima visita e ciascun arco collega giorni nei quali è possibile una
visita successiva. La cardinalità dell’insieme
i
C è definita da tutti i possibili percorsi
13
tra i nodi dal primo all’ultimo stadio della rete. Ad esempio la rete ottenuta
considerando t = 9,
i
T = 3,
i
l = 2,
i
u = 4 è rappresentata nella figura 1.1.
Pertanto l’insieme delle possibili combinazioni sarebbe:{(1,4,7), (1,4,8), (1,5,7),
(1,5,8), (1,5,9), (2,4,7), (2,4,8), (2,5,7), (2,5,8), (2,5,9), (2,6,8), (2,6,9), (3,5,7),
(3,5,8), (3,5,9), (3,6,8), (3,6,9)}.
1.5 Formulazione del modello
Per rappresentare il problema generale di PVRP, consideriamo un grafo connesso
non orientato ) , ( A V G = , dove { }
n
v v v V ,..., ,
2 1
= è l’insieme dei vertici (o nodi) che
rappresentano i clienti, mentre l’insieme { } j i n j i j i A „ = = , ,.., 1 , : ) , ( rappresenta gli
archi che congiungono i nodi. Scegliere il grafo connesso significa assumere che
ciascun nodo è collegato con tutti gli altri attraverso un cammino, quindi per ogni
coppia ) , (
j i
v v esiste un percorso che li congiunge.
Inoltre i vertici sono non orientati, cioè percorribili in entrambe le direzioni.
Il vertice
1
v rappresenta il deposito, ed è anche il nodo in cui si trova la flotta
eterogenea di m veicoli a ciascuno dei quali è associata una portata pari a
m v Q
v
,..., 1 con , = e un limite temporale di servizio m v T
v
,..., 1 con , = . Ciascun
vertice dell’insieme V corrisponde a un cliente, al quale è associata una domanda non
negativa n i d
i
,..., 1 con , = , un tempo di servizio n i t
i
,..., 1 con , = e una frequenza di
servizio n i f
i
,..., 1 con , = , che indica esattamente il numero di volte che deve essere
visitato lungo tutto l’orizzonte temporale. A ciascun arco ) , ( j i dell’insieme A, è
Figura 1.2 Multistage Network
14
associato un costo di viaggio definito con
ij
c e un tempo di viaggio
ij
t necessario per
andare dal nodo i al nodo j.
Per ogni nodo i definiamo inoltre un insieme delle combinazioni di servizio
ammissibili C
i
utilizzando una delle modalità analizzate in 1.4.
Definiamo delle costanti binarie a
rl
che indicheranno se un giorno (individuato
dall’indice l ) appartiene o meno ad una certa combinazione di servizio (individuata
dall’indice r ) nel seguente modo:
a
rl
= 1 se il giorno l appartiene alla combinazione r
a
rl
= 0 altrimenti
Le prime variabili di decisione del modello saranno x
ijvl
che costruiscono le rotte
seguite dal veicolo v nel giorno l
nel seguente modo:
x
ijvl
=1 se l’arco i-j fa parte della rotta servita dal veicolo v nel giorno l
x
ijvl
=0 altrimenti
Altre variabili di decisione saranno y
ir
che indicheranno la scelta della combinazione
associata ai diversi nodi nel seguente modo:
y
ir
= 1 se la combinazione di servizio r è assegnata al nodo i
y
ir
= 0 altrimenti.
Il valore delle variabili che otterremo mediante la risoluzione del modello ci
permetterà di individuare due differenti informazioni.
La variabile y
ir
ci consente di individuare a quale combinazione di giorni sarà
assegnato il nodo i, e di conseguenza individuare per ogni giorno qual è l’insieme di
clienti da servire; la variabile x
ijvl
ci consentiranno di individuare i percorsi seguiti dal
veicolo v in ciascun giorno dell’orizzonte temporale, quindi di costruire l’insieme
delle rotte che costituiranno la soluzione ottima e dalle quali si otterrà il valore
minimo delle funzione obiettivo.
Dalla precedente osservazione, si evince quindi che il modello effettua due
operazioni, innanzitutto individua la combinazione migliore da associare al singolo
nodo e, in un secondo passo, costruisce le rotte dei singoli veicoli attraverso i vertici,
per tutti i giorni dell’orizzonte temporale considerato.
Quindi è quello che in letteratura è definito un Problema di Ottimizzazione
Combinatoria Multilivello (Multilevel Combinatorial Optimization Problem).
15
Il modello matematico del PVRP può essere rappresentato come segue:
La funzione obiettivo (1) del modello minimizza la somma dei costi di viaggio per
ciascun veicolo e per tutti i giorni dell’orizzonte temporale.
I vincoli (2) assicurano che solo una combinazione ammissibile è associata a ciascun
nodo (dai quali è escluso il deposito), mentre i vincoli (3) garantiscono che ciascun
cliente è visitato solo nei giorni corrispondenti alla combinazione che gli è stata
assegnata. I vincoli (4) costringono un veicolo che arriva in un vertice ad uscirne
nello stesso giorno, mentre i vincoli (5) specificano che ciascun veicolo lascia al piø
una volta il deposito ogni giorno, cioè effettua al piø un solo viaggio al giorno. I
vincoli (6) e (7) descrivono la limitazione di ciascun veicolo in termini di capacità di
carico e di tempo di servizio complessivo i quali non devono eccedere i valori
stabiliti. I vincoli (8) impediscono la formazione di sottocicli e i vincoli (9) e (10)
impongono che le variabili di decisione siano binarie.
( )
{ }
{ }
{ } (10) , ,..., 2 1 , 0
(9) ,..., 1 ; ,..., 1 ,..., 1 , 1 , 0
(8) 2 ; 1 ; ,..., 1 ; ,..., 1 1
(7) ,..., 1 ; ,..., 1
(6) ,..., 1 ; ,..., 1
(5) ,..., 1 ; ,..., 1 1
(4) ,..., 1 ; ,..., 1 ; ,..., 1 0
(3) ,..., 1 ; ,..., 2 0
(2) ,..., 2 1
i
v
1 i 1
1 1 i
2
1
1 1
1 1
i ir
ijvl
S S v
ijvl
v
n n
j
ijvl i ij
v
n
j
ijvl
n
i
n
j
jvl
n
j
pjvl
n
i
ipvl
n
j C r
ir rl
m
v
ijvl
n
C r
ir
C r n i y
t l m v n j i x
S N S t l m v S x
t l m v T x t t
t l m v Q x d
t l m v x
t l n p m v x x
t l n i y a x
n i y
j
i
i
˛ = ˛ = = = ˛ ‡ - ˝ = = - £ = = £ +
= = £
= = £ = = = = - = = = - = =
∑∑
∑∑
∑ ∑
∑
∑ ∑
∑ ∑ ∑
∑
˛ ˛ = =
= =
=
= =
= ˛ =
˛ (1) Obiettivo) (Funzione MIN
1 1 1
t
1
ijvl
n
i
n
j
m
v l
ij
x c z
∑∑∑∑
= = = =
=
S.V.
16
1.6 Metodi risolutivi
Dopo la costruzione del modello matematico, si possono avere diversi approcci di
risoluzione, per ottenere la soluzione ottima del problema.
Come osservato, il PVRP si articola su due differenti livelli: nel primo livello si
assegna una combinazione di servizio a ciascun cliente, nel secondo livello si risolve
il classico CVRP per ciascun giorno dell’orizzonte temporale scelto, nel terzo livello
attraverso un modello di TSP vengono costruite le singole rotte.
PoichØ è stato dimostrato che il TSP è un problema di tipo NP-hard, anche il PVRP
avrà almeno la stessa difficoltà di risoluzione.
Per questo motivo difficilmente si può pensare di risolvere il problema con dei
Metodi esatti, anche se gli algoritmi sviluppati e le potenze elevate dei calcolatori
consentono di risolvere alcuni problemi nel caso in cui le loro dimensioni siano
sufficientemente contenute.
Si può tentare di effettuare una risoluzione attraverso la Programmazione
matematica, cioè risolvere una formulazione rilassata del problema, non ottenendo
però così un risultato ottimo, ma ottenendo un upper bound o un lower bound (a
seconda del problema) della soluzione ottima.
Gli approcci piø interessanti e attualmente piø studiati sono le Procedure Euristiche,
suddivise in due categorie, in grado di fornire soluzioni di buona qualità in tempi di
calcolo contenuti.
1.6.1 Euristiche Classiche
Sviluppate a partire dagli anni ’60, hanno una struttura generalmente semplice, tempi
di calcolo contenuti, agevole implementazione e adattamento ai diversi vincoli
operativi.
Possono a loro volta essere classificate in tre classi principali.
La prima è quella delle Euristiche Costruttive che definiscono gradualmente una
soluzione ammissibile tenendo in considerazione il costo della soluzione che si sta
costruendo. Appartiene a questa classe la Procedura dei risparmi (di Clarke &
Wright).
La seconda classe è quella delle Euristiche a Due Fasi che sono suddivise a loro
volta in due sottoclassi: gli algoritmi Cluster-first, Route-second e gli algoritmi
Route-first, Cluster-second.
17
Nei primi, i clienti vengono raggruppati in insiemi ammissibili e poi viene
costruito per ogni insieme un percorso, un esempio è l’Algoritmo di Fisher-Jaikumar
(1981); al contrario nel secondo tipo viene prima costruito un ciclo che visita tutti i
clienti ed in base ad esso vengono poi definiti i percorsi che dovranno effettuare i
veicoli , ne è un esempio l’Algoritmo Sweep.
L’ultima classe è quella degli Algoritmi di Ricerca Locale che, partendo da una
soluzione iniziale non ottima o addirittura non ammissibile, cercano di determinare
una soluzione migliore, eseguendo una sequenza di scambi di archi (spigoli) o di
vertici (nodi) all’interno del singolo percorso o tra percorsi diversi (procedure 2-opt).
Molto studiata negli ultimi anni con buoni risultati sono state le procedure di
Variable Neighborhood Search (VNS), con le quali si sono ottenuti notevoli risultati.
Avendo il PVRP la necessità di definire sia l’assegnazione dei clienti alle
combinazioni, sia la costruzione delle rotte, molto interessanti risultano gli algoritmi
del tipo “Raggruppa prima, Instrada dopo” e “Instrada prima, Raggruppa dopo” che
analizziamo.
Algoritmi “Raggruppa prima, Instrada dopo” (Cluster-First , Route-Second)
Questo tipo di algoritmi risolve il PVRP in due fasi distinte: nella prima si assegna ad
ogni vertice una combinazione, scelta tra quelle ammissibili appartenenti all’insieme
C
i
che tengono conto della frequenza di servizio; nella seconda fase invece si risolve
per ciascun giorno il problema di instradamento sul sottografo relativo ai nodi
assegnati in quel giorno, costruendo la rotta ottimale del veicolo. La definizione dei
sottoinsiemi dei nodi può essere effettuata manualmente nel caso di piccole
dimensioni oppure con algoritmi piø complessi che seguono un determinato criterio
(geografico, temporale, ecc.)
Algoritmi “Instrada prima, Raggruppa dopo” (Route First – Cluster Second)
Anche questi algoritmi risolvono il problema in due fasi simmetricamente a quelli
precedenti. Nella prima fase infatti si risolve il problema di VRP relativo a tutti i
nodi costruendo delle rotte che visitino tutti i clienti; nella seconda fase invece si
assegnano i clienti ai giorni tentando il piø possibile di inserire i clienti che
appartengono alla stessa rotta nelle combinazioni che contengono il medesimo
giorno. Successivamente si risolve un VRP per ciascun giorno per ottenere le rotte
ottimali.
18
1.6.2 Metaeuristiche
Sviluppate a partire dagli anni ’90, sono piø complesse, con tempi di elaborazione
maggiori e delicate operazioni di taratura. Infatti tutti questi algoritmi sono
caratterizzati da una serie di parametri che devono essere tarati sperimentalmente in
base allo specifico problema che deve essere risolto.
In letteratura sono descritte diverse procedure Metaeuristiche applicabili ai problemi
di VRPs come: simulated annealing (SA), deterministic annealing (DA), tabu search
(TS), genetic algorithms (GA), ant systems (AS) e neural networks (NN).
In generale le euristiche classiche effettuano una ricerca limitata all’interno dello
spazio delle soluzioni ammissibili e producono soluzioni di buona qualità a fronte di
bassi tempi di calcolo. Le Metaeuristiche invece, accettando soluzioni intermedie
peggiori o addirittura inammissibili, effettuano una ricerca approfondita nello spazio
delle soluzioni e producono così soluzioni di qualità maggiore rispetto a quelle
prodotte dalle euristiche classiche ma richiedono tempi di calcolo molto piø elevati.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
