پژوهش های سنجش از دور و اطلاعات مکانی

دوفصلنامه علمی

شماره جاری

بر اساس شماره‌های نشریه

بر اساس نویسندگان

بر اساس موضوعات

نمایه نویسندگان

نمایه کلیدواژه ها

درباره نشریه

اهداف و چشم انداز

همکاران دفتر نشریه

اصول اخلاقی انتشار مقاله

پیوندهای مفید

پرسش‌های متداول

فرایند پذیرش مقالات

اطلاعات آماری نشریه

اخبار و اعلانات

آیین نامه ها و مصوبات

مقایسه الگوریتم های جستجوی ممنوع هدایت شونده و ژنتیک تو در تو، جهت حل مسئله مکان یابی-تخصیص ظرفیت دار در شرایط اضطراری

نوع مقاله : مقاله پژوهشی

نویسنده

گروه سنجش از دور و سیستم اطلاعات جغرافیایی، دانشکده منابع طبیعی و محیط زیست، دانشگاه آزاد اسلامی-واحد علوم تحقیقات، تهران، ایران

چکیده

پیشینه و اهداف: زلزله­ه ای شدید، موجب بروز صدمات جانی و مالی زیادی می­شود که با امدادرسانی سریع و به موقع، می­ توان از بروز بسیاری حوادث پس از سانحه، جلوگیری کرد. یکی از مسائل مهم در این زمینه، تخصیص بهینه‌ی مصدومان به مراکز درمانی است و این مسئله، دارای ماهیتی پویا و پیچیده بوده و با روش ­های ساده، قابل حل نمی­باشد. به‌کارگیری سامانه‌ی اطلاعات مکانی (GIS) در کنار روش­های بهینه ­سازی و شبیه­ سازی، این امکان را فراهم می­کند که بتوان یک روش مناسب برای تخصیص بهینه‌ی مصدومان زلزله، به مراکز درمانی یافت. مسئله‌ی تخصیص مصدومان زلزله به مراکز درمانی، در دسته‌ی مسائل تخصیص ظرفیت دار قرار دارد، که در این نوع مسائل با افزایش تعداد نقاط تقاضا و مراکز خدماتی، پیچیدگی و حجم محاسبات مسئله، به صورت نمایی افزایش می­ یابد. بنابراین، در  بسیاری از مواقع، استفاده از  روش­ های جستجوی مستقیم و قطعی در حل این نوع مسائل،  کارایی ندارد و باید از روش­ های ابتکاری مناسب برای حل بهینه‌ی آن‌ها، بهره برد. از سویی دیگر، به دلیل آن‌که داده‌های مکانی، در مسئله‌ی تخصیص مصدومان زلزله به مراکز درمانی، نقش مهمی دارند، بنابراین، می توان با یکپارچه نمودن و ترکیب سامانه‌ی اطلاعات مکانی با روش­های بهینه ­سازی موجود در جهت حل بهتر و ساده ­تر آن، حرکت کرد.
روش‌ها‌: در این تحقیق، فرض بر این است که در صورت وقوع زلزله، تعدادی از جمعیت ساکن در برخی از بلوک­های ساختمانی، مصدوم  شده و نیازمند کمک  خواهند بود که محل­های قرارگیری این جمعیت مصدوم، همان نقاط تقاضا است. بدین ترتیب، باید این مصدومان به مراکز درمانی فرستاده شوند که هر یک از آن‌ها، توانایی ارائه‌ی خدمات به تعداد مشخصی از این مصدومان را، دارا هستند. پارامتر بعدی، تعداد مراکز درمانی و ظرفیت آن‌ها برای ارائه‌ی خدمات درمانی می­باشد که در این تحقیق، ظرفیت مراکز درمانی کمتر از تعداد مصدومان، فرض شده است. در نهایت، با بهینه سازی تابع هدف، نسبتی از مصدومان در نقاط مختلف که باید توسط مراکز درمانی موجود و یا جدید، مورد پذیرش قرار گیرند، با استفاده از یک الگوریتم ژنتیک تو در تو، محاسبه می­شود. خروجی الگوریتم ژنتیک که مکان مراکز جدید را مشخص می­کند، با اطلاعات موجود که همان مکان مراکز موجود است، ترکیب شده و سپس به ‌عنوان پارامترهای ورودی الگوریتم جستجوی ممنوع هدایت شونده (SGTS)، برای تعیین بهترین تخصیص به‌کار می­رود.
یافته‌ها: جهت ارزیابی دقت الگوریتم ژنتیک و روش جستجوی ممنوع هدایت شونده، انحراف معیار، دقت و زمان پردازش، مورد ارزیابی قرار گرفته است که الگوریتم جستجوی ممنوع هدایت شونده در هر سه ارزیابی، عملکرد بهتری داشته است. نتایج، نشان می ­دهد که نسبت انحراف معیار روش پیشنهادی نسبت به الگوریتم ژنتیک  12/0 است و میانگین دقت روش جستجوی ممنوع هدایت شونده نسبت به الگوریتم ژنتیک، به‌طور میانگین 18% بهبود داشته است. همچنین، روش SGTS  7% ،سریع‌تر محاسبات را انجام داده است.
نتیجه‌گیری: با مقایسه‌ی مدت زمان حل بهینه‌ی مسئله‌ی تخصیص مصدومان زلزله به مراکز درمانی، می­توان نتیجه گرفت که روش جستجوی ممنوع هدایت شونده‌ی مکانی، در مدت زمان کمتری می­تواند به همگرایی برسد. بنابراین، ایجاد لیست انتخابی با استفاده از ساختار ارائه شده بر اساس تحلیل­های مکانی می­تواند در این زمینه، موثر باشد. روش جستجوی ممنوع هدایت شونده‌ی مکانی، دارای دقت بالاتری نسبت به روش ژنتیک  و همچنین، نتایج به‌دست آمده از روش جستجوی ممنوع هدایت­ شونده‌ی مکانی دارای استحکام بیشتری می­باشد. در حل مسائل مکان­یابی و تخصیص منابع، اگر هدف بهینه­سازی توامان هر دو مورد مکان­یابی و تخصیص باشد، الگوریتم­های ترکیبی برای حل بهینه‌ی توامان، توصیه می­شود. اگرچه این مطالعه، موفق به ارائه‌ی روش ترکیبی برای حل بهینه‌ی مسائل تخصیص ظرفیت­دار شده است، اما مطالعه در زمینه‌ی ترکیب روش­های فرا ابتکاری و مقایسه‌ی نتایج آن با روش پیشنهادی، توصیه می­ گردد.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Comparison of Spatially Guided Tabu Search and Nested Genetic Algorithms for Solving the Capacitated Location-Allocation Problem in Emergency Situations

نویسنده [English]

  • H. Aghamohammadi

Department of GIS and Remote Sensing, Faculty of Natural Resources and Environment, Islamic Azad University-Science and Research Branch, Tehran, Iran

چکیده [English]

Background and Objectives: Severe earthquakes cause a lot of human and financial damage, which was prevented from occurring after the accident with quick and timely relief. One of the important problems in this field is the optimal allocation of injured to medical centers, and these problems have a dynamic and complex nature and cannot be solved by simple methods. The use of geographic information systems (GIS) along with optimization and simulation methods makes it possible to find a method for optimally allocating injured to medical centers. The problem of allocation of earthquake-related injured to medical centers is in the category of capacity allocation problems, and in this type of problems, with the increase in the number of demand points and service centers, the complexity and volume of the problem calculations increases exponentially, so in many cases, it is not It is possible to use direct and definite search methods in solving this type of problems, and appropriate innovative methods should be used to solve them optimally.On the other hand, because data plays an important role in allocating injured to medical centers, it is possible to move towards a better and simpler solution by integrating and combining the spatial information system with optimization methods.
Methods: In this study, it is assumed that in the event of an earthquake in a number of building blocks, a number of people living in them will be injured and need help, and the locations of this injured population are the demand points. In this way, these injured should be sent to medical centers, each of which has the ability to provide services to a certain number of these injured. The next parameter is the number of medical centers and their capacity to provide medical services. In this research, the capacity of medical centers is assumed to be less than the number of injured people. Finally, by optimizing the objective function, a ratio of injured people at different points that should be accepted by existing or new treatment centers is calculated using a nested genetic algorithm. The output of the genetic algorithm that determines the location of the new centers is combined with the existing information, which is the location of the existing centers, and then it is used as the input parameters of the spatially guided tabu search (SGTS) algorithm to determine the best allocation.
Findings: In order to assess the accuracy of the genetic algorithm and SGTS method, the standard deviation, accuracy, and processing time have been evaluated, which SGTS method has performed better in all three assessment. The results show that the standard deviation ratio of the proposed method compared to the genetic algorithm is 0.12, and the average accuracy of SGTS method has improved by 18% on average compared to the genetic algorithm. Also, the SGTS method performed calculations 7% faster.
Conclusion: By comparing the processing time to optimally solve the problem of earthquake-related injured allocation to medical centers, it can be concluded that SGTS method can reach convergence in a shorter period of time. Therefore, creating a selection list using the structure provided based on spatial analysis can be effective in this field. The SGTS method is more accurate than the genetic algorithm, and the results obtained from this method are robust. For solving the capacitated location-allocation problem, if the objective of optimization is locating and allocating, then combined algorithms are recommended for optimally solving both. Although this study has succeeded to propose a combination method for the optimal solution of the capacitated location-allocation problem, it is recommended to conduct the combination of meta-heuristic methods and compare the results with the proposed method.

کلیدواژه‌ها [English]

  • Allocation
  • Earthquake-Related Injured
  • Genetic Algorithm
  • Geospatial Information System
  • Spatially Guided Tabu Search

COPYRIGHTS 
© 2023 The Author(s).  This is an open-access article distributed under the terms and conditions of the Creative Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) (https://creativecommons.org/licenses/by-nc/4.0/) 

مراجع
[1] Fan WH, Wang WK, Liang CK, Yang ML, Hsu WL, Shiau YC. Smart earthquake disaster prevention system. Sensors Mater. 2021; 33(42): 1231–1244.
[2] Ibrion M, Mokhtari M, Nadim F. Earthquake disaster risk reduction in Iran: Lessons and ‘Lessons Learned’’ from three large earthquake disasters-tabas 1978, Rudbar 1990, and Bam 2003. Int J Disaster Risk Sci. 2015; 6(4): 415–27.
[3] Zhuang J, Peng J, Zhu X, Huang W. Scenario-based risk assessment of earthquake disaster using slope displacement, PGA, and population density in the Guyuan region, China. ISPRS Int J Geo-Information. 2019; 8(2): 85.
[4] Zhang S, Yang K, Cao Y. GIS-Based Rapid Disaster Loss Assessment for Earthquakes. IEEE Access. 2019; 7: 6129–6139.
[5] Tanaka H, Shiiba N, Huang MC. Tsunami Impact Assessment and Vulnerability Index Development using Computable General Equilibrium (CGE) Model and Geographic Information System (GIS) - A Study on Mie Prefecture, Japan. J Integr Disaster Risk Manag. 2021; 11(1): 46–63.
[6] Yavuz Kumlu KB, Tüdeş Ş. Determination of earthquake-risky areas in Yalova City Center (Marmara region, Turkey) using GIS-based multicriteria decision-making techniques (analytical hierarchy process and technique for order preference by similarity to ideal solution). Nat Hazards. 2019; 96(3): 999–1018.
[7] Al-Sabbagh TA. GIS location-allocation models in improving accessibility to primary schools in Mansura city-Egypt. GeoJournal. 2022; 87(2): 1009–1026.
[8] Ryan SJ, Getz WM. A spatial location-allocation GIS framework for managing water sources in a savanna nature reserve. African J Wildl Res. 2005; 35(2): 163–178.
[9] Robin TA, Khan MA, Kabir N, Rahaman ST, Karim A, Mannan II, et al. Using spatial analysis and GIS to improve planning and resource allocation in a rural district of Bangladesh. BMJ Glob Heal. 2019; 4: e000832.
[10] El Karim AA, Awawdeh MM. Integrating GIS accessibility and location-allocation models with multicriteria decision analysis for evaluating quality of life in Buraidah city, KSA. Sustain. 2020; 12(4): 1412.
[11] Cooper L. Location-Allocation Problems. Oper Res. 1963; 11(3): 331–343.
[12] Brimberg J, Hansen P, Mladenović N, Taillard ED. Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Oper Res. 2000; 48(3): 444–460.
[13] Hansen TE. The evolution of genetic architecture. Annual Review of Ecology, Evolution, and Systematics. 2006; 37: 123–57.
[14] Whittaker KA, Rynearson TA. Evidence for environmental and ecological selection in a microbe with no geographic limits to gene flow. Proc Natl Acad Sci USA. 2017; 114(10): 2651–2656.
[15] Tani K, Yamamoto K. Search Methods for Evacuation Routes during Torrential Rain Disasters Using Genetic Algorithms and GIS. J Geogr Inf Syst. 2020; 12(03): 256–274.
[16] Keling N, Mohamad Yusoff I, Lateh H, Ujang U. Highly efficient computer oriented octree data structure and neighbours search in 3D GIS. Lect Notes Geoinf Cartogr. 2017; 0(9783319256894): 285–303.
[17] Murray AT, Church RL. Applying simulated annealing to location-planning models. J Heuristics. 1996; 2(1): 31–53.
[18] Sangaiah AK, Khanduzi R. Tabu search with simulated annealing for solving a location–protection–disruption in hub network. Appl Soft Comput. 2022; 114: 108056.
[19] Salhi S, Gamal MDH. A Genetic Algorithm Based Approach for the Uncapacitated Continuous Location-Allocation Problem. Ann Oper Res. 2003; 123(1–4): 203–222.
[20] Fiedrich F, Gehbauer F, Rickers U. Optimized resource allocation for emergency response after earthquake disasters. Safety Science. 2000; 35(1-3): 41–57.
[21] Gong Q, Batta R. Allocation and reallocation of ambulances to casualty clusters in a disaster relief operation. IIE Trans. 2007; 39(1): 27–39.
[22] Abdelkarim A. Integration of Location-Allocation and Accessibility Models in GIS to Improve Urban Planning for Health Services in Al-Madinah Al-Munawwarah, Saudi Arabia. J Geogr Inf Syst. 2019; 11(06): 633–62.
[23] Vafaeinejad A, Bolouri S, Alesheikh AA, Panahi M, Lee CW. The capacitated location-allocation problem using the vaomp (Vector assignment ordered median problem) unified approach in gis (geospatial information systam). Appl Sci. 2020; 10(23): 1–22.
[24] Holzkämper A, Seppelt R. A generic tool for optimising land-use patterns and landscape structures. Environ Model Softw. 2007; 22(12): 1801-1804.
[25] Kaveh M, Kaveh M, Mesgari MS, Paland RS. Multiple criteria decision-making for hospital location-allocation based on improved genetic algorithm. Appl Geomatics. 2020; 12: 291–306.
[26] Ciarleglio M, Barnes JW, Sarkar S. Consnet-a tabu search approach to the spatially coherent conservation area network design problem. J Heuristics. 2010; 16(4): 537–557.
[27] Illoldi-Rangel P, Ciarleglio M, Sheinvar L, Linaje M, Sánchez-Cordero V, Sarkar S. Opuntia in méxico: Identifying priority areas for conserving biodiversity in a multi-use landscape. PLoS One. 2012; 7(5).
[28] Nassif AB, Capretz LF, Ho D, Azzeh M. A treeboost model for software effort estimation based on use case points. 11th International Conference on Machine Learning and Applications: 2012 December 12-15: Boca Raton, FL, USA.
[29] Saeidian B, Mesgari MS, Pradhan B, Ghodousi M. Optimized location-allocation of earthquake relief centers using PSO and ACO, complemented by GIS, clustering, and TOPSIS. ISPRS Int J Geo-Information. 2018; 7(8): 292.
[30] Krichen S, Faiz S, Tlili T, Tej K. Tabu-based GIS for solving the vehicle routing problem. Expert Syst Appl. 2014; 41(14): 6483–6493.
پژوهش های سنجش از دور و اطلاعات مکانی
دوره 1، شماره 1 - شماره پیاپی 1
دی 1401
صفحه 91-102
فایل ها
سابقه مقاله
  • تاریخ دریافت: 14 بهمن 1401
  • تاریخ بازنگری: 15 اردیبهشت 1402
  • تاریخ پذیرش: 23 خرداد 1402
هم رسانی
ارجاع به این مقاله
آمار