GEZGİN SATICI PROBLEMİ (TSP) YAKLAŞIMIYLA AFET YARDIM ROTALARININ GENETİK ALGORİTMALAR (GA) KULLANILARAK OPTİMİZASYONU
Author :
Abstract
Afet sonrası yardım dağıtım operasyonları, sınırlı zaman dilimi içerisinde çok sayıda ihtiyaç noktasına etkili müdahale gerektiren, yüksek belirsizlik içeren ve çok kriterli karar verme süreçlerini içeren karmaşık optimizasyon problemleridir. Bu çalışma, bu problemi klasik Gezgin Satıcı Problemi (Traveling Salesman Problem, TSP) paradigmasıyla modellemekte ve çözüm yöntemi olarak Genetik Algoritmalar (Genetic Algorithms, GA) gibi sezgisel bir arama algoritmasını uygulamaktadır. TSP’nin deterministik çözüm algoritmaları büyük ölçekli problem boyutlarında hesaplama açısından elverişsiz hâle gelirken, GA gibi evrimsel optimizasyon teknikleri, kabul edilebilir hata paylarıyla kısa sürede yüksek kaliteli çözümler sunmaktadır. Uygulama sahası olarak, Türkiye’nin deprem riski taşıyan bölgelerinden biri olan Muğla ili Bodrum ilçesi seçilmiş; toplam 12 kritik yardım noktası dikkate alınarak, dağıtım rotalarının optimizasyonu gerçekleştirilmiştir. Modelde, yardım rotalarının değerlendirilmesinde kullanılan uygunluk (fitness) fonksiyonu, çok ölçütlü olarak yapılandırılmıştır. Fonksiyonda yer alan bileşenler şunlardır: (i) toplam seyahat mesafesi, (ii) toplam ulaşım süresi, (iii) yardım noktalarının öncelik katsayılarına bağlı olarak tanımlanan gecikme cezası. Bu fonksiyon, ağırlıklı çok amaçlı bir optimizasyon yaklaşımı ile formüle edilmiş ve algoritmanın hedef fonksiyonu hâline getirilmiştir. Çalışma kapsamında, önerilen GA modeli klasik brute-force (BF) yaklaşımıyla karşılaştırılmış; performans ölçütü olarak hesaplama süresi (ms), optimal rotaya yakınlık oranı (% LCS benzerliği), ve çözüm kalitesi kullanılmıştır. Sonuçlar, GA’nın özellikle yüksek hedef nokta sayılarında (N ≥ 9) brute-force yöntemine göre eksponansiyel ölçekte daha hızlı çözümler üretebildiğini; aynı zamanda maksimum %18 sapma oranı ile optimal çözümlere yüksek oranda yaklaşabildiğini göstermektedir. Bu çalışma afet lojistiği bağlamında TSP temelli dağıtım problemlerine sezgisel algoritmalarla yaklaşmanın stratejik faydasını ortaya koymakta; özellikle gerçek zamanlı karar destek sistemlerinde GA tabanlı rota planlama modellerinin uygulanabilirliğini, ölçeklenebilirliğini ve adaptif esnekliğini kanıtlamaktadır.
Keywords
Abstract
Disaster relief distribution operations are complex optimization problems that involve high uncertainty, strict time constraints, and multi-criteria decision-making processes. This study addresses the optimization of post-disaster aid delivery routes by modeling the problem within the framework of the Traveling Salesman Problem (TSP) and solving it using a heuristic search technique—Genetic Algorithms (GA). As exact solution methods for TSP become computationally infeasible for large-scale instances, GA offers high-quality solutions within acceptable error margins and significantly reduced computation time. The case study focuses on Bodrum, a district in Turkey’s earthquake-prone Muğla province, considering 12 critical aid delivery points. A multi-objective fitness function was designed based on total travel distance, total delivery time, and delay penalties weighted by the priority levels of aid points. The performance of the GA-based model was compared to the classical brute-force (BF) approach using metrics such as computation time, solution similarity to the optimal route (% LCS), and overall quality. Results show that the GA outperforms BF in scalability and speed, particularly for instances with N ≥ 9, achieving near-optimal results with up to 18% deviation. These findings underline the strategic utility of GA-based routing models in disaster logistics, emphasizing their real-time applicability, scalability, and adaptability for effective decision support systems.
