Adaptive car navigation system for smart cities

Car navigation system technologies recently established across the globe as an imperative utility for modern navigation on road networks. The rising wave of self-driving cars along with an increasing demand for real-time traffic data is expected to generate massive growth in the number of routing requests and processing on large graphs representing the urban network. This trend imposes larger and more powerful computing infrastructures composed of HPC resources. In the context of smart cities, new, dynamic solutions are required in order to deliver high-quality car navigation services, powered by municipal traffic monitoring data, capable of handling such a vast expected demand with reasonable employment of financial resources. In this thesis, an adaptive car navigation system for smart municipalities is presented, proposing a methodology to approach navigation services design along with capacity planning analysis through system modelling. An efficient, configurable C++ library, named ARLib, is introduced, implementing state-of-the-art algorithms addressing the Alternative Route Planning (ARP) problem, a key part of car navigation systems. In this context, ARLib exhibits its flexibility by exposing a variety of parameters to manage the tradeoff between execution time and quality of results. Moreover, since no ultimate solution exists, an auto-tuning process is presented to proactively choose the optimal heuristic for each query, leveraging a predictive model providing recommendations based on request features. This gives the possibility to have the highest quality reachable within the available latency budget. Furthermore, a Queueing Petri Net model of the car navigation system is proposed to study its behavior from performance evaluation perspective in a computer simulation environment. This aspect helps to assess and size the infrastructure for the navigation service deployment through capacity planning analysis. Finally, an empirical evaluation of the presented methodology is reported, by applying the advised approach in a case study on the city of Milan.

I sistemi di navigazione, negli ultimi anni, si sono affermati in tutto il mondo come uno strumento fondamentale per la navigazione moderna sulla rete stradale. Il fenomeno in aumento delle auto a guida autonoma, insieme alla sempre più crescente domanda di aggiornamenti sul traffico in tempo reale, fanno prevedere una crescita imponente del numero di richieste di percorsi e di elaborazioni su enormi grafi che rappresentano le reti stradali cittadine. Questo trend impone la presenza di impianti informatici più grandi e potenti, composti da risorse HPC. Nell'ambito delle Smart City, al fine di fornire servizi di navigazione di qualità, sfruttando i dati cittadini di monitoraggio del traffico, sono necessarie soluzioni nuove e dinamiche, capaci di gestire una tale domanda prevista con un impiego ragionevole di risorse finanziarie. In questo lavoro di tesi, si presenta un sistema di navigazione adattivo per Smart City, proponendo una metodologia per la progettazione di un servizio di navigazione insieme ad un'analisi per il dimensionamento delle risorse attraverso un modello del sistema. Si introduce una libreria C++ efficiente e configurabile, chiamata ARLib, che implementa alcuni algoritmi dallo stato dell'arte per risolvere il problema della Pianificazione di Percorsi Alternativi, una componente chiave dei sistemi di navigazione su strada. In questo contesto, ARLib mostra la sua flessibilità esponendo una serie di parametri per gestire il tradeoff tra tempo di esecuzione e qualità del risultato. Inoltre, poiché non esiste un approccio definitivo al problema, si presenta un processo di auto-tuning per scegliere automaticamente, in maniera proattiva, l'euristica ottimale per ogni query, sfruttando un modello predittivo che fornisce raccomandazioni basate sulle caratteristiche delle richieste. Questo permette di ottenere la massima qualità raggiungibile nel tempo di calcolo a disposizione. In aggiunta, si propone un modello del sistema di navigazione con reti di code e reti di Petri combinate, per studiare il comportamento del servizio dal punto di vista delle performance in un ambiente di simulazione. Ciò permette di valutare e dimensionare l'infrastruttura adeguata ad erogare il servizio di navigazione attraverso capacity planning. In ultimo, si riporta una validazione empirica della metodologia presentata, applicando l'approccio consigliato ad un caso studio sulla città di Milano.