Geri Dön

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

  1. Tez No: 397223
  2. Yazar: MAZIAR KASAEI ROODSARI
  3. Danışmanlar: DOÇ. DR. FATMA SİBEL SALMAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2015
  8. Dil: İngilizce
  9. Üniversite: Koç Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2016

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği ve Operasyon Yönetimi

    DOÇ. DR. FATMA SİBEL SALMAN

  2. 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

    İngilizce

    2013

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. FATMA SİBEL SALMAN

  3. Single phase autoreclosing in 735 KV transmission system

    735 KV iletim sisteminde tek fazlı otomatik tekrar kapama

    KAVEH SALEHGHADIMI

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖMER USTA

  4. 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

    Türkçe

    2022

    Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. AYDIN SİPAHİOĞLU

  5. 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

    Türkçe

    2021

    Endüstri ve Endüstri MühendisliğiAtatürk Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA YILMAZ