Connessione mezzi pubblici

[freerafiki]

Connessione mezzi pubblici

[lucatastrophe]

Non so se li avevate già guardati, ma questo è il link per gli orari ACTV.
http://dati.venezia.it/?q=content/actv-general-transit-feed-specification-gtfs
Ho visto che esiste una libreria Python per gestire lo standard GTFS con cui sono organizzati i dati ACTV. è robaccia google ovviamente. La libreria è "transitfeed": https://github.com/google/transitfeed/
Ho cercato di installarla per provarla, ma è per Python 2. Ho visto che esistono delle fork, ma non ho avuto tempo di provare. Magari esistono altre librerie più aggiornate.

[freerafiki]

possiamo ottenere da openstreetmap overpass ecc. le coordinate dei pontili? li abbiamo gia?

[Lychfindel]

Dovrebbero esserci tra i poi sotto "ferry terminal", i percorsi invece dovrebbe essere possibile estrarli perché sono "relation" di openstreetmap (ad es. https://www.openstreetmap.org/relation/3436762#map=14/45.4301/12.3431&layers=N )

[lucatastrophe]

Provo a schematizzare come dovrebbe funzionare:

• ogni fermata di ogni linea costituisce un arco con la fermata precedente. La lunghezza dell'arco è definita in termini di tempo (quindi serve attribuire un flag all'arco in modo che la funzione peso possa riconoscerlo). Inoltre ha anche una fascia oraria perché potrebbe essere che una connessione salti a certi orari.
• ogni fermata di ogni linea viene connessa al nodo più vicino del grafo terrestre. L'arco di connessione (nuovo flag) contiene gli orari a cui passa il vaporetto.
• La funzione peso che rileva la flag dell'accesso alla fermata (quella del punto 2), fa un check dell'ora attuale (o impostata) e calcola il tempo che manca all'orario più vicino. Questo è il peso dell'arco.

[Lychfindel]

Io propongo di avere gli orari di partenza e arrivo direttamente negli archi dei battelli.
Così facendo la lunghezza dell'arco potrebbe essere come tutte le altre una lunghezza vera in metri e la funzione per i pesi (in termine di tempi) calcola semplicemente t_attuale-t_partenza+t_arrivo-t_partenza (ovvero tempo da aspettare+tempo di attraversata).
Inoltre così facendo si eviterebbero problemi nel dover cambiare il battello rimanendo nello stesso imbarcadero.

[lucatastrophe]

L'idea è buona sotto diversi aspetti. La formula in realtà è:

t_partenza-t_attuale+t_arrivo-t_partenza

. che ci dà

t_arrivo - t_attuale.

Che se ci pensate ha molto senso.
Quindi ogni arco dovrebbe contenere tutti gli orari a cui un battello (qualsiasi) passa per la fermata di arrivo. I problemi che vedo sono 2:

• il grafo non è "directed". Andrebbero salvate due liste (di dizionari, per poter memorizzare come key la linea di vaporetto ) di orari di arrivo (una per ogni nodo dell'arco), e andrebbe controllato da dove arrivi con la stessa tecnica usata per i sensi unici del grafo acqueo.
• Basta che l'orario di arrivo sia successivo all'orario attuale per far accettare la soluzione, il che è evidentemente sbagliato.

Il vantaggio dell'approccio proposto sopra è che l'arco di accesso alla linea del vaporetto funziona come gate, le condizioni di accesso vanno verificate una volta sola, dopodiché i tempi di percorrenza sono effettivamente undirected (se sei sulla linea di un battello i tempi sono uguali di andata e ritorno). Abbiamo comunque il problema di prendere l'ora attuale come parametro per accedere al vaporetto, mi riesce difficile immaginare come far tenere conto del tempo impiegato ad arrivare all'arco. Bisognerebbe capire se networkx ha un metodo in cui alla funzione peso passa anche qualche informazione sulla lunghezza del percorso che sta costruendo (secondo me dovrebbe poter esistere, perché da quel che avevo capito di dijkstra lui sceglie quale arco valutare per primo in base al percorso più corto che ha fino ad ora).
Il problema che vedo di questo approccio è che dovendo creare un arco diverso per ogni linea di vaporetto, dobbiamo anche assegnargli delle coordinate leggermente diverse (le coordinate individuano i nodi in modo univoco). Inoltre, non sono comunque sicuro che sul "gate" riusciremo a decidere che verso del battello prendere (io penso di sì, ma non ce l'ho in mente in modo chiaro)

[freerafiki]

anche a me piace la soluzione di usare l'imbarcadero come gate. La formula può essere riscritta come:
t_battello = t_attesa_imbarcadero + t_tragitto
e t_attesa_imbarcadero ci lascia più flessibilità. Considerando un imbarcadero diverso per ogni linea e direzione (quindi 2 imbarcaderi per linea), la funzione peso è molto semplice, una volta calcolato se andiamo nella direzione giusta (supponiamo una bool wrong_direction)
peso = inf if wrong_direction else t_attesa_imbarcadero
un po' come i ponti e i sensi unici.
in ogni imbarcadero salviamo i tempi di passaggio (anche tutti come una lista) e calcoliamo il tempo di attesa come
t_attesa_imbarcadero = min(max(0, t_passaggio_battello - t_attuale))
dove t_passaggio_battello - t_attuale è il tempo che uno aspetta, e il max(0, t) tronca i negativi (i battelli già passati) e il min(0,t) prende il prossimo battello.
Poi ogni arco avrà come lunghezza il tempo che ci mette.

Il lato negativo è che avremo mille imbarcaderi/gate, però a livello concettuale mi sembra più semplice.
A livello computazionale l'algoritmo di dijkstra vedrà più possibilità (le linee che vanno nella stessa direzione) ma sono cose che servono.

Alcune cose che non ho chiare che però forse funzionano automaticamente:

• come settare la bool wrong_direction e se davvero si possa fare: o salviamo nel gate la lista di fermate a cui si può arrivare e si controlla (ma i cambi farebbero un casino, perchè teoricamente puoi arrivare dappertutto cambiando Xdicimila volte, no?) o forse proprio non si può e si lascia aperto tutto e dijkstra si refferà quando il tempo aumenta troppo che sta andando nella direzione opposta (ma computazionalmente potrebbe non essere ottimale)
• i cambi dovrebbero funzionare automaticamente (uno esce dal battello attraverso il gate, che però dovrebbe avere costo 0 in quel senso di percorrenza (scendendo dal battello) e poi ha di nuovo tutti i "gate" da cui può prendere nuovi battelli), ma non ci metterei la mano sul fuoco. Però in teoria dovrebbe funzionare e in teoria così avremmo anche opzioni a piedi-battello- a piedi -battello

[Lychfindel]

Mi è appena venuto un dubbio: è possibile creare archi diversi che collegano gli stessi due nodi del grafo?

[lucatastrophe]

Mi è appena venuto un dubbio: è possibile creare archi diversi che collegano gli stessi due nodi del grafo?

Non credo, I nodi sono identificati univocamente dalla coordinata e penso proprio che gli archi siano identificati univocamente dalla coppia di nodi. Almeno quando vogliamo accedere agli attributi di un arco lo chiamiamo con i due nodi che lo identificano. Se ci pensi sarebbe un casino altrimenti!

[Lychfindel]

Il lato negativo è che avremo mille imbarcaderi/gate, però a livello concettuale mi sembra più semplice.
A livello computazionale l'algoritmo di dijkstra vedrà più possibilità (le linee che vanno nella stessa direzione) ma sono cose che servono.
Secondo me per l'attuale costruzione del grafo questa soluzione non so se sia perseguibile perché se ricordo bene noi usiamo lat e long come identificativi dei nodi, quindi dovremmo avere più nodi con stesse lat e long

Alcune cose che non ho chiare che però forse funzionano automaticamente:

* come settare la bool `wrong_direction` e se davvero si possa fare: o salviamo nel gate la lista di fermate a cui si può arrivare e si controlla (ma i cambi farebbero un casino, perchè teoricamente puoi arrivare dappertutto cambiando Xdicimila volte, no?) o forse proprio non si può e si lascia aperto tutto e dijkstra si refferà quando il tempo aumenta troppo che sta andando nella direzione opposta (ma computazionalmente potrebbe non essere ottimale)

Secondo me questo non è un problema perché è giusto che uno possa fare mille cambi, semplicemente non è conveniente, esattamente come uno potrebbe fare mille strade ma viene presa solo la più breve.

* i cambi dovrebbero funzionare automaticamente (uno esce dal battello attraverso il gate, che però dovrebbe avere costo 0 in quel senso di percorrenza (scendendo dal battello) e poi ha di nuovo tutti i "gate" da cui può prendere nuovi battelli), ma non ci metterei la mano sul fuoco. Però in teoria dovrebbe funzionare e in teoria così avremmo anche opzioni a piedi-battello- a piedi -battello

Continuo a non capire il vantaggio dei "gate" rispetto ad avere i pesi direttamente negli archi dei battelli

[freerafiki]

Continuo a non capire il vantaggio dei "gate" rispetto ad avere i pesi direttamente negli archi dei battelli

Non è un cambio enorme, non stiamo parlando di cose troppo diverse, secondo me il vantaggio è (quasi) puramente concettuale - è lascerebbe tutti gli archi dei battelli più semplici. L'unica vera differenza che vedo (non so se ora mi stia dimenticando qualcosa) è che se abbiamo tutti i pesi negli archi dei battelli dobbiamo calcolare sempre anche quando uno è "già in battello" - il che magari non sarà un dramma ed è facile da implementare (se i conti t_tragitto e tempo di partenza del battello tornano), ma mi sembra meno elegante (rifa spesso dei conti che non ci servono) e che possa causare più problemi in fase di debug, mentre se gli archi hanno solo la lunghezza (in minuti o cmq in tempo) una volta che sei montato in battello, vai via liscio. In ogni caso entrambe le possibilità sono fattibili e funzioneranno, ma avere i gate mi sembra più elegante, meglio strutturato (quindi più facile da debuggare, ma qui l'ultima parola la dirà il tempo) e più comprensibile a livello concettuale da ricreare/modificare/gestire

[lucatastrophe]

Problema trovato: esistono percorsi di durata equivalente con più o meno cambi (conta l'orario di arrivo). Cosa fa networkx in caso di pareggio? Possiamo dirgli di prediligere quello con meno archi?
[edit] potrebbe bastare aggiungere una piccola penalizzazione quando entri su un gate (1 minuto per salire sul battello)

[lucatastrophe]

Uno dei problemi dell'approccio "informazioni in ogni arco", è che senza gate posso prendere solo il primo battello che passa e non ho possibilità di vedere il più veloce.

[lucatastrophe]

Nuovo possibile approccio: ogni pontile ha un arco per ogni pontile con cui è collegato e ha il tempo di percorrenza totale per arrivare a quel pontile

[Lychfindel]

Dalla documentazione di networkx mi sembra che non sia possibile accedere alle informazioni sul percorso attualmente calcolato da dijkstra: la funzione di peso richiede esattamente tre argomenti: nodo1, nodo2, edge.
Non vedo quindi la possibilità di calcolare il tempo di arrivo all'imbarcadero

[Lychfindel]

Problema trovato: esistono percorsi di durata equivalente con più o meno cambi (conta l'orario di arrivo). Cosa fa networkx in caso di pareggio? Possiamo dirgli di prediligere quello con meno archi?
[edit] potrebbe bastare aggiungere una piccola penalizzazione quando entri su un gate (1 minuto per salire sul battello)

Ho fatto un paio di test e mi sembra prediliga i percorsi con meno archi.

import networkx as nx
G = nx.Graph()
# creo i nodi 0, 1, 2 e gli archi 0-1 e 1-2
nx.add_path(G, [0, 1, 2])
# creo un arco 0-2
nx.add_path(G, [0, 2])
print(G.nodes) # Out: [0, 1, 2]
print(G.edges) # Out: [(0, 1), (0, 2), (1, 2)]
# assegno pesi agli archi
G[0][1]['length'] = 1
G[1][2]['length'] = 1
G[0][2]['length'] = 2
# shortes path
p = nx.single_source_dijkstra(G,0,2,weight='length')
print(p) # Out: (1, [0, 2])

[Lychfindel]

Dalla documentazione di networkx mi sembra che non sia possibile accedere alle informazioni sul percorso attualmente calcolato da dijkstra: la funzione di peso richiede esattamente tre argomenti: nodo1, nodo2, edge.
Non vedo quindi la possibilità di calcolare il tempo di arrivo all'imbarcadero

C'è da dire che il codice di networkx è open e la funzione di dijkstra è questa: https://github.com/networkx/networkx/blob/e7986285bfd6582f3ac5b1df97abaa307717b07f/networkx/algorithms/shortest_paths/weighted.py#L747
Se proprio volessimo potremmo cambiarla e aggiungere ai parametri passati al weight anche il percorso calcolo fino a quel momento.

[lucatastrophe]

Il calcolo con i battelli dovrebbe funzionare, come scritto nel file (https://next.eclabs.de/apps/files/?dir=/V4W&openfile=117579)
Il problema sarà ricostruire quanto ci abbiamo messo a fare il percorso più breve (con go_again_through_the_street) infatti dobbiamo (probabilmente) interrogare di nuovo il db con gli orari dei battelli, per calcolare il tempo di percorrenza.
uno degli aspetti è che go_again_through_the_street richiederà l'orario richiesto dall'utente.

[freerafiki]

fatto