Minimizing latency in post-disaster debris removal
Afet sonrası enkazın kaldırılmasındaki gecikmeyi minimize etmek
- Tez No: 567647
- Danışmanlar: PROF. DR. FATMA SİBEL SALMAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 116
Özet
Doğal bir afetten sonra, yol ve köprüler zarar görebilir veya enkazdan dolayı tıkanabilirler, bu da hastaneler, afet müdahale merkezleri, sığınaklar ve afet bölgeleri gibi kritik yerler arasında ulaşımın kesilmesine neden olur. Acil müdahale işlemlerini kolaylaştırmak için, yollardan enkazları mümkün olan en kısa sürede temizlemek önemlidir. Ayrıca, uzun vadede, atık yönetimi ve hasarlı yolların restorasyonu bölgenin geri kazanılması adına önemli faaliyetlerdir. Bu tezde, afetten sonraki ilk 72 saat gibi acil müdahale aşamasına odaklanıyoruz ve enkaz temizleme kararlarını optimize etmeyi amaçlıyoruz. Öncelikle, afet sonrası yol temizleme problemini, engellenen yolların temizlenmesinden sorumlu kişi ya da kurumların rotasını belirlemek için hızlı ve etkili bir yöntem sağlamak amacıyla inceliyoruz. Sorun, depoda başlayan ve tüm kritik yerleri ziyaret eden birlikler için bir rota bulmak. Amaç, bir düğümün gecikmesinin depodan o düğüme giden seyahat süresi olarak tanımlandığı kritik düğümlerin toplam gecikmesini en aza indirmektir. Literatürde bu problem için matematiksel bir model geliştirilmiştir. Bununla birlikte, yediden fazla kritik düğüme sahip gerçek hayattaki durumlar için, bu kesin formülasyon sorunu 3 saatlik bir limitte en iyi şekilde çözemez. Kısa bir çalışma süresinde optimale yakın bir çözüm bulmak için, dönüştürülmüş bir ağdaki karma bir tamsayı programını çözen ve optimalite farkını yorumlamak için daha düşük sınırlayıcı bir yöntem olan bir sezgisel yöntem geliştiriyoruz. Alternatif olarak, Greedy Randomized Adaptive Search Procedure (GRASP) ve Variable Neighborhood Search (VNS) kombinasyonuna dayanan bir metasezgisel algoritma geliştirirdik. Hem sezgisel hem de metasezgisel algoritmaları İstanbul verileri üzerinde test ediyor ve en iyi veya en iyiye yakın çözümlerin saniyeler içinde elde edildiğini gösteriyoruz. Algoritmalarımızı literatürdeki mevcut çalışmalarla da karşılaştırıyoruz. Son olarak, toplam gecikme ile maksimum gecikme arasındaki dengeyi gözlemlemek adına bir analiz yapıyoruz. İkinci olarak, sorunumuza birden fazla iş birliği, birden fazla depo ve bir düğüm alt grubunu ziyaret etmeyi (tüm düğümleri ziyaret etmek yerine) dahil ediyoruz. Bildiğimiz kadarıyla, bu sorun (ve asgari gecikmenin amaç fonksiyonu olmasıyla) bu genellemeyle literatürde incelenmemiştir. Yeni bir çok seviyeli ağ modelini tanıtıyoruz. Matematiksel modeli iki veri seti kategorisiyle test ediyoruz: 1) İstanbul, Türkiye'de bulunan gerçek bir veri setine dayanan Kartal verileri. 2) önerilen matematiksel modelin gücünü doğrulamak için tüm parametrelerin rastgele olarak değerlendirildiği rastgele veri setleri. Bulgularımız matematiksel modelin tüm örnekleri makul hesaplama zamanlarında (ortalama 15 dakikadan az) en iyi şekilde çözebildiğini kanıtlamaktadır. Bu algoritmalar afet sonrası aşamada çalıştırılması gerektiğinden, hesaplama zamanlarının kısa olması çok önemlidir ve bu müdahale aşamasında yeni bilgiler elde edilirken sorunun gerçek zamanlı olarak çözülmesini sağlar. Ayrıca, önerilen tüm algoritmalardaki küçük ve makul hesaplama zamanları göz önüne alındığında, afet yönetimi ile ilgili herhangi bir kuruluşun, bir felaketten kaynaklanan olumsuz etkileri azaltmak için bu metodolojileri kullanabileceği unutulmamalıdır.
Özet (Çeviri)
After a natural disaster, roads and bridges can be damaged or blocked by debris, causing inaccessibility between critical locations such as hospitals, disaster response centers, shelters and disaster-struck areas. To facilitate immediate response operations, it is essential to clear debris from the roads in the shortest time possible. Moreover, in the longer term, management of waste and restoration of damaged roads are important activities for recovery of the region. In this thesis, we focus on the immediate response phase, such as the first 72 hours after the disaster and aim to optimize debris clearance decisions. First, we study the post-disaster road clearing problem with the aim of providing a fast and effective method to determine the route of a work troop responsible for clearing blocked roads. The problem is to find a route for the troop that starts at the depot and visits all of the critical locations. The objective is to minimize the total latency of critical nodes, where the latency of a node is defined as the travel time from the depot to that node. A mathematical model for this problem has already been developed in the literature. However, for real-life instances with more than seven critical nodes, this exact formulation cannot solve the problem optimally in a 3-hour limit. To find a near-optimal solution in a short running time, we develop a heuristic that solves a mixed integer program on a transformed network and a lower bounding method to evaluate the optimality gaps. Alternatively, we develop a metaheuristic based on a combination of Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Search (VNS). We test both the matheuristic and the metaheuristic on Istanbul data and show that optimal or near-optimal solutions are obtained within seconds. We also compare our algorithms with existing work in the literature. Finally, we conduct an analysis to observe the trade-off between total and maximum latency. Second, we incorporate multiple work troops, multiple depots and visiting a subset of nodes (instead of visiting all nodes) in our problem. To the best of our knowledge, this problem with this generalization (and with the objective function of minimum latency) has not been investigated in the literature. We introduce a novel multi-level network model. We test the mathematical model with two categories of data sets: 1) Kartal data which is based on a real data set, located in Istanbul, Turkey. 2) random data sets in which all parameters are considered randomly to verify the strength of the proposed mathematical model. Our findings testify that the mathematical model is able to solve all instances optimally within reasonable computational times (less than 15 minutes in average). Since these algorithms should be executed in the post-disaster stage, having short computational times is crucial and enables the problem to be resolved in real-time as new information is obtained over the response stage. Note that given the small and reasonable computational times in all proposed algorithms, any organization associated with disaster management can employ these methodologies to mitigate the negative impacts caused by a disaster.
Benzer Tezler
- Bayesian methods for real-time pitch tracking
Gerçek zamanlı nota takibi için Bayesçi yöntemler
UMUT ŞİMŞEKLİ
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ TAYLAN CEMGİL
- Secure and coordinated beamforming in 5G and beyond systems using deep neural networks
5G ve ötesi sistemlerde derin sinir ağları kullanarak güvenli ve koordineli hüzmeleme
UTKU ÖZMAT
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MEHMET AKİF YAZICI
DR. ÖĞR. ÜYESİ MEHMET FATİH DEMİRKOL
- Development and testing novel guidance algorithms for visual drone interception
Görsel dron yakalama için yeni güdüm algoritmalarının geliştirilmesi ve testi
AHMET TALHA ÇETİN
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMRE KOYUNCU
- IP trafiğinin optik şebekeler üzerinden taşınması
IP packet transmission over optical networks
NERGİN ÖZGÜR
Yüksek Lisans
Türkçe
2000
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. GÜNSEL DURUSOY
- Converging towards FPGA specific design decisions made on a list scheduling algorithm for effective execution
Başlık çevirisi yok
ILKIN ALIYEV
Yüksek Lisans
İngilizce
2021
Elektrik ve Elektronik MühendisliğiÖzyeğin ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN FATİH UĞURDAĞ
DOÇ. DR. ALİ AKOĞLU