Afet sonrasında yolları açmak için çok-araçlı ayrıt rotalama problemleri

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.