Algoritmi di pathfinding (routing, pianificazione del viaggio, ...) su grafici con limiti di tempo

Question

Ho un database di bus/treno/... fermate e gli orari di arrivo/partenza in ogni data e così via. Sto cercando un modo per effettuare una ricerca per il viaggio più veloce (più breve/più economico/meno transizioni) tra due località. Mi piacerebbe avere sedi arbitrarie in futuro, usando i dati di OpenStreetMap per fare passi tra le fermate e dalle fermate all'inizio/fine, tuttavia per il momento voglio solo trovare il percorso tra due fermate nel database.

Il problema è che non riesco a trovare molte informazioni su questo argomento, ad esempio this Wikipedia page ha un sacco di testo con assolutamente nessuna informazione utile in esso.

Quello che ho trovato è il formato GTFS, utilizzato in Google Transit. Mentre la mia città non fornisce un feed di dati pubblico (nemmeno privato), ho già tutte le informazioni importanti che il GTFS contiene e fare una trasformazione sarebbe banale.

Esiste un software basato su GTFS, ad esempio OpenTripPlanner che può anche eseguire il routing di pedoni/auto/bici utilizzando OpenStreetMap.

Tuttavia, il codice di instradamento non è ben documentato (almeno da quello che ho trovato) e non ho bisogno del tutto.

Tutto quello che sto cercando è una buona panoramica degli algoritmi che potrei usare, le loro prestazioni, forse qualche pseudocodice.

Quindi, la domanda è, dato un elenco di fermate, percorsi e orari di arrivo/partenza/viaggio, come posso trovare facilmente il percorso più veloce dalla fermata A alla fermata B?

Answer 1

1. Modella il tuo problema come graph. Ogni stazione sarà un vertice e ogni bus/treno sarà un Edge.
2. creare una funzione w:Edges->R, che indica il tempo/denaro/... per ciascun lato.
3. ora, si ha un tipico problema di percorso minimo, che può essere risolto da Dijkstra algorithm, che trova il percorso minimo a tutti i vertici da una determinata sorgente.

(*) Per i 'meno transizioni', il peso è in realtà 1 per ogni lato, così si può anche ottimizzare questo eseguendo un BFS o anche bi-directional BFS invece di Dijkstra, come ho spiegato in questo post [E ' è spiegato per la distanza sociale, ma in realtà è lo stesso algoritmo].

---

EDIT
come una modifica alla natura non statica del grafico [per la temporizzazione] ti ha menzionato su commenti [per il prezzo e il numero di transizioni, quello che ho detto sopra si applica ancora, dal momento che questi i grafici sono statici], è possibile utilizzare uno distance vector routing algorithm, che in realtà significava funzionare per i grafici dinamici ed è una variazione distribuita di Bellman Ford algorithm.
L'idea algoritmo:

• periodicamente, ogni vertice invia il suo "distanze vettore" per i suoi vicini [il vettore indica quanto 'costi' per viaggiare dal vertice di invio, gli uni agli altri vertici.
• I suoi vicini cercano di aggiornare le loro tabelle di routing [attraverso il quale è meglio spostarsi verso ciascuna destinazione]
• per il tuo caso, ogni nodo sa qual è il modo più veloce per raggiungere i suoi vicini, [tempo di viaggio + wait time] e [il vertice/stazione] aggiunge questo numero a ciascun antipasto nel vettore distanza, in modo da sapere come e quanto tempo ci vorrà per raggiungere la destinazione. Quando un autobus parte, il tempo di viaggio dovrebbe essere ricalcolato a tutti i nodi [da questa fonte], e il nuovo vettore deve essere inviato ai suoi vicini