Ai fini della scelta di utilizzare l’algoritmo di Dijkstra come algoritmo base per la creazione del nostro algoritmo per veicoli elettrici `e stato di fondamentale importanza il confronto con l’algoritmo di Bellman-Ford.
Imponendo il vicolo di batteria si altera il normale funzionamento dell’algoritmo di Dijk- strache, in quanto algoritmo greedy, come gi`a spiegato nel capitolo su Djkstra, fonda il suo funzionamento sul principio per cui ogni volta che visito un nodo, il cammino che mi ha por- tato su quel nodo `e il cammino minimo per raggiungerlo. Di conseguenza anche se non ho percorso tutti gli archi entranti in quel nodo so gi`a che non mi porter`a vantaggio esplorarli e potr`o assegnare quel nodo all’insieme dei nodi definitivi e non lo visiter`o pi`u. Come possiamo apprezzare nella figura 4.1 a pagina 35, sotto le seguenti condizioni:
x> z l< h + m + n batt(S, A) − l > j batt(S, A) − h − m − n < j
l’algoritmo di Dijkstra per veicoli elettrici, per costruzione, non visita il nodo E. Al contrario, come possiamo notare nella figura 4.2 a pagina 36, l’algoritmo di Bellman-Ford per veicoli elettrici visita il nodo E. Questo succede perch´e l’algoritmo di Bellman-Ford `e strutturato per lavorare su grafi in cui i pesi di alcuni archi possono essere negativi. Per questa ragione l’algoritmo percorre tutti gli archi, almeno fino a che `e in grado di rilassare i nodi.
Quindi nel caso in figura 4.2 a pagina 36 l’algoritmo visita anche il nodo E. Questo succede perch´e l’algoritmo di Bellman-Ford procede per in modo iterativo fino a che non c’`e pi`u un gua- dagno. Visita, quindi, ad ogni iterazione, tutti i nodi raggiungibili distanti un solo arco dal nodo in cui si trova, in questo modo il nodo B viene visitato prima seguendo la strada che consuma meno e quindi il veicolo ha abbastanza batteria per raggiungere il nodo E. Questa situazione per`o non si verifica sempre, ad esempio sotto le seguenti condizioni, figura 4.3 a pagina 37:
CAPITOLO 4. DIJKSTRA PER VEICOLI ELETTRICI x< z
l> h + m + n batt(S, A) − l < j batt(S, A) − h − m − n > j
Il nodo E non viene visitato n´e utilizzando l’algoritmo di Dijkstra per veicoli elettrici n´e uti- lizzando l’algoritmo di Bellman-Ford per veicoli elettrici in quanto il percorso che porterebbe a scoprire anche il nodo E si trova a pi`u archi di distanza rispetto a quello che impiega tempo minore. Una volta scoperto il percorso che impiega tempo minore, essendo questa la nostra priorit`a, l’algoritmo non aggiorner`a il valore di quel nodo anche se questo consentirebbe di scoprire il nodo E. Per avere la certezza di raggiungere un nodo, quando possibile, si potrebbe scegliere di eseguire l’algoritmo con la quantit`a di batteria come peso da ottimizzare invece che con il tempo di percorrenza.
Eseguendo l’algoritmo con lo scopo di trovare tutti i percorsi minimi tra i nodi torretta, si `e notato che i percorsi variavano solo in carenza di batteria e che la percentuale di percorsi diversi si aggirava intorno all’h. In compenso la differenza nei tempi di esecuzione tra l’algoritmo di Dijkstra e quello di Bellman-Ford si aggirava intorno alle 300 volte, in favore del primo. Per questi motivi si `e scelto di utilizzare l’algoritmo di Dijkstra invece di quello di Bellman-Ford. Per rendere pi`u accurato l’algoritmo si sarebbe potuto scegliere di includere un controllo sulla presenza di un percorso di minimo consumo nel caso in cui non l’algoritmo di Dijkstra non avesse trovato nessun percorso. Si `e deciso, tuttavia, di non inserire questo controllo poich`e avrebbe rallentato l’algoritmo fornendo una informazione poco significativa. Si tenga a mente che i consumi di un veicolo elettrico dipendono da tanti fattori e, nella quasi totalit`a dei casi, ci trovavamo di fronte a guadagni di batteria irrisori.
CAPITOLO 4. DIJKSTRA PER VEICOLI ELETTRICI
Capitolo 5
SOTTOGRAFO DELLE TORRETTE
Trovato l’algoritmo migliore per calcolare il percorso di un veicolo elettrico, ci si `e trovati di fronte al problema della ricarica. I veicoli elettrici per loro natura hanno un’autonomia limitata alla capacit`a della propria batteria. Esaurita l’energia disponibile nella batteria necessitano di una sosta per ricaricare.
Questa necessit`a di ricaricare presenta, a livello di algoritmo, un ostacolo importante. Ogni qualvolta ci sia il bisogno di ricaricare sar`a necessario ricalcolare il percorso che passa per tutte le torrette di ricarica, al fine di trovare la torretta che impone la deviazione pi`u breve dal percorso ideale ovvero quello senza ricariche.
Si `e quindi deciso di utilizzare un sottografo delle torrette [BSWZ17] ovvero una struttura che raccoglie tutti i percorsi ottimi tra i nodi torretta presenti. L’utilizzo di questa struttura consente di velocizzare il calcolo per la ricerca del percorso ottimale in caso di ricarica. In que- sto modo, ogni volta che si render`a necessario il calcolo di un percorso contenente una o pi`u soste per la ricarica del veicolo, non ci sar`a bisogno di ricalcolare tutte le possibili combinazioni di percorsi che includono una o pi`u torrette nel tragitto. Tutte queste combinazioni saranno gi`a precalcolate all’interno del sottografo e sar`a quindi sufficiente, una volta certi della neces- sit`a di ricaricare, entrare nel sottografo delle torrette per trovare il percorso migliore fino alla destinazione.
CAPITOLO 5. SOTTOGRAFO DELLE TORRETTE
5.1
Creazione del sottografo
Per creare il sottografo delle torrette `e stato eseguito l’algoritmo di Dijkstra per veicoli elettrici prendendo come punto di partenza ogni torretta e non specificando nessun punto di destina- zione; in questo modo, l’algoritmo, trova tutti i percorsi che hanno come partenza la torretta selezionata e come destinazione tutte le altre torrette. Ogni nodo del sottografo contiene come informazioni il numero del nodo nel grafo di origine, le coordinate del nodo torretta e l’in- dirizzo della torretta. Ogni nodo `e in grado di contenere anche le informazioni sulla singola torretta, come ad esempio: il numero di postazioni di carica, la velocit`a, il tipo di attacco com- patibile, etc. Ogni arco del sottografo invece, oltre a i dati relativi all’identificazione dell’arco, immagazzina anche la distanza del percorso minimo per raggiungere il nodo, ovvero: il tempo di percorrenza dell’arco, l’insieme dei nodi che compongono il percorso minimo e il consumo di batteria lungo quel percorso. La costruzione del sottografo viene effettuata in modo che ogni arco rappresenti il percorso minimo tra i nodi, calcolato sul grafo originale, effettuabile con il massimo della capacit`a di batteria a disposizione. Nella nostra sperimentazione che ha come oggetto la regione Toscana sono stati costruiti due sottografi utilizzando due diversi approc- ci: nel primo caso si `e utilizzato l’algoritmo di Dijkstra per veicoli elettrici nel secondo, ci si `e approcciati al problema utilizzando l’algoritmo di Bellman-Ford per veicoli elettrici. Tra i sot- tografi risultanti dai due algoritmi si `e potuta apprezzare una leggera differenza, il sottografo costruito utilizzando l’algoritmo di Bellman-Ford per veicoli elettrici aveva . archi mentre il sottografo risultante dall’algoritmo di Dijkstra per veicoli elettrici ne aveva ., per una differenza di archi, equivalenti all’h. Per quanto invece riguarda invece i tempi di esecu- zione dei due algoritmi, come abbiamo gi`a visto in precedenza, l’algoritmo di Bellman-Ford per veicoli elettriciimpiega un tempo di esecuzione estremamente pi`u lungo rispetto all’algoritmo di Dijkstra per veicoli elettrici. Considerato il piccolo vantaggio in termini di numero di percorsi trovati relativo all’utilizzo dell’algoritmo di Bellman-Ford per veicoli elettrici rispetto al grande svantaggio in termini di tempi di esecuzione, si `e optato per l’utilizzo dell’algoritmo di Dijkstra per veicoli elettriciper la costruzione dei sottografi delle torrette.