Articolo a cura di Ignacio “Nacho” Correas, Chief Technology Innovation Officer di Skymantics –
Ci sono due compromessi che devono essere attentamente bilanciati: accuratezza vs. prestazioni. È inutile per un motore di routing generare rapidamente percorsi sub-ottimali, ma è altrettanto poco pratico generare percorsi ottimali che richiedono molto tempo per essere elaborati. Il primo punto critico da considerare nel motore di routing è l'algoritmo di routing.
Algoritmi di routing
Skymantics ha sperimentato algoritmi di percorso più breve, in particolare Dijkstra e A* (A-star), in tre modalità: unidirezionale, bidirezionale e con ottimizzazione delle gerarchie di contrazione (CH). Implementare una versione unidirezionale e vanilla di questi algoritmi è abbastanza semplice e ci sono molti tutorial su Internet che aiutano a capire come farlo. Come regola generale, la creazione di algoritmi bidirezionali (in altre parole, il percorso viene calcolato simultaneamente sia dall'origine che dalla destinazione) fornirà il percorso ottimale da 5 a 10 volte più velocemente di unidirezionale, anche se la scelta del nodo di giunzione ottimale (dove il percorso dall'origine incontra il percorso dalla destinazione) ha i suoi problemi. Tuttavia, scegliere tra Dijkstra e A* e tra bidirezionale o con CH non è semplice.
Quando usare A*
In teoria, A* dovrebbe essere un algoritmo più efficiente, poiché richiede meno calcoli: è fondamentalmente un Dijkstra diretto che prende in considerazione solo i nodi del grafico che aiutano a muoversi nella direzione verso la destinazione. Tuttavia, ciò richiede il calcolo della direzione e delle distanze euristiche, che è un'operazione computazionalmente più costosa di un'iterazione di Dijkstra e potrebbe essere controproducente. In generale, per maglie molto dense di strade/strade della stessa gerarchia, A* potrebbe essere una scelta migliore. Per tutto il resto, Dijkstra sarà probabilmente sufficiente.
Quando usare CH
Per percorsi lunghi e interurbani, hai bisogno di un qualche tipo di ottimizzazione come Contraction Hierarchies. Questa ottimizzazione darà priorità ai percorsi con gerarchia più alta e ignorerà le alternative con gerarchia più bassa, riducendo drasticamente i calcoli per trovare il percorso più breve in modo molto efficiente. Ecco un esempio di un percorso di 265 km (165 miglia) che attraversa il Belgio: ci vogliono 35 secondi per calcolare con l'algoritmo bidirezionale Dijkstra, ma solo 0.1 secondi usando l'ottimizzazione Contraction Hierarchies.
Quando usare Dijkstra bidirezionale
Per percorsi urbani più brevi, le Contraction Hierarchies potrebbero determinare un percorso non ottimale, poiché l'algoritmo può fare delle deviazioni se trova un percorso con gerarchia superiore nelle vicinanze. È possibile ridurre questo effetto o addirittura eliminarlo completamente modificando attentamente le gerarchie stradali e consentendo all'algoritmo alcune iterazioni aggiuntive. Ma se l'applicazione di routing è solo per un'area urbana specifica, potrebbe essere più semplice utilizzare semplicemente un Dijkstra bidirezionale. Ecco un esempio di un percorso nel centro di Providence, Rhode Island, che dovrebbe essere solo una linea retta, ma che Contraction Hierarchies viene ingannata e fa una deviazione attraverso la vicina strada principale. Il tempo di calcolo per CH è di 1 millisecondo rispetto a 1.5 millisecondi per Dijkstra bidirezionale, dimostrando che c'è margine per iterazioni aggiuntive per evitare questo effetto deviazione.
Gli algoritmi di routing possono garantire accuratezza e migliorare le prestazioni fino a un certo punto. La verità è che instradano attraverso una rete di strade definite in un set di dati di mappa e i risultati dipendono fortemente dall'accuratezza di questi set di dati e dal modo in cui sono stati preelaborati.
Pre-elaborazione dei set di dati
I set di dati e la preelaborazione sono il modo più importante per migliorare l'accuratezza e le prestazioni di un algoritmo di routing. È difficile sottolineare abbastanza questo punto. Cercherò di riassumere gli aspetti principali da tenere in considerazione nei seguenti punti:
- Non tutti i set di dati hanno lo stesso livello di accuratezza. OpenStreetMap è un ottimo esempio; copre praticamente tutto il mondo ed è scaricabile e utilizzabile gratuitamente, ma mancano alcune informazioni importanti come molti limiti di velocità, limiti di altezza/peso o manovre vietate. In alcuni casi, potrebbe persino contenere informazioni false per quanto riguarda la direzionalità delle strade a senso unico o i collegamenti, per citarne un paio. Altre mappe, come QUI, offrono un livello di accuratezza molto migliore, ma hanno un costo. Stranamente, le coordinate stradali non corrispondono al 100% tra diversi set di dati e potresti scoprire che le stesse coordinate sono considerate parte di strade diverse a seconda del set di dati che utilizzi.
- A seconda dell'applicazione del tuo motore di routing, molti segmenti di strada o di strada forniti in un set di dati possono essere uniti insieme in un singolo bordo, a volte riducendo le dimensioni del grafico fino al 90%. Ad esempio, è possibile creare scorciatoie per saltare le intersezioni di gerarchia inferiore, accelerando il calcolo del percorso su lunghe distanze.
- Una parte critica della pre-elaborazione è decidere come classificare la gerarchia dei collegamenti stradali: collegano strade con gerarchia inferiore a superiore? Collegano strade con la stessa gerarchia? Questo è un aspetto particolarmente importante per gli svincoli autostradali, poiché le strade che collegano le autostrade devono avere la gerarchia più alta (per accelerare le gerarchie di contrazione), ma impostare tutti i collegamenti stradali da un'autostrada alla gerarchia più alta rallenterà i calcoli a causa di troppi incroci.
Algoritmi di routing e set di dati e pre-elaborazione sono gli aspetti chiave da considerare nella creazione di un algoritmo di routing accurato e performante. Ma ci sono altri aspetti che possono fare la differenza tra un motore di routing utile e uno inutile.
Le migliori pratiche di programmazione
Darò per scontato che siano in atto buone pratiche di programmazione e che venga scelto un linguaggio di programmazione appropriato per il compito. Ci sono tre punti critici da considerare quando si distribuisce e si gestisce un motore di routing:
- I dati grafici devono risiedere in memoria per ottenere le massime prestazioni. Potrebbero esserci alcune parti in un database, ad esempio dati geografici per aiutare a trovare i nodi più vicini all'origine e alla destinazione, ma l'algoritmo di routing deve funzionare con dati in memoria, altrimenti rischia di avere prestazioni inferiori per mappe leggermente più grandi di un centro cittadino.
- Il motore di routing deve precaricare tutti i dati richiesti e deve utilizzare il threading per attività secondarie che richiedono molto tempo, come il salvataggio del percorso generato sul disco. Altrimenti, questi tempi si sommeranno, riducendo le prestazioni complessive.
- Questo potrebbe sembrare ovvio, ma se il motore di routing deve essere offerto come servizio remoto, la velocità di connessione sarà cruciale. Non ha senso accelerare il calcolo del routing se il collo di bottiglia è nel canale di comunicazione. Latenza e throughput sono essenziali per un servizio API performante.
E questo è fondamentalmente tutto. Costruire un motore di routing può essere un compito entusiasmante, pieno di sfide e divertimento. Anche se il tuo obiettivo non è costruirne uno, ma hai bisogno di usare il routing in modo intensivo, è bene comprenderne gli aspetti chiave. Spero che ti sia divertito a leggere questa serie di articoli tanto quanto mi sono divertito io a scriverli. Salute!
