Algoritmi per la ricerca di cammini robusti nelle reti urbane

- 6 - INTRODUZIONE Utilizzare un’automobile per spostarsi in libertà da un luogo all’altro della città è un’esperienza che ha coinvolto tutte le persone. Il costante aumento dei veicoli per la necessità di doversi spostare su percorsi che toccano grandi distanze, e la presenza sempre più numerosa di autoveicoli genera quel fenomeno che è il traffico. La scarsa capacità delle reti urbane e l’aumento del traffico ha portato allo sviluppo di algoritmi per la gestione di quest’ultimo e dei sistemi Route Guidance. La tecnologia GPS può essere usata per monitorare le aree urbane e suburbane e fornire informazioni utili riguardanti i movimenti di tutti i veicoli. I più recenti sistemi Route Guidance sono semplici dal punto di vista algoritmico e riescono facilmente a suggerire il cammino più breve per arrivare a destinazione, ma, quando hanno a che fare con reti di notevoli dimensioni, non sempre tengono conto delle preferenze degli utenti in termini di percorso. In questa tesi, al problema della ricerca dei cammini brevi, si è preferito affrontare quella relativo alla ricerca dei cammini a basso rischio; si è introdotto, quindi, il concetto di cammino robusto, cioè un percorso che, in caso di un evento inatteso (i.e. un incidente), possa offrire una valida alternativa non penalizzante per l’utente. Pertanto, è stato sviluppato un algoritmo per la ricerca del cammino robusto di lunghezza minima, ovvero il cammino di lunghezza minimo che, in un qualsiasi punto, può offrire delle valide alternative all’utente. Questo algoritmo di ricerca delle vie alternative avrà come termine di paragone la lunghezza del cammino minimo del percorso considerato.