A syncronized routing problem for restoring inter-dependent infrastructure networks

Abstract

Disasters may cause significant damages in lifeline infrastructure systems (such as gas, power, water) and lead to long-lasting failures. It is important to repair the damaged components and restore the affected infrastructures quickly. Since different lifeline infrastructure systems depend on each other, considering the inter-dependencies among different networks during repair planning can speed up the recovery process. In this thesis, we focus on developing practical methods to support planning repair operations for two inter-dependent infrastructure networks by considering the inter-dependencies within and between these networks. Specifically, we assume that repairing a damaged component may not be sufficient for making the component functional due to network dependencies. We consider multiple repair teams, each of which can repair the damaged components of one type of infrastructure, and formulate a coordinated repair scheduling problem, which determines a repair schedule for each repair team to minimize the total time for making all nodes functional. To solve this problem, we propose two alternative constructive heuristics, which employ different strategies to prioritize the visit of the damaged nodes based on their dependency status. We also apply local search procedures to improve the solutions attained by the constructive heuristics. We present computational results to evaluate the performance of the proposed heuristics. The results show that our heuristics lead to high quality solutions and can be used to make repair plans quickly in the post-disaster environment.Doğal felaketten sonra, gaz, elektrik, su ve telekomünikasyon gibi altyapı sistemleri hasar görebilir ve işlevselliğini kaybedebilir. İnsani yardım çalışmalarında meydana gelen bir doğal felaketten sonra hasar gören altyapı sistemlerinin tamir süreci iyileştirme adımında gerçekleşir. Bu süreç¸ insani yardım lojistiğindeki süreç gibi ivedi karar verme ve reaksiyon alınmasını gerektirmektedir. Bu süreçteki hedef, arızaları ve birbirine bağımlı altyapıları bir an önce tamir etmek ve en kısa zamanda talebi karşılamaktır. Tamirat sürecinde otoriteler ağlar arasındaki birbirine bağımlılık hususunu da göz önünde bulundurmalıdırlar. Çalışmaları esnasında birbirine ihtiyaç duyan altyapılara birbirine bağımlı altyapılar denmektedir. Bu çalışmada altyapı içerisinde hasar görmüş düğümleri en yakın süre zarfı içerisinde tamir etmeyi amaçlayan birbirine bağımlı altyapı sistemlerini için rotalama kararlarını inceliyoruz. Özel olarak, birbirine bağımlı altyapı ağlarını tamir için senkronize rotalama problemini ( Synchronized Routing Problem for Restoring Interdependent Infrastructure Networks - SRPRIIN) tarif ediyor ve inceliyoruz. Bu çalışmada, bir matematiksel model ve iki yapıcı sezgisel program ile ön sonuç elde edip, yerel arama prosedürlerini kullanarak ön sonuçlar geliştirmekteyiz. Yapıcı sezgisel programlar, tamirat rotalarının oluşturulması esnasında ağlar arasındaki etkileşimlere verdikleri öncelikler hususunda farklılaşmaktadırlar. Modelimizi test etmek için sayısal bir çalışma gerçekleştiriyoruz ve yapıcı sezgisel programların iki farklı versiyonlarından elde edilen sonuçları optimizasyon yazılımından elde edilen sonuçlar ile mukayese ediyoruz. Bütün durumlar düşünüldüğünde, sezgisel programlar optimizasyon yazılımına göre eşit ya da daha iyi performans göstermekte ve daha hızlı sonuç vermektedir.