Creating an evacuation plan during an emergency by coordinating vehicles

Abstract

As disaster relief operations required quick and e ective service, especially evacuating victims from disaster area will be more problematic. In this paper, the problem is about evacuating the people who need service after a disaster by using best routes. The problem based on the Pickup and Delivery Problem with consideration of critical operational constraints. The problem is NP Hard and exact proposal for the solution of real life problem is not achievable. The best routes which only contain generalized Pickup and Delivery Problem is based on the established Traveling Salesman Problem(TSP) methodology. For our research, we have two types of patients and instead of create an evacuation plan with one vehicle, we developed our approach for two vehicle with two end points. The vehicles can carry all types of patient moreover, the patient locations can contain both type of patients so, some points visited twice. For minimize the total transportation time, we regulated evacuation plan as the vehicles can help each other and we proposed a change point for swap the patients to carry their own end points. So, our solution methodology is provide new routes for determine a switch point. Especially, when we consider these critical operational constraints mentioned above the TSP can be insu cient. Thus, to make this problem more practicable, we created initial routes by using Christo des' Algorithm then presented a mathematical model which applied our critical elimination process on the Hamiltonian paths that we acquired in the rst phase. This implementation improved the solution of TSP. We also described two e ective and fast heuristic algorithms. As a result of these heuristics, we improved the quality and e ciency of TSP solution and the best routes that contained the critical constraints.

Afet sonrası yardım operasyonlarının hızlı ve etkili olması gerekmektedir, özellikle kurtarılması gereken ki¸siler yaralı olduğu durumlarda operasyonlar daha problemli olabilir. Bu araştırmada, problem afet sonrasında yardıma ihtiyacı olan bireylerin kurtarılması için en iyi rotalamanın oluşturulmasıdır. Problemin konusu Toplama ve Dağıtım Problemini göz önünde bulundurarak kritik operasyonel kısıtlar üstünde durmaktadır. Bu problem NP Hard tipi bir problem olup, kesin çözümü gerçek dünya problemi bazında yapılması çok zordur. Klasik Toplama ve Dağıtım Problemi için en iyi sonucu veren rotalar Gezen Satıcı Problemini (TSP) methodolojisi kullanılarak bulunur. Bu çalışmada iki tip felaketzede bulunmaktadır, bir araba ile kurtarma planı yapmak yerine, biz ¸çözümümüzü iki son nokta i¸cin iki araba ile geliştirdik. Araçlar her tip kurbanı taşıyabilmektedir aynı zamanda talep noktaları iki tip talebi de barındırdığından bazı noktalara iki kez uğranmaktadır. Toplam kurtarma süresini minimize etmek i¸cin kurtarma planını araçların birbirine yardım etmesine izin verecek şekilde düzenledik ve kurbanları gidecekleri son noktaya bırakabilmesi adına bir değiştirme noktası belirledik. Böylece, çözüm metodolojimizi değiştirme noktasını belirleyerek yeni rotaları düzenler. Özellikle bahsedilen kritik operasyonlar göz önüne alındığında TSP metodolojisi tek başına yeterli olmaz. Çözümü daha pratik hale getirmek için, Christofides Algoritması kullanılarak ilk rotalar elde edilir. Kritik eleme operasyonu için ilk adımda oluşturulan Hamiltonian rotalara matematiksel model uygulanır. Bu uygulama ile birlikte TSP den elde edilen çözüm geliştirilmiş olunur. Ayrıca sonucu hem çözüm süresi bakımından hem de kalitesi açısından daha da iyileştirmek için kritik eleme kısıtlarını içeren iki tane sezgisel algoritma oluşturulmuştur.