Algoritmi - Algoritmo percorso migliore con mezzi pubblici

Forum - Algoritmi - Algoritmo percorso migliore con mezzi pubblici

Twizer (Normal User)
Newbie

Messaggi: 9
Iscritto: 30/10/2010

Postato alle 17:05
Venerdì, 09/12/2011

Sto cercando di realizzare un sistema che suggerisca il miglior percorso tramite mezzi pubblici per raggiungere una determinata posizione.

La risposta più ovvia è la realizzazione di un grafo e con l'algoritmo sui cammini minimi di dijkstra scegliere il miglior percorso sulla base del peso "tempo".
Purtroppo come qualcuno può immaginare tale algoritmo non aderisce perfettamente al problema in quanto non tiene conto di:
1) tempo di attesa alle fermate per gli scambi
2) tempo necessario a raggiungere le fermate (limite aggirabile)
3) numero di scambi limitato (per rendere il viaggio più confortevole)

C'è qualcuno con un pò più di esperienza o magari con qualche idea che mi possa suggerire un approccio più completo anche se non performante.

Sono accette anche documentazioni.

Grazie anticipatamente.

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 10:16
Sabato, 10/12/2011

Per fare questo algoritmo bisogna partire già del presupposto che la soluzione migliore non esiste. Bisogna almeno avvicinarsi.
In questo grafo bisognerebbe avere archi con due valori: uno per i mezzi di trasporto e uno per la "passeggiata".
Es:
1->2 con tempo 5min con mezzi di trasporto
1->2 con tempo 15min con i propri piedi

Inoltre ogni nodo deve avere un array con l'elenco degli orari dei mezzi pubblici che si possono prendere da quel nodo.

Secondo me per iniziare conviene usare un backtracking, non molto performante ma almeno funzionante.
Già implementarlo è una bella sfida XD

Un idea per un algoritmo più performante potrebbe essere questa:
1. Calcolare il percorso minimo a piedi da ogni nodo al nodo di arrivo
2. Aggiungere un arco da ogni nodo in cui c'è un fermata del mezzo a ogni nodo in cui passa segnando il tempo. (In questo modo capisci se ci metti di più a piedi o col mezzo per arrivare dal nodo X al nodo Y)
3.A questo punto fai un dijikstra per trovare il percorso più breve

Se noti non ho tenuto conto del tempo di attesa dei mezzi pubblici, per questo problema credo basti aggiungere il tempo di attesa agli archi del punto 2 del all'algoritmo.

Spero di averti dato qualche idea buona

ciao ciao

Twizer (Normal User)
Newbie

Messaggi: 9
Iscritto: 30/10/2010

Postato alle 19:23
Sabato, 10/12/2011

Grazie per averci provato, ma probabilmente non sono stato in grado di spiegarmi.

Quello che voglio realizzare è un algoritmo di "journey planner" che è stato già realizzato per diversi sistemi per la raccomandazione dei percorsi quindi non devo necessariamente inventarlo da zero.

Il problema è che non esiste praticamente alcuno spunto teorico su come sono realizzati, speravo di trovare qualcuno che ci avesse già sbattuto il naso.

Io pensavo di creare per ogni linea un grafo orientato che collegasse ad ogni fermata tutte le fermate successive;
quindi ipotizzando una linea con 3 fermate

[1]----->[2]----->[3]
| /\
| |
+-----------------+

Incrociato con tutte le altre linee

e utilizzare partendo da questo il dijkstra semplice, secondo voi può funzionare?

Ultima modifica effettuata da Twizer il 10/12/2011 alle 19:30

TheKaneB (Member)
Guru^2

Messaggi: 1792
Iscritto: 26/06/2009

Postato alle 15:09
Domenica, 11/12/2011

Puoi partire dall'algoritmo A* (pronunciato "A star").

Si tratta di una versione modificata di Dijkstra, in cui l'ordine di valutazione dei nodi non è uguale al loro inserimento in coda, ma avviene tramite una funzione "peso" supplementare che viene implementata tramite una euristica. (in pratica si usa una priority-queue, e la priorità dei nodi coincide con il valore della distanza in linea d'aria tra il nodo corrente e la destinazione).

Nel caso tipico di una mappa geografica, l'euristica equivale alla distanza euclidea (distanza che puoi calcolare abbastanza facilmente conoscendo le coordinate dei nodi).

Nel tuo caso potresti complicare ulteriormente l'euristica calcolando man mano l'orario di arrivo in ciascuna fermata e sommando il tempo necessario per l'attesa del successivo mezzo di trasporto.

Ci sono tecniche migliori ma sono algoritmi molto più complicati e non è detto che il margine di miglioramento sia sufficiente a giustificare lo sforzo implementativo.