L’idea dell’utilizzo di un sottografo delle torrette `e quella di poter entrare in un grafo di percorsi ottimi nel momento in cui vi sia la necessit`a di ricaricare il veicolo. Questa possibilit`a riduce sensibilmente il costo computazionale in quanto i percorsi minimi tra torrette sono sempre gli stessi e in questo modo vengono calcolati una volta sola. Il metodo di utilizzo del sottografo varia a seconda dell’approccio che si sceglie di usare; nel nostro caso, il primo consisteva nel collegare il nodo di partenza ad ogni nodo torretta presente nel sottografo delle torrette e, suc- cessivamente, nel collegare ogni nodo torretta presente nel sottografo al nodo di destinazione del nostro tragitto. Questo approccio permette di ottenere il percorso migliore con ricarica, se esistente. Con questo approccio il tempo computazionale per collegare ogni nodo torretta alla destinazione `e molto simile a quello necessario alla creazione del sottografo delle torrette, quindi, in questo caso il vantaggio maggiore `e ottenuto se il veicolo necessita di due o pi`u ri- cariche durante il tragitto in quanto sfrutteremmo il vantaggio di aver gi`a calcolato i percorsi ottimi tra i nodi torretta. Sono state sviluppate due funzioni ausiliarie per aggiungere il nodo di partenza e il nodo di arrivo al sottografo.
DIST, BATT, PATH = DIJKSTRA-EV (Graph, partenza, battery , weight, consumo); Graph.add node(partenza);
for torre in SubGraph.nodes() do if torre in DIST then
Graph.add edge(partenza, torre, traveltime = DIST[torre], batteria = BATT[torre], percorso = PATH[torre]);
end end
Algorithm 6:AGGIUNGI-SOURCE(SubGraph, Graph, partenza, battery)
Come possiamo notare nell’algoritmo 8 nella pagina successiva viene creata una copia tem- poranea del sottografo. Ad ogni nodo del sottografo copiato vengono collegati il punto di par- tenza e il punto di arrivo del veicolo, in questo modo una volta che il veicolo entra nel sottografo delle torrette, ha gi`a precalcolati i percorsi pi`u veloci passanti per le torrette di ricarica; i per-
CAPITOLO 5. SOTTOGRAFO DELLE TORRETTE
Graph.add node(nodo);
for torre in SubGraph.nodes() do
if torre != arrivo and torre != partenza then
DIST, BATT, PATH = DIJKSTRA-EV (Graph, torre, battery , weight, consumo); end
if DIST is not None then
Graph.add edge(torre, arrivo, traveltime=dist[arrivo],batteria = batt[arrivo], percorso = path[arrivo]);
end end
Algorithm 7:AGGIUNGI-TARGET(SubGraph, Graph, partenza, arrivo, battery)
if partenza != arrivo then tempGsub D = subG.copy();
dist,batt,path = DIJKSTRA-EV (Graph, nodo, battery , weight, consumo); end
if dist is None then
AGGIUNGI-SOURCE (tempGsub D, G, partenza, battery); AGGIUNGI-TARGET (tempGsub D, G, partenza, battery);
return DIJKSTRA-EV-NO-VINCOLI(tempGsub D, partenza, arrivo, battery, weight, consumo)
else
return DIJKSTRA-EV (G, partenza, arrivo, battery, weight, consumo) end
caso in cui dovesse necessitare di pi`u di una sosta, la costruzione del sottografo non permette- rebbe all’algoritmo di uscirne passando da una singola torretta di ricarica ma sarebbe costretto a visitare il numero di torrette di ricarica equivalenti al numero di soste necessarie.
Il sottografo `e stato inoltre utilizzato per testare l’algoritmo di Dijkstra per veicoli elettrici, nella fattispecie, oltre al sottografo costruito con l’algoritmo di Dijkstra per veicoli elettrici, si `e costruito anche un sottografo delle torrette utilizzando l’originale algoritmo di Dijkstra, in questo modo si `e potuto fare un confronto tra i tempi impiegati da un veicolo elettrico che non necessita di effettuare la ricarica e i tempi impiegati da un veicolo a combustione. Si `e notato che su un totale di . percorsi, ovvero tutti i percorsi ottimi tra tutte le torrette ottenuti con algoritmo di Dijkstra, l’algoritmo di Dijkstra per veicoli elettrici, partendo con batteria piena riesce a percorrerne . senza necessit`a di ricaricare, con una perdita dell’.%, mentre l’algoritmo di Bellman-Ford per veicoli elettricitalvolta esplorando pi`u strade riesce a percor- rerne ., con una perdita dell’.%. Inoltre si sono andate ad analizzare le differenze tra i tempi dei percorsi ottimi utilizzando l’algoritmo di Dijkstra e i due algoritmi per veicoli elettrici.
In figura 5.3 a pagina 45 possiamo apprezzare la distribuzione delle differenze tra i tempi di percorrenza utilizzando l’algoritmo di Dijkstra e l’algoritmo di Dijkstra per veicoli elettrici men- tre nella figura 5.2 nella pagina successiva, possiamo osservare la distribuzione delle differenze tra i tempi di percorrenza utilizzando l’algoritmo di Dijkstra e l’algoritmo di Bellman-Ford per veicoli elettrici. In entrambi i casi si pu`o notare che per la quasi totalit`a dei percorsi le differenze sono minime. In questo studio si `e considerata la ricarica come ricarica completa ma ci`o non toglie che costruendo il sottografo delle torrette come un multigrafo con pi`u archi parallelli contenenti i percorsi pi`u veloci effettuabili con diversi livelli di batteria si pu`o simulare una ricarica parziale del veicolo.
CAPITOLO 5. SOTTOGRAFO DELLE TORRETTE
Capitolo 6
APPROCCI EURISTICI
L’algoritmo 8 a pagina 42 cos`ı definito, una volta implementato e testato su 100 percorsi, co- me ci si attendeva, si `e rivelato troppo lento nel calcolo del percorso, con almeno una ricarica, quando necessaria. Essendo quella di creare un trip-planner per veicoli elettrici una delle pos- sibili applicazioni dell’algoritmo, si `e reso necessario il miglioramento dei tempi di calcolo dei percorsi in presenza di ricarica. Si sono quindi tentati tre approcci euristici al problema. Da una analisi della complessit`a dell’algoritmo ci si `e resi conto che la porzione che impiegava il maggior tempo ad essere eseguita era quella descritta dalle due funzioni ausiliarie 6 a pagina 41 e 7 a pagina 42. Si `e quindi andati a cercare un approccio diverso al problema che si discostasse dalla ricerca del percorso in assoluto pi`u veloce e che modificasse in qualche modo il processo di aggiunta del nodo di partenza e del nodo di destinazione. Si sono quindi sviluppate due nuove funzioni per l’aggiunta dei nodi di partenza e di arrivo al sottografo.
6.1
Euristica 1
Il primo approccio euristico [algoritmo 11 a pagina 49] che `e stato valutato, trova il percorso pi`u veloce con ricarica controllando le torrette entro un certo range dai nodi del percorso. Si `e pensato di alleggerire la fase di aggiunta dei nodi di partenza e di arrivo limitando la scelta ai soli nodi torretta che si trovavano in un determinato range dai nodi del percorso calcolato senza il vincolo della batteria. Si `e quindi innanzitutto calcolato il percorso migliore come se il veicolo avesse autonomia illimitata, si `e definito un range entro il quale sarebbe dovuta ricadere
DIST, BATT, PATH = DIJKSTRA-EV (Graph, partenza, battery , weight, consumo); Graph.add node(partenza);
for torre in TorretteCandidate do if torre in DIST then
Graph.add edge(partenza, torre, traveltime = DIST[torre], batteria = BATT[torre], percorso = PATH[torre]);
end end
Algorithm 9: AGGIUNGI-SOURCE-EURISTICA(SubGraph, Graph, partenza, battery, TorretteCandidate)
Graph.add node(nodo);
for torre in TorretteCandidate do
if torre != arrivo and torre != partenza then
DIST, BATT, PATH = DIJKSTRA-EV (Graph, torre, battery , weight, consumo); end
if DIST is not None then
Graph.add edge(torre, arrivo, traveltime=dist[arrivo],batteria = batt[arrivo], percorso = path[arrivo]);
end end
Algorithm 10: AGGIUNGI-TARGET-EURISTICA (SubGraph, Graph, partenza, arrivo, battery, TorretteCandidate)
CAPITOLO 6. APPROCCI EURISTICI
la torretta e si sono quindi, per ogni nodo del percorso, andate a cercare le torrette a distanza minore del range definito, da ogni nodo. Si `e quindi creata una lista di nodi torretta candidati ad essere la torretta di ricarica del percorso. Una volta ottenuta la lista dei nodi candidati si sono utilizzati come punti di accesso al sottografo delle torrette e sono stati quindi collegati al nodo di partenza e al nodo di arrivo.