بکارگیری الگوریتم NSGA-II برای حل مسائل مکان‌یابی چندهدفه

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

نویسندگان

1 دانشیار دانشکده معماری و شهرسازی دانشگاه بین المللی امام خمینی(ره) قزوین

2 دانشگاه بین المللی امام خمینی(ره) قزوین

چکیده

مکان‌یابی کاربری‌ها یکی از مهمترین مسائل شهرسازی است که دارای مقیاس‌های متفاوتی می‌باشد. هنگامی‌که با یک مسئله‌ی مکان‌یابی کوچک مقیاس با شرایط و محدودیت‌های اندک روبه‌رو باشیم می توان با استفاده از روش‌های سنتی به جواب رسید ولی زمانی که با یک مسئله‌ی بزرگ مقیاس مکان‌یابی با شرایط و محدودیت‌های زیاد روبه‌رو باشیم، مشکل بتوان بدون استفاده از هوش مصنوعی و الگوریتم‌های تکاملی، مکان بهینه یا حتی نزدیک به آن را در مقیاس زمان و هزینه‌ی قابل‌قبول به‌دست آورد. هدف این مقاله، معرفی یک تکنیک کارآمد و مناسب برای حل مسائل مکان‌یابی چندهدفه است. در پژوهش حاضر نوع تحقیق کاربردی و روش تحقیق توصیفی- تحلیلی است. به همین منظور یک مسئله‌ی مکان‌یابی فرودگاه برای یکی از شهرهای بزرگ کشور، به عنوان مطالعه موردی بر اساس الگوریتم ژنتیک رتبه‌بندی نامغلوب‌ (NSGA-II) بررسی شده و بنابر بر شاخص‌هایی مانند دسترسی آسان، کاهش آلودگی صوتی، میدان دید خلبان، دسترسی به تاسیسات و زیرساخت‌ها و ... به‌ صورت یک مدل برنامه‌ریزی ریاضی با 6 تابع‌هدف و تعداد مشخصی شرایط مورد نیاز پیکربندی شده است. در نهایت با حل مسئله از طریق الگوریتم پیشنهادی، از میان 200 جواب نهایی که شامل جبهه جواب‌های متفاوت بود، یک جبهه جواب با 4 نقطه به‌عنوان مکان بهینه برای احداث فرودگاه برگزیده شد. الگوریتم ژنتیک رتبه‌بندی نامغلوب(NSGA-II) ‌که جز روش‌های مستقیم حل مسائل مکان‌یابی چندهدفه می‌باشد، با توجه به سرعت و دقت بیشتر نسبت به سایر روش‌ها و همچنین ارائه‌ی یک سیستم پشتیبان تصمیم، به عنوان رهیافتی تازه در مسائل مکان‌یابی چندهدفه، جانشین مناسبی برای روش‌های تجزیه و روش‌های سنتی خواهد بود.

کلیدواژه‌ها

موضوعات


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

Using NSGA-II Algorithm to solve multi-purpose location problems

نویسندگان [English]

  • Bahram Amin zadeh Gohar rizi 1
  • saeid tohidi rad 2
  • Roshanak Asadi 2
چکیده [English]

Land-use location planning is one of the most important urbanism issues with different scales. The choice of location planning method is determined by the kind of problem and the importance of the supposed Land-use to be location planned. For example, to choose a location from some limited options, the multi-attribute decision making methods should be used; but when there is no initial option for location planning, the multi-objective decision making method should be used. Nowadays, the use of computational techniques for location planning is inevitable. The reason is that a manager's decisions in this field are influenced by various qualitative and quantitative factors, generally in conflict with each other, so that optimization of a factor may lead to the destruction of other factors. Thus, to prevent errors in decision-making, multi-objective decision-making techniques have been considered and used in recent years. There are different methods for solving multi-objective decision making problems which are categorized into two general groups: decomposition methods and direct methods. In the decomposition methods, first, the multi-objective optimization problem turns into a single-objective problem and then the problem is solved. However, in multi-objective optimization methods, the problem is solved in a multi-objective manner. Decomposition methods comprise of the 4 techniques of Weighted sum, Goal programming, Goal Attainment and  -Constraint. Each of the 4 techniques tries to simplify the problem and solve it with specific measures. To turn a multi-objective problem into a single-objective one, these methods are forced to lose some of the space decision information. To solve this issue, the problem should be solved several times, which is very time-consuming. Furthermore, each time the problem is solved with these methods, a different answer is obtained. However, direct methods are not faced with this problem and are much faster and more accurate. The purpose of this study is to introduce an efficient technique of direct methods to solve all the multi-objective location planning problems and resolve classic and decomposition methods issues. Therefore, an airport location planning problem for the one of the major cities, based on Non-dominated Sorting Genetic algorithm (NSGA-II) was considered as a case study. Based on indicators such as easy access, noise pollution reduction, visibility, and access to infrastructure, the problem was modeled as a mathematical programming problem with 6 objective functions such as the minimum distance from main roads and highways, maximum distance from industrial factories, minimum distance from power transmission lines, maximum distance from the city and traditional gardens, minimum distance from the main gas transportation pipeline, the maximum distance from residential areas around the city and a certain number of required conditions. Finally, amongst the 200 final solutions of the proposed algorithm, including different front solutions, a solution with 4 points was chosen as the optimum location for the construction of the airport. Because of greater speed and accuracy, as well as providing a decision support system, the Non-dominated Sorting Genetic algorithm (NSGA-II) which is a direct multi-objective location planning problem solving method, can be considered as an appropriate alternative to the Decomposition and other traditional multi-objective location planning methods.

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

  • Location Planning
  • NSGA-II algorithm
  • Multi-Objective Decision
  • Airport
  1. Alborzi, M.(2009), Genetic Algorithm, Tehran, Sharif university.[In Persian]
  2. Asgharpour, M.(2011), Multi-Criteria Decision making, 10th edn, Tehran, university of Tehran. [In Persian]
  3. Bennett, David A., Wade, Greg A., Armstrong, Marc P. (1999) "Exploring the Solution Space of Semi-structured Geographical Problems Using Genetic Algorithms". Transactions in GIS, No. 3(1), Pp. 51-71.
  4. Bui, Lam Thu., Alam, Sameer. (2008), Multi-Objective Optimization in Computational Intelligence: Theory and Practice (Premier Reference Source), New York, Information Science Reference.
  5. California Department of transportation. (2011), California airport land use planning handbook.
  6. Cao, Kai., Batty, Michael., Huang, Bo., Liu, Yan., Yu, Le. & Chen, Jiongfeng. (2011), "Spatial Multi-Objective Land-use Optimization: Extensions to the Non-dominated Sorting Genetic Algorithm-II". International Journal of Geographic Information Science, No. 25 (12), Pp. 1949-1969.

 

  1. Cao, Kai., Huang, Bo., Wang, Shaowen. & Lin, Hui. (2012), "Sustainable Land Use Optimization Using Boundary-based Fast Genetic Algorithm". Computers, Environment and Urban Systems, No. 36 (3), Pp. 257-269.
  2. City and Planning Consulting engineers. (2011), Master plan report of the city of Qazvin and the influence area, Ministry of Housing & Urbanism, Housing and Urbanism organization of Qazvin province. [In Persian]
  3. Coello Coello, Carlos A., Lamont, Gary B. & Van Veldhuizen, David A. (2007),  Evolutionary Algorithms for Solving Multi-objective Problems, 2th edn, New York, Springer.
  4. Duh, Jiunn Der., Brown, Daniel G. (2007), "Knowledge-informed Pareto Simulated Annealing for Multi-objective Spatial Allocation". Computers, Environment and Urban Systems. No.31 (3), Pp. 253-281.
  5. Durillo, Juan J., Nieto, Jose Garcia., Nebro, Antonio J., Coello Coello, Carlos A., Luna, Francisco. & Alba, Enrique. (2009), "Multi-Objective Particle Swarm Optimizers:An Experimental Comparison". 5th International Conference on EMO 2009, Nantes, France, April 7-10, Pp. 495-509.
  6. Engelbrecht, Andries P. (2007), computational intelligence, 2th edn, England, John Wiley & Sons Ltd.
  7. Forghani, A., Sharif yazdi, M.& Akhundi, A.(2008), Locating industrial and service centers with functional approach, Tehran, jahad daneshgahi. [In Persian]
  8. Haupt, Randy L., Haupt, Sue Ellen. (2004), Practical Genetic Algorithms, 2th edn. John Wiley & Sons, New Jersey.
  9. Huy, Man‌ Quang., Kappas, Martin.(2010),"Developing multi objective linear programming (MOLP) to improve the decision making of land use planning". 31st Asian Conference on Remote Sensing(ACRS) 2010, Hanoi, Vietnam, November 1-5, pp. 647-652.
  10. Liu, Xiaoping., Li, Xia., Shi, Xun., Huang, Kangning. & Liu, Yilun. (2012), "A Multi-type Ant Colony Optimization (MACO) Method for Optimal Land Use Allocation in Large Areas". International Journal of Geographical Information Science. No.26 (7), Pp. 1325-1343.
  11. Liu, Yang., Lan, Zeying. (2010), "Automatic Districting of Land Consolidation Based on Multi-objective Tabu Search Algorithm". Wuhan Daxue Xuebao (XinxiKexue Ban)/ Geomatics and Information Science of Wuhan University. Vol. 35, Issue. 9, Pp. 1129- 1133.
  12. Masumi, Z., Mansourian, A. & Mesgari, M.(2010), "Application of Multi-Objective Genetic Algorithm in the industrial locating studies". Journal of Iranian RS & GIS society, No. 4(2), Pp. 1-22. [In Persian]
  13. Porta, Juan., Parapar, Jorge., Doallo, Ramon., Rivera, Francisco F., Sante, Ines. & Crecente, Rafael. (2013), "High Performance Genetic Algorithm for Land Use Planning", Computers, Environment and Urban Systems, Vol. 37, Pp. 45-58.
  14. Qian, Min., Pu, Lijie., Zhu, Ming. & Weng, Lingyan. (2010), "Spatial Optimization Method for Sustainable Multi-objective Land Use Allocation". 18th International Conference on Geoinformatics, Beijing, China, June 18-20,  Pp. 1-6.
  15. Senthilkumar, Chinnamuthu., Ganesan, Gowrishankar. & Karthikeyan, Ramanujam. (2012), "Optimization of ECM Process Parameters Using NSGA-II". Journal of Minerals and Materials Characterization and Engineering. No.11(10), Pp. 931-937. 
  16. Stewart, Theodor J., Janssen, Ron. & Van Herwijnen, Marjan. (2004), "A Genetic Algorithm Approach to Multi-objective Land Use Planning". Computers and Operations Research, No. 31(14), Pp. 2293-2313.
  17. Wells, Alexander T., Young, Seth B. (2004), Airport Planning & Management, 5th edn, New York, McGraw.Hill.
  18. Yang, Z., Moodie, D.R. (2009) "Locating Urban Logistics Terminals and Shopping Centers in a Chinese City", POMS 20th Annual Conference, Orlando, USA,1-4 May.
  19. Yin, Peng Yeng., Wang, Tai Yuan. (2012), "A Grasp-VNS Algorithm for Optimal Wind Turbine Placement in Wind Farms". Renewable Energy, Vol. 48, Pp. 489-498.
  20. Zhou, Jiang., Civco, Daniel L.(1996), "Using Genetic Learning Neural Networks for Spatial Decision Making in GIS". Photogrammetric Engineering and Remote Sensing, No. 62 (11), Pp. 1287-1295.