Creating an evacuation plan during an emergency by coordinating vehicles

Abstract

Afet sonrası yardım operasyonlarının hızlı ve etkili olması gerekmektedir, özelliklekurtarılması gereken ki¸siler yaralı olduğu durumlarda operasyonlar daha problemliolabilir. Bu araştırmada, problem afet sonrasında yardıma ihtiyacı olan bireylerinkurtarılması için en iyi rotalamanın oluşturulmasıdır. Problemin konusu Toplamave Dağıtım Problemini göz önünde bulundurarak kritik operasyonel kısıtlar üstündedurmaktadır. Bu problem NP Hard tipi bir problem olup, kesin çözümü gerçek dünyaproblemi bazında yapılması çok zordur. Klasik Toplama ve Dağıtım Problemi içinen iyi sonucu veren rotalar Gezen Satıcı Problemini (TSP) methodolojisi kullanılarakbulunur. Bu çalışmada iki tip felaketzede bulunmaktadır, bir araba ile kurtarmaplanı 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 talebide barındırdığından bazı noktalara iki kez uğranmaktadır. Toplam kurtarma süresiniminimize 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 birdeğ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 halegetirmek için, Christofides Algoritması kullanılarak ilk rotalar elde edilir. Kritikeleme operasyonu için ilk adımda oluşturulan Hamiltonian rotalara matematikselmodel 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ındandaha da iyileştirmek için kritik eleme kısıtlarını içeren iki tane sezgisel algoritmaoluşturulmuştur.

As disaster relief operations required quick and effective service, especially evacuatingvictims from disaster area will be more problematic. In this paper, the problem isabout 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 criticaloperational constraints. The problem is NP Hard and exact proposal for the solutionof real life problem is not achievable. The best routes which only contain generalizedPickup and Delivery Problem is based on the established Traveling SalesmanProblem(TSP) methodology. For our research, we have two types of patients andinstead of create an evacuation plan with one vehicle, we developed our approach fortwo 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 visitedtwice. For minimize the total transportation time, we regulated evacuation plan asthe vehicles can help each other and we proposed a change point for swap the patientsto carry their own end points. So, our solution methodology is provide new routesfor determine a switch point. Especially, when we consider these critical operationalconstraints mentioned above the TSP can be insufficient. Thus, to make this problemmore practicable, we created initial routes by using Christofides' Algorithm thenpresented a mathematical model which applied our critical elimination process on theHamiltonian paths that we acquired in the first phase. This implementation improvedthe solution of TSP. We also described two effective and fast heuristic algorithms. Asa result of these heuristics, we improved the quality and efficiency of TSP solutionand the best routes that contained the critical constraints.