A Route Planning algorithm for optimizing the fuel costs

At a time when the variability of fuel prices has significantly increased, it is important to study and develop something that allows drivers to save money on these resources. General route planning algorithms are mainly based on minimizing the length or the travelling time of a route, although fuel consumption and cost are also two important criteria to consider. This thesis deals with the study of an algorithm to find the shortest route between two points on the Italian surface, with the goal of minimizing costs by indicating at which fuel stations to stop for refuelling. In addition, this study also involves the development of a server-application to run the algorithm given the starting and destination points together with the vehicle characteristics (such as the fuel type, the starting fuel level, the average fuel consumption and the maximum fuel tank capacity), and an API Server that acts as an interface between the server-application and future client-applications. The geographical data are totally managed off-line, and they are provided by OpenStreetMap (OSM). Fuel prices are retrieved from the database of the Italian Ministry of Economic Development and all applications are developed in Python. The proposed approach consists of firstly representing the road networks with graphs, then computing the shortest route between the two points (exploiting the A* algorithm) and finally choosing the best refuelling stops, along the route, using a local optimization algorithm. The algorithm is made of a set of well-defined parameters, and it has been simulated with several routes, defined by random starting and destination points, and several fuel types. In addition to providing the route, its cost and the refuelling stops with the related information, results also deal with the search for the optimal parameters of the algorithm. Results led to the creation of a look-up table, containing the optimal parameters, to be queried according to the user input parameters.

Pianificazione di percorsi per l'ottimizzazione del costo del carburante. In un periodo in cui la variabilità dei prezzi del carburante è aumentata significativamente, è importante studiare e sviluppare qualcosa che consenta ai guidatori di risparmiare denaro su queste risorse. Gli algoritmi classici di pianificazione dei percorsi si basano sulla minimizzazione della lunghezza o tempo di percorrenza di un percorso, sebbene il consumo di carburante e il prezzo siano anche due importanti criteri da considerare. Questa tesi si occupa dello studio di un algoritmo per trovare il percorso più breve tra due punti sul territorio italiano, con l'obiettivo di minimizzare i costi indicando in quali stazioni fare rifornimento. Inoltre, lo studio è incentrato anche sullo sviluppo di un'applicazione server per lanciare l'algoritmo dati i punti di partenza e destinazione insieme alle caratteristiche del veicolo (come il tipo di carburante, il livello di carburante di partenza, il consumo medio di carburante e la capacità massima del serbatoio), e un server API che fa da interfaccia tra l'applicazione server e le future applicazioni client. I dati geografici vengono totalmente gestiti offline e sono forniti da OpenStreetMap (OSM). I prezzi del carburante vengono recuperati dal database del Ministero dello Sviluppo Economico Italiano e tutte le applicazioni sono sviluppate in Python. L'approccio proposto consiste nel rappresentare dapprima le reti stradali con dei grafi, dopo calcolare il percorso più breve (usando l'algoritmo A*) e infine trovare le stazioni in cui rifornirsi, lungo il percorso, usando un algoritmo di ottimizzazione locale. L'algoritmo è composto da una serie di parametri ed è stato simulato con diversi percorsi, definiti da punti di partenza e destinazione casuali, e diversi tipi di carburante. Oltre a fornire informazioni sul percorso, il suo costo e le stazioni in cui fermarsi per il rifornimento, i risultati si occupano anche della ricerca dei parametri ottimali da utilizzare nell'algoritmo. Le analisi dei risultati hanno portato alla creazione di una tabella di look-up, contenente i parametri ottimali, che va interrogata in base ai parametri di input inseriti dall'utente.