Planning of emergency medical service stations and ambulances

Abstract

Bu tezde, acil yadım istasyonlarının planlanması için Yedek Çift Kapsama Modeli (YÇKM) ele alınmıştır. Literatürde kapsamlı bir şekilde ele alınan Enbüyük Kapsama Modeli'ni temel alan bu model, acil yardım konusunda iki tip hizmet gerektirmektedir. Modelde amaç, açılabilecek kısıtlı sayıda acil yardım istasyonları ile t1 ve t2 (t1 < t2) süreleri içinde farklı bölgelerde yer alan en az birer istasyon tarafından kapsanan nüfusun enbüyüklenmesidir. Bu modelin önerilmesindeki hedef, acil yardım hizmetine ihtiyaç duyan talep noktalarına cevap verebilecek yakın bir ambulansın olmaması durumunda daha uzak mesafeden yedek servis sağlamaktır. Büyük boyutlu problemler için modelin çözümü zor olduğundan, anlamlı süre içinde iyi sonuçlar bulabilmek amacıyla Tabu Arama (TA) algoritması önerilmiştir. Karşılaştırma için üç farklı başlangıç çözümü bulma tekniği uygulanmıştır: rassal, miyop ve doğrusal programlama gevşetmeye dayalı sezgisel yöntem. Önerilen yöntemin etkinliğini ölçmek amacıyla rassal üretilen farklı büyüklükteki çok sayıda veri seti ve farklı istasyon sayısı limiti ile deneysel çalışma yapılmıştır. Önerilen TA algortiması, CPLEX 11.0 ile önceki sürümlerine göre çok yüksek performansa sahip OPL Studio 5.5 kullanılarak elde edilen sonuçlar ile kıyaslanmıştır.Tezde ayrıca, YÇKM'nin uzantısı olarak Çok Dönemli Yedek Çift Kapsama Modeli (ÇDYÇKM) önerilmiştir. Bu modelde, ele alınan her dönemde açılacak istasyon sayısı ile bir dönemde açılan istasyonların sonraki herhangi bir dönemde kapanmaması kısıtları sözkonusudur. ÇDYÇKM'yi etkin bir şekilde çözmek için, YÇKM için tanımlanan başlangıç çözümü bulma teknikleri ile TA algoritması bu modele de uygulanmıştır. Rassal verilere dayalı olarak gerçekleştirilen deneysel çalışma ile YÇKM'de olduğu gibi ÇDYÇKM için de OPL Studio 5.5 ile bulunan çözümlerle kıyaslandığında TA'nın çok kısa sürede iyi sonuçlar bulunduğu görülmüştür.Sonuç olarak hızlı ve etkin olduğu kanıtlanan TA, İstanbul Büyükşehir Belediyesi, İtfaiye Daire Başkanlığı bünyesindeki Acil Yardım ve Cankurtarma Müdürlüğü aracılığıyla elde edilen gerçek veriler kullanılarak İstanbul'da acil yardım istasyonlarının tek yıllık ve dört yıllık planlanması problemi için uygulanmıştır.

In this thesis, we address the Emergency Medical Service (EMS) stations location problem. Firstly, we propose a Backup Double Covering Model (BDCM) as a variant of the well-known Maximal Covering Location Problem where two types of service requests are fulfilled. The objective of the model is to maximize the total population serviced within t1 and t2 minutes (t1 < t2) using two distinct EMS stations where the total number of stations is limited. Our aim in doing so is to provide a backup station in case no ambulance is available in the closer station. Since this problem is intractable for large-scale instances we propose a Tabu Search (TS) approach to find good solutions in reasonable computation time. Three initialization approaches are utilized for comparison: random, a steepest-ascent algorithm, and an LP relaxation-based heuristic. In order to test the effectiveness of the proposed method, we conduct an extensive experimental study on a large number of randomly generated data set with different sizes and number of stations. We observe that the TS algorithm provides good results fast in comparison with the solutions obtained using the optimization software OPL Studio 5.5 equipped with ILOG CPLEX 11.0. Secondly, we propose the multi-period extension of BDCM (MPBDCM). This model requires a given number of stations to be opened in each period where the stations opened in any period cannot be closed in the subsequent periods. To solve this problem efficiently, we adopt a similar TS approach using the same initialization methods as in BDCM. Our extensive experimental study on randomly generated data sets reveal that the TS approach provides good results fast compared to the results obtained by using OPL Studio 5.5. Finally, we apply the TS approaches for planning both the single- and multi-period EMS stations location problem in Istanbul on the data obtained from the Directorate of Instant Relief and Rescue at the Istanbul Metropolitan Municipality.