Modelli e algoritmi di ottimizzazione per il Bulk-Robust Connectivity Problem

La crescente dipendenza della società moderna dalle infrastrutture di rete rende la resilienza un requisito fondamentale nella fase di progettazione. Il presente lavoro di tesi affronta il Bulk-Robust Connectivity Problem, un problema di ottimizzazione combinatoria volto a garantire la connettività di un grafo a fronte di scenari di guasto massivo, minimizzando al contempo l'investimento economico. Data la natura $NP$-hard del problema, l'utilizzo di solutori esatti risulta spesso proibitivo per istanze di dimensione industriale a causa dell'esplosione dei tempi di calcolo. Per superare tali limitazioni, viene proposto un framework metaeuristico basato sulla logica Multi-Start Local Search (MSLS). L'algoritmo integra una fase di generazione ad aleatoria dinamica, volta a garantire una diversificazione efficace nello spazio delle possibili topologie, con una ricerca locale dedicata all'intensificazione e al raffinamento della soluzione. L'aspetto innovativo dell'algoritmo risiede nella sua flessibilità operativa: esso permette di ottenere configurazioni ammissibili entro un budget temporale definito dall'utente, offrendo uno strumento adattabile in cui il trade-off tra qualità della soluzione e velocità di esecuzione è gestito come variabile decisionale. La validazione sperimentale conferma l'efficacia dell'approccio proposto. Il confronto con un solutore esatto evidenzia la capacità del framework MSLS di individuare soluzioni prossime all'ottimo in tempi di calcolo estremamente contenuti, garantendo al contempo la totale ammissibilità rispetto agli scenari di guasto. Ulteriori analisi dimostrano la scalabilità dell'algoritmo e la sua capacità di raffinamento incrementale al crescere delle risorse temporali messe a disposizione, attestando la validità della metaeuristica come alternativa efficiente ai metodi di risoluzione tradizionale.