Fast computation of travel distance approximations through overlay graphs

The computation of routes in road networks has always been essential for human life, one of the primary factors underlying fundamental social practices such as trade and transport. New techniques have always been investigated to calculate road routes as quickly and efficiently as possible. Edsger Dijkstra presented the historical approach to solving this problem in 1959, in which he devised one of the world's best-known algorithms, which took his name. Dijkstra's algorithm can compute optimal paths in road graphs. However, the increase in complexity that road networks have undergone in recent decades, together with the advent of the digital age, has made Dijkstra's algorithm, due to its complexity of execution, not suited to modern society's needs. This resulted in a lot of effort dedicated to research ever-faster algorithms for road distances computation during the last years. This research has highlighted the importance of performing pre-computations to collect information that can be used to reduce the complexity of road graphs. Another significant result of these researches is the heuristics, which consists of abandoning the result's optimality and prioritising execution speed. Despite the advent of new and more efficient approaches, the continuous improvement of road routes' computation remains one of the most significant challenges that man still faces. In this area, Bluerock Logistics operates to resolve this challenging problem and all the operational research problems deriving from it. This work aims to contribute to a new approach that can approximate extensive road routes' distance very quickly. The rapidity of computation of distances overshadows the optimality of the result. The proposed method combines the pre-computation of information with a heuristic to create a suitable data structure that can be used to approximate distances of road routes. This data structure is called overlay graph. The execution speed-up is obtained through a constant complexity search for the pre-computed paths that best reflects the searched route, combined with a refinement technique, to adapt the pre-computed distance to the real one. The results show that this method can estimate distances with a logarithmic complexity with respect to the size of the pre-computed data structure regardless of the size of the path. It is also possible to estimate large distances by obtaining shallow approximation errors.

La computazione di percorsi in reti stradali è sempre stato un problema di vitale importanza per la vita dell'uomo, essendo uno dei fattori primari alla base di importantissime pratiche sociali come il commercio ed il trasporto. Da sempre vengono ricercate nuove tecniche per calcolare percorsi stradali nella maniera più rapida ed efficiente possibile. L'approccio storico per risolvere questo problema fu presentato da Edsger Dijkstra nel 1959, anno in cui ideò uno degli algoritmi più conosciuti al mondo, il quale prese il suo nome. Nonostante l'algoritmo di Dijkstra possa essere usato per computare percosi ottimali in grafi stradali, l'aumento di complessità che le reti stradali hanno subito negli ultimi decenni insieme all'avvento dell'era digitale hanno reso l'algoritmo di Dijkstra, per via della sua complessità d'esecuzione, non adatto ai bisogni della società moderna. Per questo motivo, negli ultimi anni moltissimi sforzi sono stati dedicati alla ricerca di algoritmi per la computazione di distanze stradali sempre più rapidi. Questa ricerca ha portato alla luce l'importanza di effettuare delle precomputazioni con lo scopo di estrapolare informazioni che possano essere utilizzate per ridurre la complessità dei grafi stradali. Un altro frutto di queste ricerche è stata l'euristica, che consiste nell'abbandono dell'ottimalità del risultato dando priorità alla velocità di esecuzione. Nonostante l'avvento di nuovi approcci sempre più efficienti, il miglioramento continuo della computazione di percorsi stradali rimane una delle più grandi sfide che l'uomo tuttora affronta, ed è proprio in questo ambito che Bluerock Logistics opera, con lo scopo di innovare sempre più la risoluzione di questo prestigioso problema e di tutti i problemi di ricerca operativa che ne derivano. Lo scopo di questo lavoro è quello di contribuire ad un nuovo approccio che sia in grado di approssimare la distanza di grandi percorsi stradali in maniera molto rapida. L'ottimalità del risultato è messa in secondo piano rispetto alla rapità di computazione delle distanze. Il metodo proposto combina la pre-computazione di informazioni con l'euristica, in modo da creare un'apposita struttura dati che può essere utilizzata per approssimare distanze di percorsi stradali. Questa struttura dati la chiameremo overlay graph. La velocità di calcolo è ottenuta grazie ad una ricerca di complessità costante dei dati precomputati che meglio rispecchiano il percorso cercato, combinata con una tecnica di raffinamento, con l'obiettivo di adattare la distanza precomputata a quella è la distanza reale. I risultati mostrano che questo metodo è in grado di stimare distanze con un complessità logaritmica rispetto alla dimensione della struttura dati pre-computata a prescindere dalla dimensione del percorso. É inoltre possibile stimare grandi distanze ottenendo errori di approssimazioni molto bassi.