Network optimization problems for disaster mitigation: Network reliability, investment for infrastructure strengthening and emergency facility location

Abstract

Koç ÜniversitesiYüksek Lisans Tez Özet FormuÖğrencinin Adı : Dilek GünneçAna Bilim Dalı : Endüstri MühendisliğiTez Başlığı : Afet ile Mücadelede Ağ Optimizasyonu Problemleri:Ağ Güvenilirliği, Altyapı Güçlendirmesi için YatırımPlanlaması ve Acil Müdahale Merkezi YerleştirilmesiÖzetBu tezde afet yönetimi ile ilgili üç ağ optimizasyonu problemi ele alınmıştır. Herproblem etkin bir afet sonrası faaliyetler için afet öncesi süreçte stratejik planlamayıkapsamaktadır. lk problem, alt yapı sistemlerinin güvenilirliğinin ve performansınındeğerlendirilmesi ile ilgilidir. Bu problemde, ağ bağlarının kopma olasılıklarının birbirlerinebağımlı olduğu durumları gösterebilmek için bir yaklaşım öne sürülmüştür. Bu yaklaşımkullanılarak, fazla verinin bulunmadığı afet durumlarında kullanılabilecek bir bağımlılıktanımı ortaya konmuştur. Bir ağın bu bağımlılık yapısı altında güvenilirliğini veperformansını ölçebilmek için yeni ve polinom-zamanlı bir algoritma geliştirilmiştir. kinciproblem, ağ bağlarını güçlendirmek için yapılan yatırımlarda belli bir bütçenin en iyi şekildedeğerlendirilmesi icin kritik bağlarin belirlenmesi problemidir. Kritik bağlar belirlenirkenkiamaç, güçlendirildiği takdirde ağın afet sonrası en yuksek performansını sergilediği bağıbulmaktır. kinci problemde, daha önce geliştirilmiş olan bir metodun hesapsaluygulanabilirliği Monte Carlo yöntemi kullanılarak örnek bir olay üzerinde incelenmiştir.Tezde ele alınan son problem ise afet sonrası hizmet vermesi planlanan aktarma ve dağıtmamerkezlerinin yer seçimine karar verilmesidir. Amaç fonksiyonu, farklı afet senaryolarıaltında en fazla sayıda insana en kısa zamanda çoklu malzeme taşınması ve dağıtılması olarakbelirlenmiştir. Aktarma ve dağıtma merkezlerinin her bir malzeme için belli bir uzaklıktaolması koşulu altında taşıma zamanının ağırlıklı ortalaması minimize edilmeye çalışıldığıkapasitesiz bir matematiksel model kurulmuştur. Bu model gerçek bir problemi çözmek içinkullanılmıştır. Bu üç problem de deprem riski altında olan stanbul için uygulamayakonulmuştur. Deprem senaryolari, bu senaryolar altında ulaşım ağlarının durumları, belirlibölgelerdeki deprem riskleri ve bölgeler arasındaki uzaklıklar gibi gerçek verilertoplanılmıştır. Matematiksel modelin girdileri toplanan veriler kullanılarak türetilmiştir. Önesürülen çözüm algoritmaları stanbul şehrinin deprem hazırlıkları aşamasında karşılaştığıproblemlerin çözülmesinde kullanılmıştır.Danışman: Yrd. Doç. Dr. Sibel Salman Tarih: 31.07.2007Enstitü Müdürü: Prof. Dr. Süleyman Özekici Tarih: 31.07.2007

MSc Thesis Abstract FormName of the Student : Dilek GünneçProgram of Study : Industrial EngineeringThesis Title : Network Optimization Problems for DisasterMitigation: Network Reliability, Investment forInfrastructure Strengthening and EmergencyFacility LocationAbstractThree network optimization problems arising in disaster mitigation are addressed inthis thesis. Each problem involves strategic decision-making in pre-disaster stage foreffective post-disaster relief operations. The first problem is on assessing the reliability andperformance of infrastructure networks under disaster risk. Here, a framework to representlink dependency in failures is proposed. Using this framework, a special type of dependencystructure which is relevant for the disaster situation with lack of sufficient past data, isdefined. Under this dependency structure, a novel polynomial-time algorithm is proposed toanalyze the reliability and performance of a network. The second problem involves allocatinga budget to links of an infrastructure network to increase the reliability and the performanceof the network. With investment, each link can be strengthened structurally such that itsprobability of survival after a disaster increases. Then, the problem is to find which links toinvest in so that most benefit is obtained in terms of post-disaster performance of thenetwork with respect to accessibility and travel time between critical points in the network.The computational applicability of a previously developed method is demonstrated in thesecond problem by developing a Monte Carlo simulation algorithm and applying it to a real-life case study. The last problem addressed in this thesis is a facility location problem thatseeks to identify locations of emergency response and distribution centers to provideeffective post-disaster logistics operations such as the supply of relief commodities to theaffected areas. For this problem, an uncapacitated facility location model is formulated withthe objective of reaching a maximum number of people in minimum time possible after adisaster to distribute multiple commodities through the facilities under several disasterscenarios for demand and travel time. Average weighted travel time is minimized subject toconstraints on the existence of a facility within a fixed distance from each district for eachcommodity. This model is used to solve a real-life problem. All of the three problems and themethodology developed for these problems are computationally tested on the case ofIstanbul, a metropolitan under serious earthquake risk. Real-life data including theearthquake scenarios, the risk of the highway structures under these scenarios, expecteddamage at various districts, expected demand for relief commodities after an earthquake,travel time estimates between critical origin-destination points were collected. Ourmathematical model inputs are generated with respect to the collected data, and our solutionalgorithms are used to solve the real-life problems relevant for the earthquake preparednessof the city of Istanbul.Advisor: Assist. Prof. Sibel Salman Date: 31.07.2007Director: Prof.Dr. Süleyman Özekici Date: 31.07.2007