Trip planning methods for electric vehicles

(1)

Corso di Laurea Magistrale in Data Science and Business Informatics

TESI DI LAUREA

TRIP PLANNING METHODS FOR ELECTRIC VEHICLES

RELATORE

Prof. Mirco NANNI

CANDIDATO

Francesco RALLIS

(2)

Indice

1 INTRODUZIONE 1

1.1 La necessit`a . . . 1

1.2 Il problema . . . 2

1.3 L’obiettivo della tesi . . . 2

2 BACKGROUND 4 2.1 Grafo . . . 4 2.2 Cammini minimi . . . 5 2.2.1 Rilassamento . . . 6 2.2.2 Dijkstra . . . 6 2.2.3 Bellman-Ford . . . 7

2.3 Caratteristiche del veicolo elettrico . . . 8

2.4 Consumi nei veicoli elettrici . . . 9

2.4.1 Regenerative Braking System . . . 10

3 PREPROCESSING 12 3.1 Open Street Map . . . 12

3.1.1 Velocit`a sugli archi . . . 13

3.1.2 Pendenza archi . . . 16

3.1.3 Tempo di percorrenza . . . 23

3.1.4 Calcolo consumo . . . 23

3.2 Open Charge Map . . . 26

(3)

4 DIJKSTRA PER VEICOLI ELETTRICI 29

4.1 Pseudocodice . . . 30

4.1.1 Vincolo di batteria . . . 31

4.1.2 Ricarica . . . 31

4.1.3 Anxiety value . . . 32

4.2 Confronto con Bellman-Ford per veicoli elettrici . . . 33

5 SOTTOGRAFO DELLE TORRETTE 38 5.1 Creazione del sottografo . . . 40

5.2 Utilizzo del sottografo . . . 41

6 APPROCCI EURISTICI 46 6.1 Euristica 1 . . . 46

6.2 Euristica 2 . . . 48

6.3 Euristica 3 . . . 48

6.4 Scelta del range . . . 51

7 ESPERIMENTI 53 8 CONCLUSIONI 64 8.1 Lavori futuri . . . 65

(4)

Elenco delle figure

2.1 Rilassamento arco . . . 6

2.2 E-pedal . . . 11

3.1 Distribuzione della velocit`a massima tra i valori non nulli (10%) . . . 13

3.2 Velocit`a massima Toscana utilizzando l’attributo . . . 15

3.3 Velocit`a massima porzione della Toscana utilizzando l’attributo . . . 16

3.4 Velocit`a massima Toscana utilizzando l’attributo . . . 17

3.5 Velocit`a massima porzione della Toscana utilizzando l’attributo . . . 18

3.6 Pendenza arco . . . 18

3.7 Distribuzione pendenze% . . . 19

3.8 Altitudine nodi Toscana . . . 20

3.9 Altitudine nodi porzione della Toscana . . . 21

3.10 Pendenza archi Toscana . . . 22

3.11 Pendenza archi porzione della Toscana . . . 23

3.12 Torrette ricarica Toscana . . . 28

4.1 Dijkstra per veicoli elettrici . . . 35

4.2 Bellman-Ford per veicoli elettrici . . . 36

4.3 Dijkstra per veicoli elettrici . . . 37

5.1 Sottografo delle torrette . . . 39

5.2 Distribuzione differenze tempi di percorrenza tra Dijkstra e Dijkstra per EV . . 44 5.3 Distribuzione differenze tempi di percorrenza tra Dijkstra e Bellman Ford per EV 45

(5)

7.1 Frequenza di ricarica . . . 54

7.2 Scatter plot consumo batteria su tempo di percorrenza . . . 55

7.3 Scatter plot consumo batteria su lunghezza arco . . . 56

7.4 Percorso con deviazione per ricarica . . . 57

7.5 Tempi di esecuzione e percorrenza per 100 tragitti . . . 58

7.6 Tempi di esecuzione e percorrenza per 100 tragitti solo euristiche . . . 58

7.7 Tempi di esecuzione e percorrenza per 100 tragitti solo euristiche Knn . . . 59

7.8 Scatter plot travel time euristicha 2Knn su travel time euristica 3Knn su 1.000 simulazioni . . . 60

7.9 Scatter plot runtime euristicha 2Knn su runtime euristica 3Knn su 1.000 simu-lazioni . . . 60

7.10 Scatter plot travel time euristicha 2Knn su travel time euristica 3Knn su 5.000 simulazioni . . . 61

7.11 Scatter plot runtime euristicha 2Knn su runtime euristica 3Knn su 5.000 simu-lazioni . . . 61

7.12 Scatter plot runtime euristica 2Knn su runtime euristica 3Knn su 5.000 simula-zioni valori medi calcolati su 5 run . . . 63

7.13 Scatter plot traveltime LONG-SEARCH su traveltime euristica 3Knn su 100 simulazioni . . . 63

(6)

Abstract

In questo lavoro si è andati ad analizzare un argomento estremamente attuale, i veicoli elet-trici, soffermandosi però sull’impatto che potrebbe avere per un automobilista il passaggio a un mezzo alimentato a energia pulita. Ci si è concentrati su una delle molteplici complicazioni che ci si trova costretti ad affrontare ogni qual volta si decida di intraprendere un percorso inno-vativo. Si è quindi sollevato il problema della disponibilità immediata di energia e si è cercato di trovare un metodo di pianificazione dei viaggi che potesse allo stesso tempo rendere meno invalidante questo problema senza dover però impiegare tempi eccessivamente lunghi per la pianificazione. È stato sin da subito evidente che il problema non aveva un’unica soluzione e che le soluzioni ottime sarebbero state troppo dispendiose da calcolare. Si è quindi cercata una soluzione più pratica al problema. In primo luogo è stata scartata l’ipotesi delle molteplici soluzioni, portando il problema dall’essere a due variabili ad un problema ad un’unica variabile, successivamente si è andati a cercare un algoritmo che approssimasse al meglio una situazione reale. Trovato l’algoritmo che descrivesse al meglio il percorso da scegliere e l’autonomia residua del veicolo, si è affrontato il problema delle ricariche e quindi delle deviazioni dal per-corso migliore per ricaricare il veicolo.

(7)

INTRODUZIONE

Il mercato dei veicoli elettrici `e in forte espansione, secondo l’International Energy Agency la flotta di veicoli elettrici nel 2018 ha superato i 5.1 milioni di unit`a e con un aumento di 2 milioni di veicoli rispetto all’anno precedente. Nel solo 2018 il mercato dei veicoli elettrici ha raddop-piato le vendite [IEA19] . Le ragioni di questo aumento delle vendite, spesso disomogeneo, sono da ricercarsi inizialmente in un netto e costante rafforzamento della consapevolezza che il pianeta su cui abitiamo necessita di una maggiore attenzione alla sua preservazione, suppor-tato da incentivi governativi quali l’intensificazione dell’infrastruttura elettrica di ricarica. In secondo luogo nelle nuove tecnologie che permettendo una maggiore durata delle batterie e un minor consumo da parte dei veicoli rendono un eventuale passaggio ad un veicolo % elettrico molto meno traumatico rispetto a quanto potesse essere qualche anno fa.

1.1 La necessit`a

Nonostante questo aumento delle vendite molti consumatori sono ancora scettici nei confronti del passaggio all’elettrico. Questa avversione è da ricercarsi nella convinzione comune che il passaggio a un veicolo % elettrico possa avere un forte impatto sulla propria vita quoti-diana. Una delle più grandi differenze tra un veicolo alimentato a combustibile e un veicolo a batteria sta nella disponibilità immediata di energia necessaria alla sua alimentazione. Il

(8)

tem-CAPITOLO 1. INTRODUZIONE

mentre una sosta per ricaricare la batteria di un veicolo elettrico, in base alle capacità della torretta di ricarica, è solitamente superiore all’ora. Tra gli scenari di immaginario più comuni di chi è restio al passaggio a questo genere di veicoli c’è quello in cui ci si trova di fronte a una situazione di impellente necessità e la macchina non è provvista di batteria carica e si è di conseguenza costretti a trovare una soluzione alternativa, con tutti i disagi che ciò comporta. Si rende quindi necessario uno studio su come e quanto cambi la vita di un individuo con il passaggio a un veicolo % elettrico.

Per poter effettuare un tale studio vi `e le necessit`a di simulare situazioni di vita quotidiana di un individuo-tipo alla guida di un veicolo elettrico, per confrontarlo poi con lo stesso alla guida di uno a combustione.

1.2 Il problema

I dati sulla mobilità a nostra disposizione ci consentono di analizzare agevolmente gli sposta-menti di un individuo alla guida di un veicolo alimentato a combustibile ma manca un metodo altrettanto accurato che simulasse lo stesso percorso intrapreso però con un veicolo elettrico. In questa situazione i comuni software per la pianificazione di viaggi in auto non sono utili in quanto non tengono in considerazione dei fattori fondamentali che differenziano le due catego-rie di veicoli, nello specifico non considerano l’autonomia limitata del veicolo, non considerano la variabilità dei consumi in base alla pendenza della strada che, in alcuni casi, porta il veicolo a ricaricare durante la marcia e non considerano l’eventualità in cui si renda necessaria una ricarica durante il tragitto, a fronte dell’impossibilità per il veicolo di raggiungere il punto di destinazione. Si è quindi reso necessario uno strumento in grado di pianificare un viaggio per un veicolo elettrico tenendo in considerazione tutte queste variabili e questi possibili scenari che non si verificano quando si pianifica un viaggio per un veicolo alimentato a combustibile.

1.3 L’obiettivo della tesi

L’obiettivo della tesi `e quindi quello di creare un nuovo algoritmo, basato su algoritmi noti, in grado di pianificare i viaggi per veicoli elettrici. Partendo dalla necessit`a di pianificare il

(9)

viaggio, nel capitolo 2 sono stati considerati il problema dei percorsi minimi, valutando l’ap-plicabilità al problema di due algoritmi, Dijkstra e Bellman-Ford; le caratteristiche del veicolo, valutando quale veicolo scegliere come prototipo per lo studio dei consumi e il problema dei consumi nei veicoli elettrici, attraverso una funzione di consumo della batteria basata sulle ca-ratteristiche del veicolo. Nel capitolo 3 si è curata l’implementazione di un grafo rappresentante l’infrastruttura stradale arricchito dalla presenza di torrette di ricarica. Nel capitolo 4 è stata ideata e implementata una versione modificata dell’algoritmo di Dijkstra la quale fornisce un percorso minimo tenendo in considerazione le variabili carica residua, pendenza della strada e quindi consumo del veicolo. Nel capitolo 5 è stato introdotto il concetto di sottografo delle torrette, ovvero un grafo quasi completamente connesso dove i nodi rappresentano le torrette di ricarica e gli archi i percorsi ottimi. Si è inoltre illustrata la prima versione dell’algoritmo di Dijkstra per veicoli elettrici che oltre alle variabili precedenti prende in considerazione anche le soste per ricaricare il veicolo, trovando cos`ı il percorso più veloce anche quando c’è la neces-sità di sostare per ricaricare la batteria del veicolo. Nel capitolo 6 sono state proposte alcune euristiche per accelerare il processo di selezione del percorso migliore nel caso in cui il veicolo debba effettuare almeno una sosta per ricaricare la batteria, individuando la parte dell’algorit-mo con complessità maggiore e dell’algorit-modificandone il funzionamento in dell’algorit-modo da ottenere risultati con elevati livelli di precisione in tempi più brevi. Nel capitolo 7 sono stati effettuati diversi esperimenti per valutare l’efficacia e l’efficienza delle euristiche proposte, confrontando tra di loro le velocità di esecuzione e i tempi di percorrenza per ogni euristica proposta.

(10)

Capitolo 2

BACKGROUND

In questo capitolo verranno illustrati gli algoritmi per il calcolo dei percorsi minimi, in partico-lare l’algoritmo di Dijkstra e l’algoritmo di Bellman-Ford, ai quali ci si è ispirati per la creazione dell’algoritmo per veicoli elettrici. Si evidenzieranno inoltre le caratteristiche del veicolo elet-trico preso in considerazione come prototipo per lo studio. Infine si illustrerà la funzione di consumo utilizzata per calcolare i consumi dei veicoli elettrici in relazione alla pendenza della strada, alla velocità di percorrenza e alla distanza percorsa.

2.1 Grafo

Il primo passo per rendere in termini matematici un problema pratico come quello della pianifi-cazione del percorso per un veicolo elettrico, `e stato quello di definire le strutture matematiche che avrebbero rappresentato gli elementi fondamentali del problema. Si `e quindi utilizzato un grafo per rappresentare la rete stradale.

Un grafo, in matematica, `e la configurazione formata da un insieme di punti ( vertici o nodi ) e un insieme di linee ( archi ) che uniscono coppie di nodi.[CLRS09]

Nel caso in questione, i nodi rappresentano i punti di intersezione tra le strade e gli archi rappresentano le strade della rete viaria.

(11)

Il grafo `e la struttura migliore per rappresentare una rete stradale in quanto consente di im-magazzinare delle informazioni aggiuntive per ogni nodo e per ogni arco. I nodi possono, per esempio, mantenere: i valori delle coordinate geografiche del punto, informazioni relative al-la funzione di quel nodo (supermercato, stazione di servizio, farmacia, bar, etc.), indirizzo del punto e altre informazioni utili. Anche gli archi possono essere etichettati con informazioni utili come ad esempio: il nome della via che l’arco rappresenta, la geometria della strada, il peso dell’arco, la pendenza della strada, il tipo di strada e molte altre. Inoltre i nodi del grafo di solito immagazzinano anche la lista di adiacenza, uno strumento molto utile quando si tratta di ottenere informazioni per cui sia ad esempio necessaria una visita del grafo o quando si `e interessati a conoscere i vicini di un certo nodo.

2.2 Cammini minimi

L’idea alla base della risoluzione del problema di pianificazione dei percorsi per veicoli elettrici era quella di trovare il tragitto pi`u veloce. Quando si tratta di trovare il tragitto pi`u veloce tra due punti su un grafo si sta parlando del problema dei cammini minimi.

”In un problema di cammini minimi viene fornito un grafo orientato e pesato G= (V, E), con una funzione peso w∶ E → R che associa ad ogni arco un peso a valore nei reali. Il peso di un cammino p= ⟨v, v, ..., vk⟩ `e la somma dei pesi

degli archi che lo costituiscono:

w(p) = ∑k_i=w(vi−, vi)

Il peso di cammino minimo da u a v `e definito come:

δ(u, v) =⎧⎪⎪⎪⎪ ⎨⎪⎪⎪ ⎪⎩

min{w(p)∶ u ; v} se esiste un cammino da u a v

∞ altrimenti

(12)

cam-CAPITOLO 2. BACKGROUND

I due algoritmi su cui si `e basato lo studio per la risoluzione del problema in questione sono stati l’algoritmo di Dijkstra e l’algoritmo di Bellman-Ford.

2.2.1 Rilassamento

Gli algoritmi che presenteremo in questo capitolo usano la tecnica del rilassamento. Per ogni vertice v∈ V si mantiene un attributo d [v] che `e un limite superiore al peso di un cammino minimo dalla sorgente s a v. Chiameremo d[v] una stima di cammino minimo. Rilassare un arco (u, v) significa verificare se passando per l’arco (u, v) si ottiene un valore pi`u basso di d[v]. Inizialmente tutti i nodi vengono inizializzati ad un valore infinito. Per ogni vertice v∈ V , d [v] ←Ð ∞[CLRS09].

if d[v] < d [u] + w(u, v) then d[v] = d [u] + w(u, v); π[v] = u;

end

Algorithm 1:RELAX(u,v,w)

Se la distanza per raggiungere v è maggiore della somma tra, la distanza per raggiungere u e la distanza tra u e v. Allora l’arco verrà rilassato e v prenderà come distanza la somma tra la distanza per raggiungere u e la distanza tra u e v. Verrà assegnato u come predecessore di v.

Figura 2.1: Rilassamento arco

2.2.2 Dijkstra

L’algoritmo di Dijkstra risolve il problema dei cammini minimi con sorgente singola su un gra-fo orientato e pesato G= (V, E) nel caso in cui tutti i pesi degli archi siano non negativi. Dato

(13)

un grafo orientato e pesato G= (V, E) con sorgente s e funzione peso w ∶ E → R+. L’algoritmo

crea e aggiorna un insieme S contenente tutti i nodi resi definitivi, ovvero il cui percorso mini-mo dalla sorgente è stato già definito. L’algoritmini-mo seleziona il nodo con la stima del cammino minimo più bassa, lo inserisce nell’insieme S e rilassa tutti gli archi uscenti da quel nodo. Viene implementato con una coda di priorità che mantiene in cima il nodo con la stima più bassa. L’algoritmo di Dijkstra sfrutta il principio per cui ogni volta che visito un nodo il cammino che mi ha portato su quel nodo è il cammino minimo per raggiungerlo. Quindi anche se non ho percorso tutti gli archi entranti in quel nodo, so già che non mi porterà vantaggio esplo-rarli e potrò assegnare quel nodo all’insieme dei nodi definitivi e non lo visiterò più. Questo principio sarà utile per comprendere il motivo per cui si è deciso di valutare anche l’algoritmo Bellman-Fordnonostante non ci fossero pesi negativi sugli archi.

INITIALIZE-SINGLE-SOURCE(G, s) ; S= ∅; Q= V [G]; while Q≠ ∅ do u= EXTRACT-MIN (Q); S= S ∪ {u};

for each vertex v∈ Adj [u] do RELAX(u, v, w);

end end

Algorithm 2:DIJKSTRA(G,w,s)

2.2.3 Bellman-Ford

L’algoritmo di Bellman-Ford risolve il problema dei cammini minimi con sorgente singola su un grafo orientato e pesato G= (V, E) nel caso pi`u generale in cui i pesi degli archi possano essere negativi. Dato un grafo orientato e pesato G= (V, E) con sorgente s e funzione peso w∶ E → R. L’algoritmo verifica se esiste o meno un ciclo di peso negativo. Restituisce falso se incontra un ciclo negativo. Altrimenti restituisce vero e calcola i cammini minimi tra la

(14)

CAPITOLO 2. BACKGROUND sorgente e gli altri nodi.

INITIALIZE-SINGLE-SOURCE(G, s) ; for i=  to ∣V [G] ∣ −  do

for each edge(u, v) ∈ E [G] do RELAX(u, v, w);

end end

for each edge(u, v) ∈ E [G] do if d[v] < d [u] + w (u, v) then

return FALSE; end

end

return TRUE

Algorithm 3:BELLMAN-FORD(G,w,s)

Anche l’algoritmo di Bellman-Ford cos`ı come quello di Dijkstra utilizza la funzione di rilas-samento, solo che a differenza di Dijkstra rende definitivo un nodo dopo averlo esplorato ma mantiene la possibilit`a di rilassare nuovamente nel caso in cui questo venga raggiunto nuova-mente con un percorso meno costoso. Questo lo rende idoneo al calcolo di percorsi minimi su grafi con pesi negativi sugli archi.

2.3 Caratteristiche del veicolo elettrico

Una delle prime scelte di fronte a cui ci si è trovati è stata la selezione del veicolo da utilizzare come prototipo per la sperimentazione. Tra i vari veicoli elettrici presenti sul mercato si è preferita la Nissan LEAF, per diverse ragioni.

In Norvegia Nissan LEAF `e l’auto pi`u venduta in assoluto nel 2018.

Con un acquisto ogni 10 minuti, la nuova Nissan LEAF `e il veicolo % elettrico pi`u venduto in Europa nel 2018.

In Italia, la nuova Nissan LEAF è l’auto % elettrica più venduta sia nel mese di settembre con unità che nel periodo gennaio-settembre  con . unità, pari a una quota di mercato

(15)

del %.[Nis17]1

Principalmente si è scelta la Nissan LEAF poichè risultata essere la macchina più diffusa in Europa e in Italia. Un’altra ragione per cui la scelta è ricaduta su questo veicolo è stata la categoria in cui si colloca, una berlina  volumi, ovvero un veicolo adatto sia alla città che a viaggi medio-lunghi, una categoria di veicoli molto versatile e adatta a molteplici situazioni. Infine il lavoro di Inghirami a cui ci si è ispirati per la realizzazione del modello di consumo per il veicolo elettrico, è stato anch’esso effettuato prendendo come veicolo di riferimento una Nissan LEAF.

Il modello utilizzato in questa sperimentazione `e la versione 

Modello Leaf kW h Potenza kW(CV ) Coppia massima N m Batteria kW h Autonomia km 0–100 km/h , s Velocit`a max(Km/h)  Ricarica standard .kW , h Ricarica domestica h

2.4 Consumi nei veicoli elettrici

Nei veicoli alimentati a combustibile, quando si parla di consumi, c’è spesso una certa diffe-renza tra i valori di consumo dichiarati da parte delle aziende produttrici e i valori reali di consumo rilevati dagli utilizzatori. Questa discrepanza aumenta quando si parla di veicoli elet-trici, questo accade perché i consumi nei veicoli elettrici sono ancora più difficili da calcolare rispetto a quelli dei veicoli alimentati a combustibile. La capacità delle batterie è soggetta alle

(16)

CAPITOLO 2. BACKGROUND

condizioni climatiche esterne, in particolare a variazioni di temperatura e umidità. Come si può notare dalla tabella lo stesso veicolo su percorsi diversi e in condizione climatiche diverse può guadagnare anche il % di autonomia.

Real Range between − km

City - Cold Weather km City - Mild Weather km Highway - Cold Weather km Highway - Mild Weather km Combined - Cold Weather km Combined - Mild Weather km

2 3

Come se non bastasse l’autonomia di un veicolo elettrico `e anche influenzata da quanto il veicolo `e in grado di ricaricare durante la marcia. I veicoli elettrici, cos`ı come quelli ibridi, utilizzano un sistema di frenata rigenerativo.

2.4.1 Regenerative Braking System

Il Regenerative Braking System o Sistema Rigenerativo di Frenata è un meccanismo di recupero dell’energia che rallenta il veicolo e ne trasforma l’energia cinetica in una forma di energia che può essere accumulata e conservata per un utilizzo futuro, aumentando l’autonomia del vei-colo fino al %. Solitamente i veicoli elettrici sono equipaggiati con un sistema rigenerativo di frenata idraulico che permette di avere la stessa sensazione di frenata che si avrebbe con un veicolo non elettrico [Cha14]. La casa automobilistica Nissan ha invece sviluppato un sistema di frenata assistita, chiamato e-Pedal, il quale consiste in un dispositivo che inizia a lavorare nel momento in cui il pilota alza il piede dal pedale dell’acceleratore, facendo decelerare il veicolo gradualmente e proporzionalmente alla pressione esercitata sul pedale. In questo modo viene ridotto al minimo l’utilizzo del pedale del freno e viene cos`ı incrementata la quantità di energia cinetica recuperabile per mezzo della frenata. L’e-Pedal, sfrutta il principio del Sistema Rige-nerativo di Frenata per cui un motore elettrico che inverte il suo funzionamento si trasforma in un generatore. Un elemento importante considerando che a bordo dei veicoli elettrici tutti

2_{Indication of real-world range in several situations. Cold weather: ’worst-case’ based on -10°C and use of}

heating. Mild weather: ’best-case’ based on 23°C and no use of A/C. The actual range will depend on speed, style of driving, climate and route conditions.

(17)

Figura 2.2: E-pedal

questi meccanismi, come il servofreno, di solito azionati dal motore a scoppio, sono sostituiti con dispositivi elettrici che necessitano di energia per essere alimentati.[Nis17]4

(18)

Capitolo 3

PREPROCESSING

In questo capitolo verranno illustrati i passi compiuti nella parte di preprocessing, verranno quindi mostrate le librerie utilizzate e, inoltre, verranno argomentate le scelte operate nella co-struzione del grafo e in che modo sono stati creati i nodi torretta. Essendo necessaria un strut-tura a grafo si è optato per Open Street Map e se ne è utilizzata la libreria OSMnx[Boe17] si è inoltre utilizzata la libreria NetworkX[HSSC08] che comprende una serie di tool per operare su grafi. Per recuperare la posizione delle torrette di ricarica sono state utilizzate le coordinate fornite dalla piattaforma Open Charge Map.

3.1 Open Street Map

Open Street Map è una piattaforma che fornisce dati geografici sulle mappe di tutto il mondo. ”OpenStreetMap è costruito da una comunità di mappatori che contribuiscono e mantengono i dati sulle strade, sentieri, caffè, stazioni ferroviarie e molto altro ancora, in tutto il mondo.”1

Tramite una chiamata della funzione ox.graph from place(city, network type=networkType) si ottiene la mappa della regione di interesse sotto forma di grafo. Nel caso in questione si `e presa in considerazione la regione Toscana come base per la sperimentazione in quanto si era in possesso di dati reali di mobilit`a sui quali poter valutare l’algoritmo.

(19)

Una volta ottenuto il grafo della regione di interesse, deve essere modificato in modo da soddisfare i requisiti necessari alla risoluzione del problema. Nel caso in questione si è dovuto prendere in considerazione il fatto che un veicolo elettrico ha una autonomia limitata, non ha la possibilità di fare rifornimento dove e quando vuole ma, soprattutto, che i consumi di un veicolo elettrico dipendono, oltre che dalla velocità di marcia e dalla distanza percorsa anche dalla pendenza della strada. Si sono quindi dovute calcolare le velocità massime di percorrenza sugli archi, le altitudini dei nodi e, da queste, successivamente, le pendenze dei rispettivi archi. Si è poi calcolato il tempo di percorrenza dell’arco da parte del veicolo e infine si è potuto calcolare il consumo del veicolo sull’arco. Tutte queste informazioni aggiuntive sono state inserite nei nodi e negli archi del grafo di modo da ottenere una struttura contenente le informazioni necessarie al funzionamento dell’algoritmo per veicoli elettrici di cui verrà discusso in seguito.

3.1.1 Velocit`a sugli archi

(20)

CAPITOLO 3. PREPROCESSING

Per quanto riguarda la velocità sugli archi, i dati forniti da Open Street Map sono scarsi, poco accurati e spesso mancanti, utilizzando l’attributo MaxSpeed, ovvero l’attributo che dovrebbe fornire informazioni sulla velocità massima dell’arco, solo il 10% degli archi ha un valore di velocità massima. Possiamo notare dal grafico [ 3.1 nella pagina precedente] che la velocità più frequente è quella di km/h, trovandoci in Italia il dato risulta coerente con l’infrastruttura viaria italiana. Per ovviare alla mancanza di dati si è dovuto quindi ricorrere ad un espediente per la loro stima. Si è scelto l’attributo Highway in quanto presente su ogni arco. Questo attributo rappresenta il tipo di strada e prende i seguenti valori:

[’alley’, ’crossing’, ’disused’, ’emergency bay’, ’living street’, ’motorway’, ’motorway link’, ’no’, ’primary’, ’primary link’, ’razed’, ’residential’, ’rest area’, ’road’, ’secondary’, ’secondary link’, ’tertiary’, ’tertiary link’, ’trunk’, ’trunk link’, ’unclassified’, ’yes’]. Partendo da questi valori è stato creato un dizionario avente come chiave il tipo di strada e come valore il rispettivo limite di velocità. I limiti di velocità sono stati scelti in base ad una tabella di conversione presente sul sito della Polizia di Stato.

{’alley’: 50, ’crossing’: 50, ’disused’: 50, ’emergency bay’: 50, ’living street’: 50, ’motorway’: 130, ’motorway link’: 130, ’no’: 50, ’primary’: 110, ’primary link’: 110, ’razed’: 50, ’residential’: 50, ’rest area’: 50, ’road’: 50, ’secondary’: 90, ’secondary link’: 90, ’tertiary’: 70,

’tertiary link’: 70, ’trunk’: 110, ’trunk link’: 110, ’unclassified’: 50, ’yes’: 50}

È stato poi effettuato un plot della Toscana con le strade colorate in base alla velocità massima di percorrenza [Figura 3.2 nella pagina successiva] per vedere se i risultati fossero coerenti con l’infrastruttura della rete viaria Toscana. Lo si è inoltre confrontato con il plot effettuato precedentemente, utilizzando l’attributo MaxSpeed [Figura 3.4 a pagina 17].

I valori di velocità sono distribuiti in base ad una scala cromatica che va dalrossoper le ve-locità più basse alverdeper le velocità più alte. Si può inoltre notare che il colore predominante è ilgiallo, plausibilmente il colore che rappresenta la velocità di 50 km/h. Il che risulta coeren-te con la distribuzione iniziale di velocità massime. Si può notare come l’utilizzo dell’attributo Highwayabbia incrementato la quantità di valori di velocità massima e come la distribuzione dei valori di velocità sia coerente con l’infrastruttura viaria italiana.

(21)

Figura 3.2: Velocit`a massima Toscana utilizzando l’attributo MaxSpeed

(22)

Figura 3.3: Velocit`a massima porzione della Toscana utilizzando l’attributo MaxSpeed

3.1.2 Pendenza archi

Come detto in precedenza, ogni nodo rappresenta una intersezione tra due o più archi e per calcolare il consumo del veicolo sull’arco è necessaria tra le altre la pendenza dell’arco stesso. Per calcolare la pendenza dell’arco si è partiti dall’altitudine dei nodi. Si è utilizzata la libreria srtm2, per ottenerne l’elevazione [Figura 3.9 a pagina 21]. Da questa si è calcolato il dislivello [Figura 3.10 a pagina 22]. Nel calcolo del dislivello si è notato che alcuni non erano graduali ma si presentavano con salti di svariati metri. Questo succede in quanto i dati di altitudine sono calcolati sul terreno e non considerano quindi infrastrutture quali gallerie, ponti e cavalcavia. Per ovviare a questo problema si è deciso di considerare  la pendenza su quei tratti. Un altro problema che si è dovuto affrontare è stato quello della mancanza dei valori di altitudine per alcuni nodi. In questo caso, si è deciso di assegnare, come valore di altitudine ai nodi che ne erano sprovvisti, la media dei valori dei nodi vicini. Una volta in possesso di valori coerenti di elevazione dei nodi, si è calcolata la distanza euclidea tra i nodi utilizzando la formula

Distanza=√LungStrada− Dislivello

2_{Lo Shuttle Radar Topography Mission `e un’impresa internazionale che `e riuscita ad ottenere un Modello}

(23)

Figura 3.4: Velocit`a massima Toscana utilizzando l’attributo Highway

(24)

Figura 3.5: Velocit`a massima porzione della Toscana utilizzando l’attributo Highway

Figura 3.6: Pendenza arco

Successivamente si calcolata la percentuale e l’angolo di pendenza dell’arco P endenza= Dislivello_Distanza

∡Pendenza = arctan(Pendenza)

Infine per verificare la coerenza dei dati ottenuti si è andati a vedere la distribuzione delle pen-denze e si è notato che l’andamento delle penpen-denze è per lo più simmetrico, il che è spiegabile dal fatto che la maggior parte delle strade sono a doppio senso e quindi sono in salita e in di-scesa con la stessa pendenza. La distribuzione delle pendenze ha le code per valori minori del −% e per valori maggiori del +% il che è coerente con i valori usuali di pendenza minima

(25)

e massima delle strade. Inoltre c’è una presenza consistente di valori tra il−% e il +% e un calo drastico per valori uguali allo % il che è molto coerente con una infrastruttura viaria cittadina, che è solitamente densa di strade quasi pianeggianti.[Figura 3.7]

(26)

(27)

(28)

(29)

Figura 3.11: Pendenza archi porzione della Toscana

3.1.3 Tempo di percorrenza

Open Street Map, per apprezzare il peso degli archi, fornisce la distanza in m. Partendo da que-sti valori, al fine di calcolare il consumo, è stato necessario il calcolo del tempo di percorrenza. Con i dati a disposizione non è stato possibile calcolare il tempo medio di percorrenza per un veicolo su un arco e si è quindi dovuta effettuare una stima di questi tempi. Per semplicità la velocità sull’arco è stata considerata costante.

3.1.4 Calcolo consumo

Calcolati tutti i valori necessari si è passati al calcolo del consumo. Si è partiti dalla funzione di consumo sviluppata in un precedente lavoro di tesi [Ing18]. Il valore di capacità della batteria, che sul veicolo preso a modello nel lavoro a cui ci si è ispirati, era di Kw, è stato portato a Kwper adeguarlo a quello attuale, è stato anche aggiornato il peso dell’autoveicolo ed è stato portato a ., aumentandolo di quasi Kg3 _{rispetto ai  del modello precedente. Si è}

implementata la funzione in Python per renderla compatibile con lo spazio di lavoro utilizzato.

(30)

CAPITOLO 3. PREPROCESSING # Area f r o n t a l e d e l v e i c o l o A = 2 . 2 7 # Massa d e l v e i c o l o Mcar = 1580 # Massa d e l g u i d a t o r e Md = 90 # C o e f f i c i e n t e d i r e s i s t e n z a a e ro di n am i c a Cd = 0 . 2 9 # C o e f f i c i e n t e d i r e s i s t e n z a a l r o t o l a m e n t o R = 0 . 0 1 2 # C a p a c i t d e l l a b a t t e r i a eBatCap = 38 # Massa t o t a l e TotalMass = Mcar+Md # E f f i c i e n z a d e l l a t r a s m i s s i o n e e f f G e a r = 0 . 9 7 # E f f i c i e n z a d e l motore e l e t t r i c o effMot = 0 . 9 5 # Potenza a u s i l i a r i a Paux = 0 # E f f i c i e n z a d e l l a b a t t e r i a e f f B a t t C h a r g e = 0 . 9 5 # E f f i c i e n z a s c a r i c a m e n t o b a t t e r i a e f f B a t t D i s c h a r g e = 0 . 9 8 # A c c e l e r a z i o n e d i g r a v i t g = 9 . 8 1 # D e n s i t a r i a rho = 1 . 2 0 4 1 # R e g e n e r a t i o n r a t i o (G = 0 . 3 5 in ECO MODE) r e g e n R a t i o = 0 . 3 5

(31)

d e f evBattCons ( distanceFromPrev , timeGap , speed , a c c e l , alpha ) : # R e s i s t e n z a a l r o t o l a m e n t o

F r r = R ∗ ( TotalMass ) ∗ g ∗ math . cos ( alpha ) # R e s i s t e n z a a re o d i n am i c a

Fa = 0 . 5 ∗ A ∗ Cd ∗ rho ∗ math .pow( speed , 2 ) # G r a v i t

Fgo = ( TotalMass ) ∗ g ∗ math . s i n ( alpha ) # Forza d ’ i n e r z i a F i = 1 . 0 5 ∗ ( TotalMass ) ∗ a c c e l # Forza t o t a l e F t o t = F r r + Fa + Fgo + F i # Forza t r a z i o n e meccanica P t o t = F t o t ∗ speed PmotOut = 0 i f ( P t o t >= 0 ) : PmotOut = P t o t / e f f G e a r e l s e : PmotOut = r e g e n R a t i o ∗ P t o t ∗ e f f G e a r PmotIn = 0 i f ( PmotOut >= 0 ) :

PmotIn = PmotOut / effMot e l s e :

PmotIn = PmotOut ∗ effMot Pbat = PmotIn + Paux

# M o d e l l a z i o n e b a t t e r i a eBat = 0

i f ( Pbat >= 0 ) :

(32)

eBat = Pbat ∗ timeGap ∗ e f f B a t t D i s c h a r g e # C a l c o l o DeltaSoC

kWh2Ws = 3 6 0 0 ∗ 1 e3

d e l t a S o C = eBat / ( eBatCap ∗kWh2Ws) r e t u r n d e l t a S o C

La funzione di consumo presentata è stata applicata ad ogni arco del grafo e ne è stato ricavato il valore di consumo sull’arco per il veicolo elettrico scelto come prototipo. Per semplicità, sono state ipotizzate costanti la velocità e la pendenza sull’arco, come velocità di percorrenza dell’arco è stato scelto il limite massimo di velocità consentito per quell’arco.

3.2 Open Charge Map

Open Charge Map è un servizio non-profit, non commerciale, ospitato e supportato da una comunità di imprese, enti di beneficenza, sviluppatori e appassionati di tutto il mondo ed è definito come:

”Il data base pubblico globale delle colonnine di ricarica.”4

Tramite le API di Open Charge Map viene effettuata una richiesta al server5_{, specificando}

l’area geografica di interesse, si ottiene in risposta un file JSON contenente la latitudine e la longitudine delle torrette presenti in quella zona e altre informazioni sul tipo di ricarica fornita.

3.2.1 Integrazione torrette di ricarica

Per integrare le torrette di ricarica nella struttura già presente si è inizialmente pensato di attri-buire la proprietà di nodo torretta al nodo più vicino alle coordinate geografiche della torretta. Cos`ı facendo ci si è resi conto che alcune torrette, specialmente quelle collocate all’interno di

4_{https://openchargemap.org/site/} 5_{https://api.openchargemap.io/v3/poi/}

(33)

resort di lusso, erano troppo distanti dal loro nodo più vicino. Per risolvere il problema dell’in-serimento di queste torrette particolari si è quindi optato per l’aggiunta di un nuovo nodo con proprietà di nodo torretta. Per la creazione di questi nuovi nodi si è innanzitutto calcolata la distanza tra le coordinate geografiche di ogni torretta e il suo nodo più vicino, si sono scelte le torrette con distanza superiore ad un certo valore6_.

Per queste torrette è stato ricercato l’arco più vicino. Tramite una funzione creata apposita-mente è stata scomposta la geometria dell’arco in punti, si è scelto il punto dell’arco più vicino alla torretta ed è stato trasformato in un nodo con proprietà di nodo torretta. Si è cos`ı divisa la geometria dell’arco in due e si sono ricostruiti i percorsi per e dal nuovo nodo. Nella Figu-ra 3.12 nella pagina seguente possiamo apprezzare la distribuzione delle torrette di ricarica, i nodi del grafo colorati in blu, sul territorio della Toscana. Come possiamo vedere la maggiore concentrazione delle torrette combacia con le grandi città mentre si dirada proporzionalmente nel momento in cui ce ne allontaniamo.

(34)

(35)

DIJKSTRA PER VEICOLI ELETTRICI

Nel caso preso in analisi non era possibile usare un algoritmo noto per valutare il percor-so minimo di un veicolo elettrico in quanto il problema di partenza non ammetteva un’unica soluzione. Non sarebbe stato nemmeno utile trovare tutte le possibili soluzioni S tali da per-mettere di raggiungere un nodo di arrivo v da un nodo di partenza s che impiegavano tempi t diversi con consumi c diversi per cui:

t[Si(s ; v)] < t [Sj(s ; v)] ⋀c[Si(s ; v)] > c [Sj(s ; v)]

OR

t[Si(s ; v)] > t [Sj(s ; v)] ⋀c[Si(s ; v)] < c [Sj(s ; v)]

Considerando che il nostro studio ha come scopo quello di andare a valutare l’impatto sulla vita quotidiana dell’individuo, nel caso di un passaggio ad un veicolo elettrico, è stata data una maggiore valenza al tempo che si impiega per percorrere un tragitto piuttosto che alla batteria che si consuma. Si è quindi deciso di considerare come variabile da minimizzare solo il tempo di percorrenza sull’arco, trattando la batteria come un vincolo al raggiungimento di alcuni nodi. A questo punto il problema poteva essere trattato come una variante del percorso minimo con un vincolo aggiuntivo. È stato quindi scelto un algoritmo noto, l’algoritmo di Dijkstra, ed è stato modificato con l’aggiunta di un vincolo alla funzione di rilassamento dei nodi. È stata inoltre apportata una modifica in modo da consentire l’aggiornamento del valore di batteria

(36)

CAPITOLO 4. DIJKSTRA PER VEICOLI ELETTRICI

È stato sviluppato un ulteriore algoritmo, modificando l’algoritmo di Bellman-Ford, poichè, proprio per il suo diverso funzionamento, avrebbe permesso in alcuni casi, di trovare soluzioni alternative laddove l’algoritmo di Dijkstra per veicoli elettrici avrebbe invece fallito. Si è voluto quindi andare a valutare, prendendo in considerazione anche la differenza tra il tempo di esecu-zione di un algoritmo rispetto all’altro, quanto sarebbe andato a perdere quest’ultimo rispetto all’algoritmo di Bellman-Ford per veicoli elettrici.

4.1 Pseudocodice

INITIALIZE-SINGLE-SOURCE(G, s) ; S= ∅; Q= V [G]; while Q≠ ∅ do u= EXTRACT-MIN (Q); S= S ∪ {u};

for each vertex v∈ Adj [u] do

RELAX-EV(u, v, w, c, maxBatt, anxV alue); end

end

(37)

if a[u] + c(u, v) > maxBatt ∗ anxV alue then if d[v] < d [u] + w(u, v) then

d[v] = d [u] + w(u, v);

if a[u] + c(u, v) > maxBatt then a[v] = maxBatt else a[v] = a [u] + c(u, v); end π[v] = u; end end Algorithm 5:RELAX-EV(u,v,w,c,maxBatt,anxValue)

4.1.1 Vincolo di batteria

La presenza della batteria, anche se considerata come un vincolo, mantiene ad ogni modo un ruolo estremamente importante nel nostro algoritmo in quanto tramite il Regenerative Bra-king System, in base alla pendenza dell’arco percorso essa si consuma o viene ricaricata di un valore definito dalla funzione di consumo. Si è per questo dovuto inserire un limite superiore oltre il quale una batteria non può essere caricata e un limite inferiore oltre il quale la batteria non può essere consumata. Questo limite inferiore che prende il valore di  al caso limite ma che può essere anche incrementato tramite l’anxiety value, è quello che nell’algoritmo non permette di rilassare il peso di cammino minimo di un nodo se non si è in grado di raggiungere quel nodo con la batteria a disposizione. Questo vincolo di batteria non permette all’algorit-mo di proseguire se si è terminata la carica disponibile e fa restituire il messaggio di nodo non raggiungibile.

4.1.2 Ricarica

La ricarica del veicolo pu`o essere effettuata in due modi di cui il primo `e tramite un nodo torret-ta. Questo tipo di ricarica prevede un’iniziativa da parte del conducente che deve interrompere

(38)

la marcia e ricaricare la batteria della macchina; pu`o essere effettuato sia nell’abitazione del pro-prietario del veicolo tramite una presa di corrente o una torretta privata, sia lungo il percorso attraverso una delle torrette di ricarica facenti parte della rete infrastrutturale di elettrificazio-ne. Come vedremo nel capitolo dedicato al sottografo delle torrette, questa torretta di ricarica verr`a suggerita dall’algoritmo nel momento in cui si renda necessaria una sosta per completare il percorso.

Il secondo metodo di ricarica non prevede alcun intervento da parte del conducente in quanto viene effettuato tramite il Regenerative Braking System. Questa possibilit`a di ricaricare la batteria del veicolo durante la marcia viene catturata dall’algoritmo e il valore di batteria residua viene aggiornato ogni qualvolta si seleziona il cammino minimo per un determinato nodo, mantenendo in questo modo non soltanto i valori dei tempi di percorrenza sui cammini minimi, ma anche i valori di batteria consumata.

4.1.3 Anxiety value

La batteria disponibile nei veicoli elettrici non è mai quella dichiarata ma si mantiene un certo range, solitamente il %, come margine di sicurezza per il corretto funzionamento della batte-ria; a esempio, nel caso della Nissan LEAF, la batteria dichiarata è da Kw ma ne sono resi disponibili per l’utilizzo soltantoo Kw. Questi Kw di potenza non vengono considerati dai sistemi del veicolo ma servono esclusivamente al mantenimento della batteria stessa. Il no-stro algoritmo prende come valore di riferimento di batteria il valore reale a disposizione del conducente ovvero i Kw. Introduce tuttavia un valore in percentuale definito come anxiety value (valore di ansia) questo valore, permette appunto al conducente di non avere la preoc-cupazione di ritrovarsi con la batteria scarica e senza nessuna torretta in prossimità e quindi essere costretto a rivolgersi al soccorso stradale per ricaricare il veicolo. Il funzionamento di questo valore all’interno dell’algoritmo è quello di nascondere una percentuale della batteria. In questo modo il valore minimo di carica oltre il quale il veicolo viene ritenuto impossibilitato a proseguire nella marcia non sarà più  bens`ı un valore v> , v ∈ R. Questo anxiety value può essere modificato a piacimento. Durante la sperimentazione è stato impostato a , quindi è stata utilizzata tutta la batteria a disposizione.

(39)

4.2 Confronto con Bellman-Ford per veicoli elettrici

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à 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 è il cammino minimo per raggiungerlo. Di conseguenza anche se non ho percorso tutti gli archi entranti in quel nodo so già che non mi porterà vantaggio esplorarli e potrò assegnare quel nodo all’insieme dei nodi definitivi e non lo visiterò più. 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é l’algoritmo di Bellman-Ford è 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 è 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é l’algoritmo di Bellman-Ford procede per in modo iterativo fino a che non c’è più 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ò non si verifica sempre, ad esempio sotto le seguenti condizioni, figura 4.3 a pagina 37:

(40)

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é utilizzando l’algoritmo di Dijkstra per veicoli elettrici né 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ù archi di distanza rispetto a quello che impiega tempo minore. Una volta scoperto il percorso che impiega tempo minore, essendo questa la nostra priorità, l’algoritmo non aggiornerà 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à 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 è 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 è scelto di utilizzare l’algoritmo di Dijkstra invece di quello di Bellman-Ford. Per rendere più 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 è deciso, tuttavia, di non inserire questo controllo poichè 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à dei casi, ci trovavamo di fronte a guadagni di batteria irrisori.

(41)

(42)

(43)

(44)

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à di ricaricare presenta, a livello di algoritmo, un ostacolo importante. Ogni qualvolta ci sia il bisogno di ricaricare sarà necessario ricalcolare il percorso che passa per tutte le torrette di ricarica, al fine di trovare la torretta che impone la deviazione più breve dal percorso ideale ovvero quello senza ricariche.

Si è 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à necessario il calcolo di un percorso contenente una o più soste per la ricarica del veicolo, non ci sarà bisogno di ricalcolare tutte le possibili combinazioni di percorsi che includono una o più torrette nel tragitto. Tutte queste combinazioni saranno già precalcolate all’interno del sottografo e sarà quindi sufficiente, una volta certi della neces-sità di ricaricare, entrare nel sottografo delle torrette per trovare il percorso migliore fino alla destinazione.

(45)

(46)

CAPITOLO 5. SOTTOGRAFO DELLE TORRETTE

5.1 Creazione del sottografo

Per creare il sottografo delle torrette è 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 è in grado di contenere anche le informazioni sulla singola torretta, come ad esempio: il numero di postazioni di carica, la velocità, 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à 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 è utilizzato l’algoritmo di Dijkstra per veicoli elettrici nel secondo, ci si è approcciati al problema utilizzando l’algoritmo di Bellman-Ford per veicoli elettrici. Tra i sot-tografi risultanti dai due algoritmi si è 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à visto in precedenza, l’algoritmo di Bellman-Ford per veicoli elettriciimpiega un tempo di esecuzione estremamente più 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 è optato per l’utilizzo dell’algoritmo di Dijkstra per veicoli elettriciper la costruzione dei sottografi delle torrette.

(47)

5.2 Utilizzo del sottografo

L’idea dell’utilizzo di un sottografo delle torrette è quella di poter entrare in un grafo di percorsi ottimi nel momento in cui vi sia la necessità di ricaricare il veicolo. Questa possibilità 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 è molto simile a quello necessario alla creazione del sottografo delle torrette, quindi, in questo caso il vantaggio maggiore è ottenuto se il veicolo necessita di due o più ri-cariche durante il tragitto in quanto sfrutteremmo il vantaggio di aver già 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

(48)

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

(49)

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 sapermette-rebbe costretto a visitare il numero di torrette di ricarica equivalenti al numero di soste necessarie.

Il sottografo è 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 è costruito anche un sottografo delle torrette utilizzando l’originale algoritmo di Dijkstra, in questo modo si è 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 è 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à di ricaricare, con una perdita dell’.%, mentre l’algoritmo di Bellman-Ford per veicoli elettricitalvolta esplorando più 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ò notare che per la quasi totalità dei percorsi le differenze sono minime. In questo studio si è considerata la ricarica come ricarica completa ma ciò non toglie che costruendo il sottografo delle torrette come un multigrafo con più archi parallelli contenenti i percorsi più veloci effettuabili con diversi livelli di batteria si può simulare una ricarica parziale del veicolo.

(50)

CAPITOLO 5. SOTTOGRAFO DELLE TORRETTE

(51)

(52)

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 è rivelato troppo lento nel calcolo del percorso, con alco-meno una ricarica, quando necessaria. Essendo quella di creare un trip-planner per veicoli elettrici una delle pos-sibili applicazioni dell’algoritmo, si è 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à dell’algoritmo ci si è 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 è quindi andati a cercare un approccio diverso al problema che si discostasse dalla ricerca del percorso in assoluto più 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 è stato valutato, trova il percorso più veloce con ricarica controllando le torrette entro un certo range dai nodi del percorso. Si è 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 è quindi innanzitutto calcolato il percorso migliore come se il veicolo avesse autonomia illimitata, si è definito un range entro il quale sarebbe dovuta ricadere

(53)

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)

(54)

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.

6.2 Euristica 2

Il secondo approccio euristico [algoritmo 12 a pagina 50] che è stato valutato, trova il percorso più veloce con ricarica controllando le torrette entro un certo range dai nodi di partenza e di arrivo del percorso. In questo caso si è pensato di alleggerire la fase di aggiunta dei nodi di partenza e di arrivo limitando la scelta ai soli nodi torretta che si trovavano all’interno di un determinato range dai nodi di partenza e di arrivo. Si è quindi inizialmente definito un range entro il quale sarebbe dovuta ricadere la torretta, si sono poi calcolate le distanze tra il nodo di partenza e i suoi nodi vicini fino a trovare il nodo torretta più vicino, lo stesso procedimento si è utilizzato per trovare la torretta più vicina al nodo di arrivo e si sono utilizzati questi due nodi torretta come porta di accesso e porta di uscita al sottografo delle torrette. Questa euristica ha come vantaggio la rapidità di calcolo, in quanto deve collegare solo due nodi al sottografo delle torrette; tra gli svantaggi invece troviamo l’obbligo di passare per quei due nodi torretta, il che significa quindi una deviazione imposta a priori magari non necessaria, considerato il fatto che questa potrebbe rivelarsi molto dispendiosa e allontanare il veicolo dall’arrivo nel caso in cui ci trovassimo in una zona con una bassa densità di torrette e la più vicina fosse nella direzione geografica opposta al punto di destinazione.

6.3 Euristica 3

Il terzo approccio euristico [algoritmo 13 a pagina 52] che è stato valutato, trova il percorso più veloce con ricarica collegando il nodo di partenza con tutte le torrette e il nodo di arrivo alla torretta più vicina. In questo caso si è pensato di alleggerire la fase di aggiunta dei nodi di partenza e di arrivo limitando la scelta ai soli nodi torretta che si trovavano all’interno di

(55)

DIST, BATT, PATH = DIJKSTRA-EV (Graph, nodo, battery , weight, consumo); end

if DIST is None then

DIST, PATH = DIJKSTRA (G, partenza, arrivo, weight=’traveltime’); if DIST is not None then

TorretteCandidate;

for NodoPercorso in PATH do

for NodoTorretta in SubGraph do

if Distanza(NodoPercorso, NodoTorretta)< offset then TorretteCandidate.append(NodoTorretta);

end end end

AGGIUNGI-SOURCE-EURISTICA (tempGsub D, G, partenza, battery, ToretteCandidate);

AGGIUNGI-TARGET-EURISTICA (tempGsub D, G, partenza, arrivo, battery, ToretteCandidate);

end else

(56)

TorretteCandidateStart; TorretteCandidateEnd;

if Distanza(partenza, NodoTorretta)< offset s then TorretteCandidateStart.append(NodoTorretta); end

end

if Distanza(arrivo, NodoTorretta)< offset e then TorretteCandidateEnd.append(NodoTorretta); end

end

AGGIUNGI-SOURCE-EURISTICA (tempGsub D, G, partenza, battery, ToretteCandidateStart);

AGGIUNGI-TARGET-EURISTICA (tempGsub D, G, partenza, arrivo, battery, ToretteCandidateEnd);

end else

(57)

un determinato range dai nodi di arrivo, collegando comunque il nodo di partenza a tutti i nodi torretta e garantendo in questo modo una più ampia scelta di ingresso nel sottografo delle torrette, mantenendo quasi lo stesso tempo di esecuzione, in quanto nell’euristica 2 si tratta di una esecuzione dell’algoritmo DIJKSTRA-EV con nodo di partenza e nodo di arrivo mentre nell’euristica 3 si tratta di una esecuzione dell’algoritmo DIJKSTRA-EV con nodo di partenza ma senza nodo di arrivo, ovvero su tutto il grafo. Questa euristica ha come vantaggio quasi la stessa rapidità di calcolo dell’euristica 2 ma una maggiore accuratezza in quanto non si limita a collegare il punto di partenza con il nodo torretta più vicino ma lo collega a tutti i nodi torretta presenti nel sottografo. Soffre degli stessi svantaggi dell’euristica 2 per quanto riguarda il nodo di arrivo: potrebbe anch’esso, in alcuni casi, portare il veicolo, almeno inizialmente, su un percorso che lo allontanerebbe dal punto di arrivo.

6.4 Scelta del range

Negli approcci euristici proposti si è definito un range arbitrario, per dare la possibilità all’u-tente di poter decidere quanto deviare dal percorso ottimale o quanto allontanarsi dai punti predefiniti. Si è però valutata anche l’opzione in cui l’utente non sia in grado o non voglia de-cidere di quanto allontanarsi dal cammino ottimo ma voglia lasciare all’algoritmo questa scelta. La scelta arbitraria del range includeva tutte le torrette in quel raggio mentre con questa opzio-ne se opzio-ne seleziona solo una. La scelta del range può essere operata sia tramite una serie di prove che vanno a individuare la torretta più vicina al nodo del percorso, sia attraverso l’utilizzo di un modello KNN. Il problema dell’approccio iterativo alla ricerca della torretta più vicina è che ci si potrebbe trovare di fronte ad alcune situazioni in cui la ricerca della torretta più vicina impieghi tempi molto lunghi, questo perché durante il tragitto ci si allontana da luoghi abitati e quindi da luoghi ricchi di punti di ricarica, rallentando notevolmente l’algoritmo.

L’approccio KNN, al contrario, velocizza notevolmente questa scelta. Si è quindi utilizzato un classificatore KNN che tramite la distanza euclidea riesce a trovare il nodo torretta più vicino in tempi molto rapidi. Il modello è stato addestrato sul sottografo delle torrette e utilizza la distanza euclidea per trovare la torretta più vicina al nodo in questione.

(58)

TorretteCandidateEnd;

if Distanza(arrivo, NodoTorretta)< offset e then TorretteCandidateEnd.append(NodoTorretta); end

end

AGGIUNGI-SOURCE (tempGsub D, G, partenza, battery);

AGGIUNGI-TARGET-EURISTICA (tempGsub D, G, partenza, arrivo, battery, ToretteCandidateEnd);

end else

(59)

ESPERIMENTI

Ottenuto l’algoritmo con ricarica e le euristiche si è potuto dare inizio alla fase di sperimenta-zione e valutasperimenta-zione dell’euristica migliore. Si sono effettuati diversi test partendo da dati reali. I dati a disposizione riguardavano dei tragitti reali da un punto di partenza ad un punto di arrivo descritti da coordinate geografiche e limitati alla sola Regione Toscana. Questi dati sono stati resi anonimi, estraendo il nodo più vicino ai punti reali di partenza e di arrivo e utilizzando questi nodi come punti di partenza e di arrivo del tragitto. Da questi percorsi se ne è estratto un campione casuale formato da  coppie partenza arrivo e si è calcolato il percorso migliore applicando l’algoritmo LONG-SEARCH e i tre approcci euristici. Ci si è resi subito conto che la quantità di batteria massima permetteva il raggiungimento di quasi tutti i nodi torretta. Si sono allora effettuate delle ulteriori simulazioni per andare a verificare quale fosse la percen-tuale di percorsi che necessitavano di almeno una sosta in rapporto alla percenpercen-tuale di batteria con cui si faceva partire il veicolo. La distribuzione di questi valori è apprezzabile nel grafico in figura 7.1 nella pagina seguente. Come possiamo vedere nel grafico e come ci aspettavamo, maggiore è la quantità di batteria a disposizione al momento della partenza e minore sarà la necessità di effettuare una sosta per ricaricarla. Per ottenere la distribuzione delle ricariche in base alla batteria di partenza, si sono effettuate . simulazioni sullo stesso campione di per-corsi, per ogni livello di batteria e si sono andati a contare il numero di percorsi in cui il veicolo necessitava di ricaricare. Si è quindi deciso di ridurre la quantità di batteria alla partenza, in questo modo si è cercato di simulare un veicolo che si trovasse in situazione di scarsa batteria e

(60)

CAPITOLO 7. ESPERIMENTI

(61)

Figura 7.2: Scatter plot consumo batteria su tempo di percorrenza

un’autonomia di circa −  minuti di percorrenza prima di esaurire la carica. Da un’analisi degli archi del grafo che è stato costruito si è estrapolato il consumo medio per unità di tempo che è pari a circa .Kw per ora di percorrenza, questo dato è stato stimato effettuando una media del consumo per ogni arco del grafo rispetto al tempo che si impiega a percorrerlo. Si è inoltre effettuata una rappresentazione, tramite scatter plot, figura 7.2 dei consumi di batteria rispetto al tempo di percorrenza degli archi dove si può notare come il consumo di batteria dipenda dai minuti di movimento del veicolo ma non in modo perfettamente lineare. Una ul-teriore rappresentazione, sempre tramite scatter plot, figura 7.3 nella pagina seguente, è stata fatta per mostrare la correlazione tra il consumo di batteria e la lunghezza dell’arco, nuova-mente si può notare come il consumo di batteria dipenda dalla lunghezza dell’arco sempre in modo non perfettamente lineare, questo dipende dalle caratteristiche della strada, ovvero la pendenza e la velocità che influenzano il consumo, portandolo alle volte a essere negativo.

Nella figura 7.4 a pagina 57 vediamo una simulazione del percorso di un veicolo elettrico con a disposizione Kw di batteria su uno stesso tragitto effettuato da un veicolo alimentato a combustibile. Possiamo apprezzare come l’algoritmo devia dal percorso ottimo per effettuare

(62)

CAPITOLO 7. ESPERIMENTI

Figura 7.3: Scatter plot consumo batteria su lunghezza arco

to di arrivo, in blu il percorso ottimo, quello calcolato come se il veicolo non fosse elettrico e quindi avesse autonomia infinita, in rosso la deviazione da questo percorso ottimo e in giallo la torretta di ricarica e quindi il punto in cui viene effettuata la sosta. Successivamente ci si è concentrati sul confronto tra i tempi di esecuzione degli algoritmi. Si sono effettuate del-le simulazioni sullo stesso campione di tragitti per ottenere i tempi di esecuzione dei diversi algoritmi. Nel primo caso, come possiamo vedere in figura 7.5 a pagina 58 sono stati confron-tati l’algoritmo LONG-SEARCH con le tre euristiche sia nella versione con offset predefinito che nella versione Knn. Dallo scatter plot possiamo vedere come l’algoritmo LONG-SEARCH rappresentato dai triangoli rossi è il più lento, impiegando quasi tre ore per calcolare cento percorsi. Tra gli approcci euristici possiamo vedere come l’euristica 2 con offset predefinito, rappresentata dal simbolo+, sia veloce quanto le euristiche con il Knn, andando però a vedere il numero di percorsi trovati ci si accorge che a differenza degli altri algoritmi questa euristica per ben due volte non trova nessun percorso. Le stesse conclusioni le possiamo trarre anche nello scatter plot, un po’ più nel dettaglio, in figura 7.6 a pagina 58. Si è poi andati a vedere nello specifico un confronto tra le tre euristiche più veloci ovvero le Knn, anche in questo caso le simulazioni sono state eseguite su un campione di  tragitti. Come possiamo apprezzare

(63)