Algoritmo di trasporto pubblico bus

Question

Sto lavorando a un'applicazione C# offline in grado di trovare percorsi di autobus. Posso estrarre i dati orari/bus/percorso. Sto cercando la soluzione più semplice che funzionerà con i dati di base.

Quale algoritmo può essere utilizzato per trovare un percorso dalla fermata "A" alla fermata "B"? Esiste una soluzione open-source pronta per C#/Java? Il formato GTFS di Google per il database è buono per una soluzione semplice? http://code.google.com/transit/spec/transit_feed_specification.html

Grazie per qualsiasi aiuto. Sono bloccato con questo. Non so da dove cominciare - come conservare i dati e come trovare percorsi. So di Dijkstra/A * ma li ho usati solo su grafici che non dipendevano dal tempo ...

Answer 1

Concettualmente, si prende lo stesso algoritmo di base per valutare la distanza tra A e B, ma invece di distanza, si dovrebbe essere la valutazione del tempo. Dijkstra può fare entrambe le cose, se gli dai il giusto input.

Sei abituato a vedere una mappa come misura della distanza. Tuttavia, la stessa mappa può essere anche una misura del tempo; tutto ciò che serve è aggiungere dati sulla velocità media e il tempo necessario per coprire una determinata distanza di una determinata strada si scuoterà da solo. Puoi anche visualizzare la mappa in termini di tempo; percorsi che richiedono più tempo saranno più lunghi. Dijkstra non si cura di cosa stia valutando, davvero; si preoccupa solo di trovare la rotta continua con il numero più basso e se tale numero rappresenta la lunghezza o il tempo è irrilevante.

Per incorporare la velocità, gli algoritmi ingenui utilizzano semplicemente il limite di velocità diurno e presuppongono che non si debba mai fermarsi mentre si va da A a B; algoritmi più avanzati possono incorporare informazioni sull'ora del giorno e modelli di traffico (che influiscono sulla velocità media su quella strada in quel momento), e se una strada è una superstrada o una strada di superficie (e quindi fare ipotesi plausibili sul tempo trascorso fermato ad un incrocio). Ciò che si utilizza dipende da ciò che si ha a disposizione, ma una dimensione temporale del giorno a 4- o 5 livelli dovrebbe essere adeguata a tutti, tranne alle applicazioni più critiche in termini di tempo. Per ogni direzione di ogni strada della tua mappa, hai bisogno della velocità media durante la corsa mattutina, diurna, serale e notturna, possibilmente con i numeri dell'ora di pranzo. Una volta ottenuto ciò, si tratta di un cambiamento relativamente basilare di un algoritmo di Dijkstra da passare in un momento della giornata e fare valutare gli itinerari in base al tempo.

Answer 2

Se si è interessati alle informazioni sul tempo, quindi perché non etichettare i valori della distanza sui bordi del grafico usando le informazioni sul tempo invece della loro distanza fisica l'una dall'altra. In questo modo cercherai il percorso più veloce, invece del percorso più breve. È quindi possibile utilizzare Dijkstra/A * per calcolare il risultato.

Sono un po 'poco chiaro su cosa intendi per tempo dipendente. Se si intende che è necessario rispondere alle domande del modulo 'va da x a y prima delle 10:00', quindi è possibile calcolare quali percorsi di bus arrivano prima delle 10:00, sembra un semplice filtro sui dati. Quindi applicare Dijkstra/A * ai dati.

Answer 3

Il problema su cui si sta lavorando non è un compito banale. Tanto, questo ha un nome: il problema di programmazione non lineare di interi misti (MINLP). Nelle parole di un autore (Deb 1998):

"Quando formulato matematicamente, il problema di pianificazione tempo diventa un misto intero non lineare programmazione problema (MINLP) avere un gran numero di risorse e servizio- relativi vincoli .Anche se i tentativi sono stati fatti in passato per trovare una schema ottimale di un modello semplificato utilizzando ottimizzazione classica tecniche (rilegatore & DCsilets, 1992; Kikuchi & Parameswaran, 1993), si osserva che si tratta di un estremamente compito difficile anche per una piccola rete di transito . La difficoltà deriva principalmente a causa del gran numero di variabili e vincoli, natura discreta di variabili, e nonlinearità coinvolte nella funzione obiettivo ei vincoli."

In carta di Deb si propone una genetica l'algoritmo

L'altra opzione sarebbe quella di utilizzare la simulazione. Solo per lanciare qualcosa là fuori puoi provare subito-- scegliere migliaia di percorsi casuali che partono dalla tua origine e pescare quelli che funzionano abbastanza bene per ottenere alla destinazione.

Immagine dell'algoritmo in questo modo: Stai cercando di trovare il percorso più veloce dalla fermata A per interrompere B, a partire da una certa ora. Assumi 1.000 persone e armali con un quarto da lanciare. Digli di lanciare la moneta ogni volta che hanno la possibilità di salire o scendere da un autobus. Testa, scendere (o andare avanti, se già spento). Tails, rimani su (o continua ad aspettare, se spento). Ognuno di loro ha una scheda per annotare le scelte che fanno mentre vanno. Vai al punto B e aspetta che il primo tizio si presenti e prenda la sua carta.

Answer 4

Prova questo come modello di dati.

Bus 1 va a fermate A, B e C. Bus 2 va a fermate B, D ed E.

avrei memorizzare un nodo univoco sulla base sia bus e stop, con distanze nodi essendo basato sulla tempo. Avremmo il nodo A1, B1, C1, B2, D2 ed E2. Nel caso speciale dei trasferimenti, applicare l'attesa per il bus successivo come distanza tra i nodi. Ad esempio, se il Bus 1 arriva allo stop B 30 minuti prima del Bus 2, il tempo di percorrenza da B1 a B2 è di 30 minuti.

Dovresti essere in grado di applicare l'algoritmo di Dijkstra.

Answer 5

leggere questo:

Multimodale percorso di pianificazione. tesi di Master, Università di Karlsruhe (TH), Facoltà di scienze informatiche, 2009. on-line disponibile all'indirizzo http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

la sezione di routing ferrovia vale anche per il routing del bus.

In sintesi: l'approccio ingenuo di espandere lo spazio e il tempo in un singolo grafico non funziona per reti di grandi dimensioni. Ci sono soluzioni più intelligenti.

Answer 6

Volevo solo condividere il mio approccio finale su questo problema. Questo faceva parte di un progetto universitario, quindi potrebbe non essere completamente adatto all'uso nel mondo reale. Doveva essere ragionevolmente veloce per essere eseguito su un dispositivo Windows Mobile.

Ho finito per utilizzare 4 tabelle (SQLite). Una tabella mantiene la lista degli autobus, la seconda mantiene una lista di stazioni. Un'altra tabella mantiene le combinazioni: quale bus si ferma su una stazione specifica e da dove va questa stazione e per quanto tempo (minuti) impiega. Tutte le combinazioni devono essere memorizzate. E l'ultimo tavolo è un semplice orario.Per ogni stazione elenca ogni bus che si ferma lì e il tempo (ho memorizzato il tempo come valore intero - 14:34 è 1434, per renderlo più veloce per il confronto).

Ho usato un algoritmo di ricerca bidirezionale di larghezza prima. Le stazioni vicine (direttamente accessibili) vengono recuperate per la stazione di partenza e la stazione di destinazione. C'è un percorso dalla stazione A alla stazione X se questi due "grafici" si sovrappongono su una stazione. Ad esempio, dalla stazione A è possibile raggiungere le stazioni B, C, D, E (utilizzando bus specifici). E dalla stazione di destinazione X puoi arrivare direttamente a N, C, Z. Questi due grafici si sovrappongono alla stazione C. Quindi esiste un percorso A -> C -> X. Se non vengono trovati percorsi in questa prima iterazione, l'algoritmo continua e distribuisce nuovamente i grafici (BFS).

Il tempo non viene preso in considerazione nel primo passaggio: ciò lo rende abbastanza veloce. Viene visualizzato solo un elenco di percorsi possibili con un elenco di bus che è necessario utilizzare per percorrere questi percorsi. I tempi vengono valutati nell'ultimo passaggio, si passa attraverso l'elenco dei possibili percorsi e si controlla se il bus viaggia nel tempo specifico (aumentando il tempo ogni fermata).

In una piccola città, con 250 stazioni e oltre 100 autobus/ferrovie, questo approccio consente di eseguire fino a 3 modifiche (in cui è necessario modificare gli autobus durante il viaggio). Ci vogliono solo pochi secondi per calcolare. Ma ho dovuto caricare l'intero database in memoria (Dizionario) per velocizzare le query, che richiedevano troppo tempo.

Non credo che ciò funzionerebbe per una grande rete. Ma funziona per un trasporto pubblico di una singola città di piccole-medie dimensioni.

Answer 7

C'è una lunga lista di pubblicazioni (30+) su algoritmi di routing di trasporto pubblico che è stato compilato nel corso del tempo dai contributori alla open-source (Java) OpenTripPlanner project qui:

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

OpenTripPlanner è motore di routing multi-modale che comprende anche moto e camminare - dal link qui sopra:

Questa è una lista di articoli, tesi di laurea, e libri che hanno ispirato e informato sia l'esistente OTP motore di routing di un e alcuni esperimenti in corso. Attualmente, OpenTripPlanner utilizza un singolo grafico temporale (al contrario del tempo espanso) che contiene sia le reti stradali che quelle di transito. I viaggi di sola andata e solo in bicicletta sono generalmente pianificati usando l'algoritmo A * con gerarchie euristiche o di contrazione dell'euclideo. Walk + Transit o Bike + I viaggi di transito sono pianificati utilizzando una variante dell'algoritmo MOA * con predominanza epsilon per la potatura del percorso e l'euristica Tung-Chew (un grafico che fornisce un limite inferiore sul peso aggregato) per l'ordinamento delle code.

La bibliografia di routing include sopra i riferimenti per le seguenti categorie di algoritmi e relativi lavori:

• Tecniche percorso di ricerca Speedup
• multi-obiettivo Pareto Percorso Minimo
• Routing risorse limitate
• Schemi di contrazione e trasferimento
• Instradamento basato su orario
• ALT e Metric incastri
• calibrazione e dettagli implementativi
• Post-Dijkstra Transito pubblico Routing

Se si scopre qualcosa di nuovo che non è sulla lista, non esitate a aggiungerlo al wiki!

quanto riguarda gli altri mezzi di trasporto pubblico librerie di routing open-source - c'è anche il progetto RRRR da bliksem Labs:

https://github.com/bliksemlabs/rrrr

dal link qui sopra:

RRRR (di solito pronunciato R4) è un'implementazione in linguaggio C dell'algoritmo di routing pubblico RAPTOR. È il componente principale del routing del pianificatore di viaggi di Bliksem e del sistema di informazioni per i passeggeri. L'obiettivo di questo progetto è generare serie di itinerari pareto-ottimali su vaste aree geografiche (ad esempio BeNeLux o tutta Europa), migliorando il consumo di risorse e la complessità delle alternative più flessibili esistenti. Il sistema dovrebbe alla fine supportare gli aggiornamenti in tempo reale di veicoli/viaggio riflessi nei piani di viaggio ed essere in grado di funzionare direttamente su un dispositivo mobile senza connessione a Internet.

Sia OpenTripPlanner che RRRR utilizzano dati GTFS.