Robust optimization models for the hazmat transport network design problem

A great number of Hazardous Materials _ or Hazmats _ are transported on our roads every day, and an accident happening to such shipments could have high consequences on people and the environment. The risk associated with every hazmat shipment and every path depends on the probability of an accident and the nearby population density. In order to mitigate the risk associated with the transportation of hazmats, given a road network the regulators cannot decide the single routes, but have the authority to close certain roads to hazmat traffic: in this work only a subset of the road segments can be closed. The carriers will choose on the resulting network the paths that minimize their cost. Unfortunately, the risk parameters are not easy to be estimated and therefore are subject to uncertainty. Also the origins and destinations of each shipments may be uncertain, since the carriers do not have to declare them by law. The purpose of this work is to propose and investigate alternative robust models for the Hazmat Transport Network Design Problem (HTNDP), that are robust with respect to the variation of the uncertain risk coefficients. In order to do so, we start from a nominal stable bilevel formulation and from a compact single-level MILP derived from it, as done in previous works. Important properties of such models are stability and linearity. We maintain such features in all the models we propose. Moreover, we consider compact MILP formulations instead of heuristic algorithms or cutting plane approaches, seen the better performances of a MILP approach in solving integer problems. To take into account the uncertainty on the risk coefficients, we adopt a Robust Optimization (RO) approach _ specifically, based on the "Gamma-robustness" proposed by Bertsimas and Sim _ instead of the previously born Stochastic Optimization, that is computationally more costly. Firstly we introduce RO in the nominal single-level formulation. We split the process into multiple steps, starting by providing a robust objective function. We notice that, if stability were neglected, the robust objective function would make the model fully robust. Then we adopt the same method for the "strong duality constraint" that derives from the bilevel inner problem objective function, preserving stability. We remark that a slight modification in such constraint allows to correlate the worst-case deviations of the risk parameters in the objective function and in the constraint, producing a more coherent and not over-conservative model. Naturally such update affects only marginally the model and still allows to account for stability. Then we extend Gamma-robustness independently to all the remaining constraints. In order to do so, we need to adapt the method, completely maintaining the meaning of RO. These constraints cannot be treated together with the previous uncertain terms, therefore their robust version could introduce a little over-conservativeness. As an alternative, we also propose and study a robust model deriving from the original bilevel formulation, instead of its single-level derivative. The process leading to such model introduces a duality-gap, therefore its optimal solutions will return a higher value in risk of the objective function. We also describe possible variations of the nodes of origin and destination. By adapting the methodology of RO to this particular situation, we provide a robust formulation of the Shortest Path Problem, that is the simplest problem that can present such variations of the nodes. Then we move the first steps in extend the developed technique to the HTNDP. We produce a bilevel formulation of the HTNDP, robust with respect to variations of the nodes of origin and destination, that cannot be reduced to a single-level MILP due to non-linearities introduced. We run computational tests of our models on available benchmark data sets of the city of Ravenna considered in literature. From the data point of view, we also study and increase the number of independent paths on the original graph, generating a more connected graph. In doing so, we provide algorithms to augment a graph and compute its coefficients. As done in previous works, we consider our robust models on directed graphs and point out and discuss the consequences, concluding that further changes to the model would introduce unrealistic hypothesis. The robustness and conservatism parameters are generated reasonably starting from the provided data. Our models, implemented in Python, are solved using the state of the art MILP solver Gurobi 6 and the results obtained by the different models (single-level derived and bi-level derived) are compared. We show with such results and comparisons that the models provided, while ensuring a chosen level of robustness, produce solutions that are economically acceptable, i.e. their cost is not significantly different from the cost of non-robust solutions, and not too conservative: indeed, our robust solutions produce a very small augment in risk compared to the previous non-robust solutions. Besides, these models can be solved with state of the art solvers, with a computational effort that is not excessively higher than the one required for their nominal counterpart. Depending on the chosen level of conservatism, ro bust solutions can deviate more or less from the solutions returned by the nominal model. Although, for reasonable values of the conservatism parameter, our solutions do not change excessively their nominal counterpart _ but they bring the advantage of being robust. We compare the different models we proposed and a previous attempt of a robust HTNDP model, also using different parameters of numerical precision. Lastly, we test a nominal and robust model on the more connected graph we generated previously, stressing the differences of behaviour with the solutions obtained on the original graph.

Un gran numero di materiali pericolosi (Hazmats) vengono trasportati ogni giorno sulle nostre strade, e un incidente a questi carichi può avere gravi conseguenze su persone e sull'ambiente. Il rischio associato ad ogni spedizione di hazmat e ad ogni percorso dipende dalla probabilità di incidenti e dalla densità di popolazione nell'area. Per mitigare il rischio associato al trasporto di hazmat, data una rete stradale le autorità non possono stabilire i singoli percorsi seguiti dai camion, ma hanno il potere di chiudere certe strade al traffico di hazmat: in questo lavoro solo un sottoinsieme dei tratti stradali può essere chiuso. I trasportatori sceglieranno sulla rete risultante i cammini che minimizzano il loro costo. Sfortunatamente, i parametri di rischio non sono facili da stimare e quindi sono soggetti ad incertezza. Anche le origini e destinazioni di ogni spedizione possono essere incerte, dato che i trasportatori non devono dichiararle per legge. L'obiettivo di questo lavoro è di proporre e studiare diversi modelli robusti per il problema di progetto di rete per il trasporto di materiali pericolosi (Hazmat Transport Network Design Problem _ HTNDP), che siano robusti rispetto alle variazioni dei coefficienti di rischio, che sono incerti. Partendo da una formulazione nominale bilivello che è stabile, e da una formulazione compatta (MILP) mono-livello derivata da questa, come da lavori precedenti. La stabilità e la linearità sono caratteristiche importanti di questi modelli, che ci preoccupiamo di preservare in tutti i modelli che proponiamo. Inoltre, consideriamo formulazioni compatte MILP, invece che utilizzare algoritmi euristici o piani di taglio, viste le prestazioni migliori di un approccio MILP nel risolvere problemi interi. Per tenere conto dell'incertezza sui coefficienti di rischio, adottiamo un approccio di tipo Ottimizzazione Robusta (RO) _ nello specifico, modelli basati sulla Gamma-robustezza proposta da Bertsimas e Sim _ anziché la più classica ma computazionalmente più onerosa Ottimizzazione Stocastica. Iniziamo introducendo la RO alla formulazione nominale mono-livello, dividendo il processo in passi successivi e iniziando col ricavare una funzione obiettivo robusta. Notiamo che, se si ignorasse la stabilità, questa funzione obiettivo renderebbe il modello interamente robusto. Poi adottiamo lo stesso metodo per il vincolo di dualità forte, derivato dalla funzione obiettivo del problema interno della formulazione bilivello, che preserva la stabilità. Osserviamo che una leggera modifica al vincolo permette di correlare le deviazioni dei parametri di rischio nella funzione obiettivo e nel vincolo nel caso peggiore considerato dal modello. Questo produce un modello più coerente e non troppo conservativo, e ovviamente influenza solo marginalmente il modello, preservando la stabilità. Infine estendiamo la RO a tutti i vincoli rimanenti indipendentemente. Per questi dobbiamo adattare il metodo, mantenendone completamente il significato. Questi vincoli non possono essere trattati assieme agli altri elementi di incertezza, e per questo la loro versione robusta potrebbe rendere il modello più conservativo. Proponiamo anche, in alternativa, un modello robusto a partire dalla formulazione originale bilivello, invece che dal problema mono-livello. Nel ricavare questo modello viene introdotto un salto di dualità, che fa sì che le soluzioni abbiamo un valore di rischio più elevato della funzione obiettivo. Descriviamo anche le possibili variazioni dei nodi di origine e destinazione, fornendo prima una formulazione robusta per il Problema del Cammino Minimo, che è il problema più semplice a presentare tali variazioni. Quindi facciamo un primo passo per estendere la tecnica sviluppata al nostro problema. Ricaviamo una formulazione bilivello dell'HTNDP robusta rispetto alle variazioni dei nodi di origine e destinazione, che non può però essere ridotta a un MILP mono-livello a causa delle non linearità introdotte. Effettuiamo prove computazionali dei nostri modelli su insiemi di dati di riferimento già disponibili, relativi alla città di Ravenna e utilizzati in letteratura. Dal punto di vista dei dati, studiamo anche il numero di cammini indipendenti sul grafo originale, e lo incrementiamo generando un grafo più connesso. Nel farlo presentiamo degli algoritmi per estendere un grafo e calcolarne i nuovi coefficienti. Come viene fatto in lavori precedenti, consideriamo i nostri modelli robusti su grafi orientati ed ne indichiamo e discutiamo le conseguenze, concludendo che ulteriori modifiche al modello introdurrebbero ipotesi non realistiche. I parametri di robustezza e grado di controllo su quanto la soluzione è conservativa sono generati ragionevolmente a partire dai dati disponibili. I nostri modelli, implementati in Python, sono risolti utilizzando il risolutore MILP stato dell'arte Gurobi 6 e i risultati ottenuti con i vari modelli (derivati da bilivello e mono-livello) sono confrontati. In particolare si osserva dai nostri risultati e confronti che i modelli presentati, che assicurano il livello di robustezza scelto, restituiscono soluzioni economicamente accettabili, ovvero il cui costo non è molto differente dal costo delle soluzioni non robuste, e non troppo conservative: infatti le nostre soluzioni robuste producono un aumento di rischio molto piccolo confrontato con le precedenti soluzioni non robuste. Inoltre, questi modelli possono essere risolti con i ri solutori attuali, con uno sforzo computazionale non molto maggiore di quello richiesto dal modello nominale. A seconda di quanto conservative si richiedono le soluzioni, queste possono variare più o meno rispetto alle soluzioni del modello nominale. Comunque, per valori ragionevoli del parametro che controlla quanto la soluzione è conservativa, le nostre soluzioni non modificano eccessivamente la soluzione del modello nominale _ hanno però il vantaggio di essere robuste. Confrontiamo i diversi modelli proposti e un tentativo precedente di un modello robusto per l'HTNDP, anche con diversi parametri di precisione numerica. Infine risolviamo il modello nominale e uno robusto su un grafo più connesso che abbiamo generato, evidenziando le differenze rispetto alle soluzioni ottenute sul grafo originale.