Decomposizione ed euristica lagrangiana per ottimizzare la pianificazione del trasporto di merci pericolose in galleria

This thesis arises from the actual issue of managing the access of dangerous goods into tunnels, in compliance with the norms set forth in the ADR 2011 (European Agreement concerning the international carriage of Dangerous goods by Road}. The aim of the study is to minimize the global risk related to the circulation of dangerous goods by means of an optimal planning of the openinig/closure of tunnels. Recent studies in the transport sector stress the necessity of giving a general overview of the problem and at the same time analysing the shipment of hazardous materials from their origins $o$ to destinations $d$. The availability of this information for the Lombardy Region has enabled us to use aBilevel model based on Mathematical Programming which generates a MILP problem (Mixed Integer Linear Programming). This optimization problem could be included among the so called ''NP-hard'' problems, this means that the research of the optimal solution shall be switched to the study of suboptimal resolving algorithms. According to the characteristics of the problem, we have decided to focus on a Lagrangian relaxation oriented to the decomposition of the problem into independent subproblems. Hence, these subproblems could be optimized separately using the subgradient method in order to searching the optimal Lagrange multipliers. Furthermore a Lagrangian Heuristic applied to the subgradient method is able to control the gap between the lower bound and the upper bound of the problem, thus reducing the time necessary for searching the optimal Lagrangian multipliers. This method has been tested with satisfactory results on actual issues related to the traffic of dangerous goods by road in the Lombardy Region.

Questa tesi nasce da un problema reale legato alla necessità di gestire gli accessi in galleria delle merci pericolose su strada secondo quanto previsto dall'ADR 2011 (european Agreement concerning the international carriage of Dangerous good by Roads). Lo scopo è di minimizzare il rischio globale relativo alla circolazione delle merci pericolose attraverso la pianificazione ottima dell'apertura/chiusura delle gallerie. Gli studi in ambito trasportistico mettono in evidenza la necessità sia di considerare il problema da un punto di vista globale che di conoscere i flussi di traffico tra le coppie origine-destinazione. La disponibilità di tali dati per la regione Lombardia ha permesso l'utilizzo di un modello di Programmazione Matematica bilivello generando un problema di tipo PLIM Programmazione Lineare Intera Mista). Il problema di ottimizzazione che ne deriva rientra nella cosiddetta classe dei problemi "NP-difficili" ed è quindi necessario abbandonare la ricerca di una soluzione ottima concentrandosi su algoritmi risolutivi subottimi. Per le caratteristiche del problema, si è scelto di procedere con un rilassamento lagrangiano finalizzato alla sua decomposizione in sottoproblemi indipendenti. Perciò tali sottoproblemi sono ottimizzabili separatamente utilizzando il metodo del sottogradiente per la ricerca dei moltiplicatori ottimi di Lagrange. Infine un'euristica lagrangiana inserita all'interno del metodo del sottogradiente controlla il gap tra lower bound ed upper bound del problema permettendo anche di ridurre i tempi di calcolo per la ricerca dei moltiplicatori ottimi di Lagrange. Il metodo è stato testato con buoni risultati su istanze reali relative al traffico di merce pericolosa della regione Lombardia.