Arc routing problems to restore connectivity of a road network
Karayolu ağında bağlantıların tekrar sağlanması için ayrıt rotalama problemleri
- Tez No: 397223
- Danışmanlar: DOÇ. DR. FATMA SİBEL SALMAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 100
Özet
Doğal afetler sonucunda karayollarında meydana gelen hasarlar ve yollara yığılan enkazların etkisiyle yollar kapanabilmektedir. Bunun sonucunda bazı bölgelere ulaşım imkansız hale gelebilir. Afet sonrası acil müdahale safhasında yolların en kısa sürede açılması ve etkilenen bölgelere ulaşımın sağlanması gereklidir. Bu çalışmada yolları açmak üzere yola çıkarılacak olan iş makinaları ve personelden oluşan grubun rotasını belirlemek üzere farklı amaç fonksiyonlarına sahip üç ayrıt rotalama problemi üzerinde çalışılmıştır. İlk problemde tüm ulaşım ağındaki noktaları tekrar birbirine bağlı hale getirmek için geçen zamanı en aza indirmek hedeflenmiştir. İkinci problemde belirli bir süre içerisinde birbirine bağlantısı sağlanan izole bölgelerden toplanan ödülün en çok olması hedeflenmiştir. Üçüncü problemde ise amaç kritik tedarik ve talep noktalarını en kısa sürede bağlı hale getirmektir. Bu problemlerin NP-zor olduğu ispatlanmıştır. Her bir problem için bir karışık tam sayılı programlama modeli geliştirilmiş ve ilk iki problem için de Değişken Komşuluk Arama meta-sezgiseli çerçevesinde ikişer sezgisel algorıtma geliştirilmiştir. Sezgisel algoritmaların ve model çözümlerinin karşılaştırılması için İstanbul karayolunu çeşitli hasar senaryoları altında inceleyen örnekler yaratılmıştır. Ayrıca literatürdeki çeşitli Köylü Postacı Problemi verileri kendi problemlerimize adapte edilmiştir. Bu veriler ile yapılan hesaplamalı deneyler sonucunda sezgisellerin denenen örneklerin çoğunda en iyi ya da en iyiye yakın çözümler verdiği görülmüştür. Bu problemlerin ve çözüm metodlarının afet sonrası karar desteği için nasıl kullanılabileceği tartışılmış ve problem çözümleri karşılaştırılmıştır. İkinci problemin erişim sağlanması için toplam bekleme süresini ilk probleme göre azalttığı gözlemlenmiştir.
Özet (Çeviri)
Natural disasters cause destructive effects. Road networks can be damaged or blocked by debris; bridges and viaducts may collapse. This may enforce closing of some road sections and even render some parts of the road network disconnected. In the immediate disaster response phase, to facilitate emergency transportation, the problematic roads should be cleared or repaired and the road clearing team(s) should be dispatched to the affected areas in the most efficient way. We study emergency road restoration with the aim to reconnect a disconnected road network in the shortest time after a disaster. We address three arc routing problems that find the route of a work-troop dispatched to clear blocked roads and achieve connectivity. In the first problem, we minimize the time to reconnect the network while in the second problem, we maximize the total prize from components that are reconnected within a time limit. In the third problem, we reconnect critical supply and demand points. We prove that these problems are NP-hard. For each problem, we develop an MIP formulation. For the first two problems, we propose two heuristic algorithms based on Variable Neighborhood Descent (VND) framework. We compare the performance of the heuristics with MIP solutions on a case of Istanbul and instances adapted from the literature with up to 400 nodes and 600 edges, and analyze the solution characteristics. We achieve near-optimal or optimal solutions much faster than Cplex in most tested instances; thereby justifying the use of the heuristics in the post-disaster stage. We discuss how these problems can be utilized in a post-disaster decision support system and compare solutions obtained by solving the second problem consecutively over a time frame. This analysis shows the benefit of using the second problem in terms of total waiting time of people until they get access.
Benzer Tezler
- 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
VAHID AKBARIGHADIKOLAEI
Doktora
İngilizce
2016
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği ve Operasyon Yönetimi
DOÇ. DR. FATMA SİBEL SALMAN
- Logistics planning for restoration of network connectivity after a disaster
Afet sonucu ağ bağlanırlığının sağlanması için lojistik planlama
AYŞE NUR KİBAR
Yüksek Lisans
İngilizce
2013
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. FATMA SİBEL SALMAN
- Single phase autoreclosing in 735 KV transmission system
735 KV iletim sisteminde tek fazlı otomatik tekrar kapama
KAVEH SALEHGHADIMI
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ÖMER USTA
- Drone ayrıt rotalama problemleri ve metasezgisel çözüm yaklaşımı
Drone arc routing problems and metaheuristic solution approach
İSLAM ALTIN
Doktora
Türkçe
2022
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. AYDIN SİPAHİOĞLU
- Belirsizlik altında hiyerarşik çinli postacı problemi ve çözüm yaklaşımları
Hierarchical chinese postman problem under uncertainty and solution approaches
ÖZLEM ÇOMAKLI SÖKMEN
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiAtatürk ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA YILMAZ