Riottimizzare cammini minimi: analisi e strategie risolutive

Il problema del cammino minimo è uno dei problemi più studiati in Ricerca Operativa, sia per la sua importanza dal punto di vista teorico, sia perché si presenta, nelle sue innumerevoli variazioni, in moltissime applicazioni. È frequente, sempre in ambito applicativo, ritrovarsi a dover risolvere non uno, bensì una sequenza di problemi di cammino minimo, dove ciascuno di essi differisce dal precedente per piccoli cambiamenti nei parametri del problema. Basti pensare, ad esempio, a problemi di gestione del traffico aereo o stradale, dove la convenienza a percorrere certe traiettorie può variare significativamente nel tempo e come conseguenza cambia il modello che si utilizza. In questa sequenza un problema e il successivo possono differire per piccoli cambiamenti nella struttura del grafo sottostante oppure nei costi associati agli archi. Sorge allora la seguente questione: dati due problemi di cammino minimo in cui il secondo è “leggermente diverso” dal primo, è necessario riapplicare nuovamente l’algoritmo risolutivo daccapo o si possono sfruttare le soluzioni ottime precedentemente ottenute e giungere alla soluzione in modo alternativo con minor costo computazionale? A questo scopo sono stati formulati degli algoritmi di "riottimizzazione" i quali essenzialmente risolvono il problema di cammino minimo a partire dalle informazioni di ottimalità riguardanti un grafo leggermente diverso. In questa tesi, viene presentato e analizzato un algoritmo di riottimizzazione che affronta il caso più generale, cioè quello in cui un grafo e l'altro differiscono per modifiche ai costi di un qualsiasi sottoinsieme di archi, i quali possono variare sia per un aumento che per una diminuzione arbitrari. Si indagherà la correttezza teorica delle procedure proposte e verranno analizzate diverse casistiche; tutto ciò verrà accompagnato da vari esempi, per arrivare infine a confrontare l'efficienza di tale strategia rispetto all'approccio classico di risoluzione ex novo.