Progetto congiunto di ricerca e sviluppo per lo studio e la realizzazione di sistema web based per la pianificazione adattiva della logistica rivolta a soluzioni di mobilità sostenibile.
Il progetto è stato caratterizzato da un’intensa attività di studio e analisi delle tecniche e dei modelli matematici su cui si basa il SW di pianificazione, al fine di ridurre i tempi di calcolo della matrice ripensando a strutture e algoritmi di esplorazione del grafo stradale. Le matrici di distanze costituiscono di fatto il dato iniziale sul quale si basa l’algoritmo di ottimizzazione. Ridurre quindi i tempi di calcolo di queste matrici, contenenti le distanze tra i punti di visita, ha un impatto notevole sui tempi di calcolo dell’intera ottimizzazione.
Sono stati individuati e realizzati degli algoritmi di ricerca del percorso minimo su grafo stradale basati sulla riduzione dello spazio di ricerca tramite il metodo dei grafi multilivello.
Il concetto alla base di queste tecniche e quello comunemente utilizzato dagli umani quando devono raggiungere una destinazione lontana, questi raggiungono un punto di accesso ad una strada statale poi ad un’autostrada e con questa raggiungono un punto di uscita prossimo alla destinazione. Ovviamente per garantire la certezza della soluzione ottima, non è possibile utilizzare come gerarchia quella propria delle strade ma ci si deve basare sulla topologia del grafo.
La prima fase quindi consiste nella costruzione di un grafo multilivello andando ad individuare gli archi topologicamente vantaggiosi e promuovendoli ai livelli superiori.
Durante la seconda fase, quella di ricerca, il calcolo delle matrici e dei percorsi minimi viene eseguito esplorando il grafo multilivello e prediligendo gli archi che appartengono ai livelli superiori, questo porta ad una riduzione dello spazio di ricerca e a un conseguente diminuzione dei tempi di calcolo.
Queste tecniche portano ad una notevole riduzione dei tempi di calcolo mantenendo comunque la correttezza e la certezza della soluzione.
Riportiamo alcuni tempi ricavati da esperimenti condotti su grafo Italia e su matrici di grosse dimensioni, come si può vedere la riduzione in termini di tempo è di parecchi ordini di grandezza.
| Dimensione delle matrici | Tempi di calcolo con metodi classici | Tempi di calcolo con nuovi metodi |
| 3 × 3 | 10,3 s | 0,190 s |
| 200 × 200 | 14 m 4 s | 3 s |
| 1000 × 1000 | 52 m 3 s | 28 s |
| 1500 × 1500 | 1 h 13 m | 52 s |
| 2000 × 2000 | 2 h 30 m | 1 m 10 s |
Utilizzando le stesse tecniche di speed-up è stato inoltre possibile realizzare degli algoritmi per il calcolo dei percorsi minimi su grafi tempo-varianti. Questi grafi a differenza di quelli statici, hanno la caratteristica di avere un peso dell’arco che varia in funzione di un orario e vengono quindi utilizzati per modellizzare i tempi di attraversamento di un arco in presenza di traffico.
Il sistema è quindi in grado di fornire percorsi e tempi ottimi in funzione dell’orario di partenza e in base ai dati di traffico forniti da gestori cartografici.
