Approssimare lo shortest-path in una rete stradale con un metodo basato sul Deep Learning

I grafi sono delle strutture dati utilizzate in vari campi della scienza: dall'informatica (con riferimento alle infrastrutture comunicative, le reti di computer e le mappe di siti) alla geografia (in cui i grafi vengono utilizzati per rappresentare reti stradali e di trasporti). La rete stradale, intesa come insieme di linee di circolazione e di punti di interesse, si può matematicamente rappresentare come un grafo, definito come un insieme di nodi (incroci) e delle dirette interazioni fra di loro chiamate archi (strade). Il concetto di distanza tra due nodi in una rete è differente rispetto a quello dei sistemi fisici. Mentre la distanza tra due punti può essere calcolata come distanza euclidea, il path length (la lunghezza del percorso) fra due nodi, invece, si calcola seguendo e sommando i pesi degli archi della rete. Nella teoria dei grafi è frequente la necessità di determinare la distanza fra due nodi. Per reti piccole è un compito semplice, ma per reti di milioni di nodi può essere molto dispendioso in termini di tempo e risorse. Gli algoritmi di shortest-path sono in grado di portare a termine questo compito di ricerca, trovando il percorso con il costo minimo fra due nodi in un grafo. Lo scopo della Tesi è quello di utilizzare un metodo basato sul Deep Learning come alternativa a questi algoritmi per il calcolo dello shortest path all’interno di una rete stradale. Dopo aver recuperato la rete stradale da Open Street Map, il metodo proposto si propone di stimare la distanza fra due incroci (nodi) anziché calcolarla, rendendo più veloce il calcolo e limitando drasticamente l’utilizzo delle risorse computazionali necessarie. Per fare ciò, la rete viene rappresentata tramite un Node Embedding. In tal modo sarà possibile rappresentare ogni incrocio come un vettore di pesi che potrà essere fornito in input ad una Deep Neural Network. Nello specifico, in questa tesi verranno descritti l’architettura utilizzata ed i processi di addestramento della Rete Neurale. Il risultato finale sarà un modello di Deep Learning che restituirà una stima della distanza tra due incroci di una rete stradale.