مقايسه قابليت‌ الگوريتم‌هاي فراابتكاري در حل مسيله مكان‌يابي مراكز آتش نشاني

Assessing the Capability of Meta-Heuristic Algorithms in Location-Finding for Firefighting Centers

مكان يابي و تخصيص از نوع مسايل NP-Hard است كه با افزايش تعداد نقاط تقاضا و مراكز خدماتي، پيچيدگي و حجم محاسبات مسيله به‌صورت نمايي افزايش مي‌يابد. براي حل اين‌گونه مشكلات، از روش‌هاي فراابتكاري متناسب با شرايط مسيله استفاده مي‌شود. در اين تحقيق، روش هاي فراابتكاري جست‌وجوي ممنوع، ژنتيك و شبيه‌سازي بازپخت به‌عنوان روش‌هاي بهينه سازي براي مكان يابي مراكز آتش نشاني و تخصيص مناطق شهري به آن‌ها استفاده شده‌اند. اين روش ها با توجه به معيارهاي زمان حل مسيله، مقدار تابع هدف، تعداد تكرار و نحوه پوشش منطقه در سناريوهاي مختلف ارزيابي شده‌اند. سناريوهاي مختلف در روش ژنتيك بر‌اساس تغيير در تعداد تكرار و جمعيت اوليه و در روش شبيه-سازي بازپخت بر‌اساس تغيير در تعداد تكرار حركات و تغييرات دما توليد شده‌اند. روش جست‌وجوي ممنوع داراي بيشترين زمان محاسباتي (38 دقيقه و 42 ثانيه) و كمترين (بهترين) مقدار تابع هدف (104×749/4) است و با توجه به نقشه توليد‌شده، بهترين پوشش را در منطقه توسط مكان‌هاي بهينه برگزيده ايجاد مي‌كند. الگوريتم شبيه سازي بازپخت، در بين روش‌هاي اجرا، داراي كمترين زمان حل مسيله است و هنگامي‌كه تعداد تكرارها در اين روش از اندازه مسيله (در اينجا تعداد پارسل‌ها) بزرگ‌تر باشد، جواب‌هاي مطلوبي توليد مي‌شود. نتايج به‌دست‌آمده در سناريوي دوم روش SA در اين تحقيق، صحّت اين ادعا را اثبات كرده است. بر‌اساس يافته‌هاي اين تحقيق، مي‌توان نتيجه‌گيري كرد كه در‌صورت نياز به اجراي سريع (زمان بسيار كوتاه عملكرد الگوريتم) روش شبيه‌سازي بازپخت سريع‌ترين روش خواهد بود؛ در شرايط نياز به سرعت و دقت مناسب و متوسط، الگوريتم ژنتيك گزينه مناسبي است و سرانجام در حالت نياز به دقت و كيفيت بالاي جواب و بدون محدوديت زمان، روش جست‌وجوي ممنوع گزينه برتر است.

Location finding is considered as an NP-Hard problem, in which the complexity and volume of computations due to larger numbers of demand points and service centers are exponentially increased. To overcome such complexities meta-heuristic algorithms are usually used. These methods usually produce answers close enough to the optimum solution in acceptable time. In this research three Meta heuristic algorithms of Tabu Search (TS), Genetic Algorithm (GA) and Simulated Annealing (SA) are used to optimize the location of fire fighting station and allocating urban blocks to them. The mentioned Meta heuristic methods are evaluated and compared with respect to time scale, the value of objective function, number of iteration and coverage of the study area. Different scenarios are developed, based on the number of iterations and the initial population for the genetic method. Similarly, different scenarios are developed for annealing method based on the number of repetitions of the same movements and temperature. The Tabu Search method has the maximum time of computation and minimum value of objective function, among the Meta heuristic methods. In addition, the sites selected by Tabu Search provide the best coverage in the area studied. In simulated annealing method, the solution ideas are produced when the number of iteration is larger than the size of the problem. The achieved results, in second scenario of simulated annealing method, have proved the correctness of this claim. It could be concluded that the simulated annealing method can be a suitable method when quick time results are required. When both quality of solutions and performance are to be considered, the genetic algorithm can be a proper choice. Finally, when there is no time limitation, the Tabu Search can generate the best results.