Multi-vehicle arc routing problems to restore post-disaster network connectivity
Afet sonrasında yolları açmak için çok-araçlı ayrıt rotalama problemleri
- Tez No: 456341
- Danışmanlar: DOÇ. 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: 2016
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği ve Operasyon Yönetimi
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 106
Özet
After a natural disaster roads can be damaged or blocked by debris, while bridges and viaducts may collapse. This commonly observed hazard causes some road sections to be closed and may even disconnect the road network. In the immediate disaster response phase work teams are dispatched to open a subset of roads to reconnect the network. Closed roads are traversable only after they are unblocked/cleared by one of the teams. The main objective is to provide an efficient solution method to generate a synchronized work schedule for the road clearing teams so that none of the closed roads are traversed unless their unblocking/clearing procedure is finished. We address two arc routing problems that find the route of multiple work-troops dispatched to clear blocked roads and achieve connectivity. In the first problem, we minimize the time to reconnect the network entirely. In the second problem, we maximize the total prize gained by reconnecting disconnected network components within a specified time limit. For each problem, we develop an exact Mixed Integer Programming (MIP) formulation. Furthermore, for the first problem, we propose a matheuristic that is based on an MIP-relaxation and a local search algorithm. We prove that the optimality gap of the relaxation solution is bounded by K times the lower bound obtained from the relaxed model, where K is the number of teams. For the second problem, we develop a matheuristic method. The matheuristic solves single vehicle problems sequentially with updated prizes. To obtain an upperbound, we first relax the timing elements in the exact formulation and then solve its relaxed MIP, which decomposes into single vehicle problems by Lagrangian Relaxation. We show the effectiveness of the proposed methods computationally on both random Euclidean and three distinct Istanbul road network data generated with respect to predicted earthquake scenarios.
Özet (Çeviri)
Doğal felaketlerden sonra köprüler ve viyadükler çökebilirken, yollar hasar görebilir veya enkazla kaplanabilir. Bu sık görülen tehlike bazı yol bölümlerinin kapanmasına ve hatta yol ağının bağlantısının kesilmesine neden olur. Afet müdahale aşamasında, çalışma ekipleri, yol ağını yeniden bağlamak ve ulaşıma açmak için yolların bir alt kümesini açmak üzere işe gönderilir. Kapalı bir yoldan, bir takım tarafından bu yol açılmadan geçilemez. Bu çalışmanın amacı, yol temizleme ekipleri için senkronize edilmiş bir çalışma programı üretecek etkin bir çözüm yöntemi sunmaktır. Bloke olmuş yolları temizlemek ve tekrar bağlantı sağlamak için gönderilen birden çok iş ekibinin rotalarını bulan iki ayrıt rotalama problemi ele alınmıştır. Birinci problemde amaç ağın tamamen yeniden bağlanması için gereken zamanı enküçüklemektir. İkinci problemde ise amaç, bağlantısı kesilen ağ bileşenlerini belirli bir süre içinde tekrar bağlayarak kazanılan toplam ödülü enbüyüklemektir. Her bir problem için tam sonuç veren bir karışık tam sayılı programlama (KTP) modeli geliştirilmiştir. İlk problem için KTP modelinin bir gevşetmesinden olurlu çözüm üreten bir mat-sezgisel önerilmiştir. Gevşetme çözümünün optimalite boşluğunun, K'nın takım sayısı olduğu durumda, gevşetilmiş modelden elde edilen alt sınırın en fazla K katı olduğu kanıtlanmıştır. İkinci problem için ise, bir mat-sezgisel yöntem geliştirilmiştir. Bu yöntem, tek araç problemlerini sırasıyla güncellenmiş ödüller ile çözer. Bir üst sınır elde etmek için, önce kesin formülasyondaki zamanlama unsurları gevşetilip, daha sonra Lagrange gevşetme yöntemi ile tek araç problemlerine dönüşen gevşetilmiş KTP çözülür. Önerilen yöntemlerin etkinliği, sistematik şekilde rasgele oluşturulan çeşitli büyüklüklerdeki Öklidyen veriler ve tahmini deprem senaryolarına göre üretilen üç farklı İstanbul yol ağı verisi üzerindeki hesaplamalı deneyler ile gösterilmiştir.
Benzer Tezler
- A New neuristic procedure for capacitated arc routing problems
Başlık çevirisi yok
HAYRULLAH HAYRİ FEYZİOĞLU
Yüksek Lisans
İngilizce
1993
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İLHAN OR
- مسيريابي و زمانبندي بهینه وسايل نقليه برای جمع آوري سبز پسماندهاي شهری
Yeşil belediye katı atık toplama faaliyetleri için araç rotalama ve çizelgeleme
ERFAN BABAEE TIRKOLAEE
Doktora
Farsça
2019
Endüstri ve Endüstri MühendisliğiMazandaran University of Science and TechnologyEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. IRAJ MAHDAVI
PROF. DR. MIR MEHDI SEYYED ESFAHANI
PROF. DR. GERHARD WILHELM WEBER
- Transportation network design models with costefficiency, capacity balancing, and resilience
Başlık çevirisi yok
YUSUF SECERDİN
- Pvd tekniği kullanılarak farklı seramik malzemelerle kaplanmış segmanların aşınma davranışlarının incelenmesi
Investigation of the wear behavior of piston rings coated with different ceramic materials by using pvd technique
DİLEKNUR EVRENSEL
Yüksek Lisans
Türkçe
2021
Metalurji MühendisliğiOndokuz Mayıs ÜniversitesiMetalurji ve Malzeme Mühendisliği Ana Bilim Dalı
DOÇ. DR. SEVİM ALIŞIR
- An optimization model to control the flow of relief commodities in humanitarian supply chain under uncertainty
Belirsiz koşullarda insani yardım tedarik zinciri malzeme akışını kontrol etmede optimizasyon modeli
ISRAA ISMAIL
Doktora
İngilizce
2021
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ESRA BAŞ