Logistics planning for restoration of network connectivity after a disaster

Abstract

Sel, deprem gibi doğal afetlerin etkisiyle karayolları hasara uğrayabilir ve zemin sıvılaşmasına bağlı olarak çökme ya da bina ve elektrik/lamba direklerinin enkazı yığılması sonucu bazı yollar ulaşıma kapanabilir. Sonuç olarak, bazı bölgelere ulaşım engellenebilir. Yol ağı bağlanılırlığının sağlanması için gerekli çalışmalar yerine getirilmelidir. Bu çalışmalar acil tıbbi yardım ve ulaşımı kolaylaştırmak adına büyük önem taşır.Afet sonrasında en kısa zamanda ulaşımı hızlandırmak ve ulaşım ağında bağlantının yeniden sağlanması için, kritik olan yolların açılması gerekmektedir. Yeterli personel ve teçhizata sahip, çeşitli lokasyonlarda konuşlandırılmış araçlar bu iş için kullanılmalıdır. Bu çalışmada koordineli bir iş çizelgesi oluşturma amacıyla bir eniyileme problemi tanımlanmıştır. Yol ağı, yönlü bir çizge üzerinde, araçlara ait seyir süreleri ile birlikte temsil edilmiştir. Kapalı olan yolları açmak için gereken sürenin, afet sonrasında edinilecek yol durumu bilgisine göre tespit edileceği varsayılmıştır. Problem, hangi kapalı yolların açılacağının ve her araç için bir dağıtım noktasından (depo, acil yardım merkezinden vs.) başlayan, açılacak olan yollardan geçen turların belirlenmesidir. Amaç, en uzun tur uzunluğunu enküçüklemektir. Ayrıt rotalama, zaman çizelgeleme ve ağ tasarımı öğeleri içeren bu probleme K Araçlı Bağlanırlık Amaçlayan Ayrıt Rotalama Problemi adı verilmiştir ve tek araçlı durumda bile polinom zamanda çözümünün zor olduğu ispat edilmiştir. Olası ve en iyi çözümlerin özellikleri incelenmiştir. Akış karar değişkenleri kullanılarak bir karışık tamsayı programlama formulasyonu verilmiş ve iki gevşetme modelinden alt sınırlar elde edilmiştir. İstanbul karayolları ağı kullanılarak veri oluşturulmuş ve bileşen, araç ve depo sayısının çözüm süresi ve kalitesi üzerindeki etkileri analiz edilmiştir.

In a natural disaster; e.g., earthquake, flood, landslide, road networks can be damaged, and consequently some parts of the roads may be blocked by building or lamppost debris or may collapse due to ground liquefaction. As a result, the road network may become disconnected. In order to ensure connectivity, necessary actions should be taken after a disaster. In the immediate disaster response phase, to facilitate emergency transportation, a critical subset of the blocked roads should be cleared to restore network connectivity as soon as possible. A fleet of machinery with required personnel and equipment which are initially positioned at various locations, e.g. depots, should be dispatched for this task. We define an optimization problem to generate a coordinated work schedule. We represent the road network by a directed graph with estimated arc traversal times for work vehicles. We assume that time to open each blocked arc will be estimated after the disaster by gathering information on road conditions. The problem is to determine which blocked arcs to open and a walk for each vehicle starting at its depot that collectively cover the selected blocked arcs. The objective is to minimize the total time of the longest walk, i.e. the makespan. We name this problem that combines network design, scheduling and arc routing aspects, Arc Routing for Connectivity Problem with K Vehicles (K-ARCP). We prove that K-ARCP is NP-hard even when a single vehicle exists. We characterize some properties of feasible and optimal solutions. We formulate a mixed integer program using flow variables for the walks. We define two relaxations to obtain lower bounds and test their performance computationally. We generate instances using data of Istanbul highway network and analyze the effects of the number of disconnected components, the number of vehicles and depot locations on solution time and quality.