Flotta:dimensionamento

Per fare una valutazione economica preliminare di un progetto di rete di PRT e per poter concepire il progetto stesso in modo completo, è necessario dimensionare, oltre alla parte infrastrutturale, il numero dei veicoli che andranno a comporre la flotta. Essa dovrà avere una dimensione tale da garantire il servizio agli utenti che lo richiedono e va dimensionata in funzione della domanda nell’ora di punta.

Una strategia di routing efficiente è fondamentale per ottenere una flotta relativamente contenuta, nell’intento di limitare il costo da sostenere per l’acquisto e la manutenzione dei veicoli. Esiste inoltre un aspetto che esula dalla problematica del routing in senso stretto: ciascun veicolo dispone di una batteria che deve essere ricaricata in un deposito specifico, a meno che la linea non sia diversamente attrezzata.

È dunque necessario dimensionare la flotta tenendo presente che la minimizzazione deve essere applicata non solo al numero di veicoli, ma anche al consumo di energia della batteria.

È di questo che trattano Chebbi & Chaouachi (2014).

Gli autori individuano nella capacità della batteria un vincolo al numero di veicoli da prevedere in un sistema con un predeterminato numero di richieste. Si tratta ancora una volta di un problema di complessità computazionale crescente con la dimensione della rete che può essere risolto con un metodo euristico, ad esempio con i già citati algoritmi genetici.

Chebbi & Chaouachi (2014) schematizzano il sistema con un grafo G=(V,E). Si suppone che nel sistema ci siano n domande. Ciascuna di queste richiede l’invio di un veicolo vuoto dal deposito D alla stazione di partenza per lo spostamento i-esimo che abbia la batteria sufficientemente carica. Da qui il veicolo per soddisfare la domanda deve raggiungere , stazione di arrivo.

Viene poi assunta l’ipotesi che tutti i veicoli abbiano la stessa capacità di batteria B e che questa possa essere caricata in un unico punto D della rete.

Si sottolinea che queste ipotesi sono piuttosto riduttive soprattutto per grandi reti nelle quali possono esserci più punti destinati alla ricarica e in cui i veicoli circolanti potrebbero essere equipaggiati con batterie a diversa capacità. In ogni caso si considerano valide le due ipotesi per semplificare il procedimento.

L’obiettivo ultimo è quindi quello di determinare i percorsi a costo minimo che partendo dal deposito soddisfino la domanda nel più breve tempo possibile e riportino poi i veicoli ancora in D, rispettando il vincolo imposto dalla batteria e in modo che sia minimizzato il totale consumo di energia e il numero di veicoli utilizzati.

La schematizzazione della rete in grafo prevede che l’insieme dei nodi sia dato dall’insieme delle domande e dal deposito (indicato con ):

, con .

L’insieme degli archi E invece è costituito da elementi . Una coppia (i,j) è inserita nell’insieme E se e solo se soddisfa uno tra i seguenti criteri:

 Il momento in cui perviene la richiesta j ( ) è successivo all’istante ottenuto sommando al momento in cui il sistema riceve la richiesta i ( ) al tempo necessario per effettuare lo

86

spostamento -> -> ( > +t( , , ). Il costo di quest’arco è il costo dello

spostamento -> -> .

 il nodo . Si costruisce in questo caso un arco (0,i), dal deposito al nodo i-esimo, il cui costo è quello dello spostamento 0-> -> .

 Il nodo . Si costruisce in questo caso un arco (i,0) il cui costo è quello dello spostamento ->0.

Si noti che applicando i precedenti criteri se esiste l’arco (i,j), allora non esiste (j,i).

Si tratta ora di risolvere un VRP (Vehicle Routing Problem) in cui ogni percorso deve essere compiuto entro un tempo limite dato dallo stato della batteria del veicolo che lo intraprende.

Per farlo gli autori hanno ideato un particolare MOGA (Multi-Objective Genetic Algorithm) che fa uso di operazioni di crossover, mutazione e selezione, e si distingue per come vengono generate le soluzioni nella fase di inizializzazione. Gli autori propongono infatti di utilizzare due distinte operazioni di minimizzazione per ottenere le soluzioni che con i metodi tipici di un algoritmo genetico saranno poi modificate e composte per ottenere la soluzione ottimale.

Si pone innanzitutto , , , .

Con queste ultime due condizioni si impone che per ogni nodo, escluso quello rappresentante il deposito, si abbia un solo arco entrante ed un solo arco uscente.

Si possono ora descrivere le due operazioni di minimizzazione.

La prima minimizza il consumo totale delle batterie dei veicoli presenti in rete:

La seconda minimizza il numero di veicoli utilizzati, minimizzando il numero di archi che collegano il nodo deposito ai nodi di V*:

Le soluzioni così generate non sono fattibili nel sistema che si tenta di realizzare, ma attraverso successive operazioni di tipo genetico si perviene ad un set di soluzioni fattibili e non dominate, tra le quali cioè l’algoritmo non può individuarne una superiore alle altre.

Per questa operazione Chebbi & Chaouachi (2014) propongono di scegliere nel set di non dominate le due soluzioni e che risultano le migliori l’una per consumo energetico, l’altra per numero di veicoli. Ordinando poi le soluzioni rimaste nel set secondo uno dei due criteri, la soluzione dominante è ottenuta confrontando le soluzioni estreme della serie ordinata con e .

87

Chebbi & Chaouachi (2014) testano il MOGA su un sistema di rete con dodici stazioni e ottengono buoni risultati. Osservano anche che la bontà di questo procedimento è incrementata dal fatto che i due obiettivi di minimizzazione non sono in contrasto tra loro: si arriva anzi ad un punto tale per cui il consumo energetico diminuisce di pari passo con il numero di veicoli utilizzati.

Si fa notare infine che la trattazione impone alcune restrizioni poco realistiche: non è posto infatti alcun limite al numero di veicoli che possono stazionare nel deposito. Inoltre, come già evidenziato i veicoli sono considerati tutti tra loro equivalenti. Infine l’applicazione proposta dagli autori non fa uso di precisi dati di domanda, ma genera la domanda stessa in modo casuale, limitando superiormente il numero di richieste. Ciò simula sì quantitativamente il traffico dell’ora di punta, ma non ne rispecchia la distribuzione tra le varie stazioni. Sarebbe allora opportuno, per una miglior rappresentazione del funzionamento del sistema, introdurre ulteriori vincoli nel procedimento.

Il merito dell’algoritmo proposto risiede comunque nella sua semplicità e capacità di generare l’opportuna dimensione della flotta, una soluzione utile per un dimensionamento generale del sistema di PRT.

89