An integrated post-disaster assessment routing problem for collecting damage information with drones

Abstract

In this study, we focus on post-disaster damage assessment operations supported by a set of drones when the disaster-affected area is divided into grids, and grids are clustered based on their attributes. We propose a two-phase methodology to assess the damage status of the built environment in grids. Specifically, given a set of drones and a limited time for an assessment interval, the first phase addresses the problem of determining the grids to scan by each drone and the sequence of visits to the selected grids. We aim to maximize the total priority score collected from the scanned grids while satisfying the predefined targeted coverage ratio. In the second phase, we aim to predict the damage status of unscanned grids by using the cluster-based information obtained from the scanned grids at the end of the assessment interval. Nevertheless, the damage status of all grids may not be assessed (by scanning or prediction) after one interval; therefore, these two phases iterate until all grids are evaluated. For the problem solved in the first phase, we adapt two formulations from the literature developed for electric vehicle routing problems. We also develop a Variable Neighborhood Descent based heuristic which can find high-quality solutions rapidly. We evaluate the performance of the alternative formulations and the heuristic in a variety of instances. For the second phase, we devise a novel imputation method and different imputation policies to predict the damage status of the unscanned grids. We also define several performance metrics to measure the efficiency and effectiveness of the proposed imputation policies. Our analyses demonstrate that using the proposed imputation policies improve the system performance as they induce a rapid detection of the damaged areas.Bu çalışma, bir dizi insansız hava aracı (dron) tarafından desteklenen afet sonrası hasar değerlendirme operasyonlarına odaklanmaktadır. Afetten etkilenen bölge gridlere ayrılarak ele alınmış ve bu gridler özelliklerine göre kümelenmiştir. Gridlerde bulunan yapıların hasar durumlarını belirlemek için iki aşamalı bir metodoloji önerilmektedir. İlk aşama temel olarak bir dizi dron ile sınırlı bir değerlendirme süresi içinde taranacak gridleri seçme ve seçilen gridlerin taranma sıralarını belirleme sorununu ele alır. Bu aşamadaki amaç, her bir küme için önceden belirlenmiş olan kapsama oranını karşılarken, taranan gridlerden elde edilen toplam öncelik puanlarını maksimize etmektir. İkinci aşamada ise, bir değerlendirme aralığından sonra taranan gridlerden elde edilen küme bazlı hasar bilgileri kullanılarak, taranmamış gridlerdeki hasar durumlarının tahmin edilmesi hedeflenmiştir. Ancak bütün gridlerdeki hasar durumlarının belirlenmesi (taranarak veya tahmin edilerek) tek bir değerlendirme aralığı sonunda mümkün olmayabilir. Bu nedenle önerilen iki aşama tüm gridlerdeki hasar seviyeleri belirlenene kadar yinelenir. İlk aşamada çözülen sorun için, literatürdeki elektrikli araç yönlendirme problemleri için geliştirilen iki matematiksel model uyarlanmıştır. Ayrıca, daha hızlı bir şekilde yüksek kaliteli çözümler elde edebilen bir sezgisel algoritma önerilmiştir. Matematiksel modellerin ve sezgisel algoritmanın performansları çeşitli örnekler üzerinde test edilmiştir. İkinci aşama için, taranmamış gridlerdeki hasar durumlarını tahmin etmekte kullanılmak üzere çeşitli politikalardan oluşan özgün bir veri atama yöntemi önerilmiştir. Ayrıca, bu politikaları verimlilik ve etkinlik açısından değerlendirmek için çeşitli performans ölçütleri tanımlanmıştır. Yapılan analizler önerilen politikaların kullanılmasının hasarlı alanların daha hızlı tespit edilmesini sağlayarak sistem performansını iyileştirdiğini göstermektedir.