Implementation of Ant Colony Optimization Algorithm (ACO) in locating temporary accommodation shelters after earthquake (Kerman case study)

Dissertation for M.Sc degree

Department of Remote Sensing and Geographical Information System - Water and Soil Resources

Abstract

Among the important issues in the crisis management of unexpected natural events, especially earthquakes, is the optimal location in order to accommodate citizens during or after an accident. One of the big problems of the organizations involved in urban crisis management is the lack of a comprehensive spatial model in order to apply unit management in moving city residents to predetermined temporary accommodation places after the accident. The optimization of the temporary accommodation process takes place in three phases: determining the optimal safe places, determining the optimal routes, and allocating the population to safe places. The purpose of this research is to implement and evaluate the results of the ant colony optimization algorithm (ACO) in the location of the temporary shelter by determining the optimal routes and allocating the population to safe places in the city of Kerman as the study area. By making the necessary changes in the implementation of the ACO algorithm in solving the itinerant salesman problem, the steps related to location and allocation have been designed in the form of a spatial model. This model is designed based on an objective function in order to minimize the cost of moving the population of building blocks and three limitations of the average overflow/underflow, the maximum number of selected locations and the average spatial fit, so that the constraints of the problem guarantee the quality of the model's answers. To decide on the optimality of the solutions in ACO, the multi-criteria evaluation method was used. In order to improve the results, the sensitivity of the model to the change of the pheromone parameters and the innovative function of the ACO algorithm was evaluated and their appropriate and optimal values ??were determined. By taking into account the determined constraints and also the convergence graph of the objective function, the best performance in the final reduction of the objective function was determined by the model, and in addition, the results of the repeatability test show the stability and stability of the solutions of the investigated algorithm. The results of population allocation to safe places have an undeniable dependence on the distribution of safe places and their capacity, as well as the dispersion and population of building blocks. The average distance traveled to the nearest safe place in the final allocation model is equal to 1200 meters, but due to the lack of proper distribution of these places according to the distribution of the population in the city, more than 40% of the population must travel a distance of more than 1500 meters to the nearest selected safe place. As a result, it is necessary to search and establish new safe centers to reduce this gap. The results show that the use of ACO algorithm has many capabilities to be combined with geographic information systems to solve the problem of location and allocation that require a dynamic simulation environment (changing the combination of safe places - changing capacity). Keywords: crisis management, temporary accommodation, location and allocation, ant colony optimization algorithm (ACO), distance traveled, safe place, Kerman city.

1-      Chapter One: Research Overview

1-1-    Problem Statement

Despite the tremendous advances in technology and achieving the impossible of the past centuries, humans are still helpless against unexpected natural events such as earthquakes, floods, etc., and from time to time they are exposed to many casualties and financial damages. In the past decade, more than 200 million people per year due to natural disasters They have suffered life and financial injuries. In the meantime, unprincipled constructions and disregard for the risk-generating power of an area, not respecting the distance of sensitive uses and residential areas from the boundaries of faults and rivers, etc., cause the escalation of disasters (Esadi Nazari, 2013). Earthquake is one of the natural phenomena that occurs in most parts of the world, including Iran. During the years 1900 to 1990 AD, 1100 deadly earthquakes occurred in 75 countries and more than 80% of the deaths occurred in six countries. Iran is among these countries with 120 thousand human casualties. Also, in the years 1361 to 1370, Iran has experienced the highest number of earthquakes. (Abdolahi, 1381)

Our country, Iran, is located in the seismic zone of the world. Most of the urban and non-urban parts of the country are located in areas with a high relative risk of earthquakes. The importance of earthquakes in Iran is more understood today with the intensification of the country's development process, the expansion of cities, and the concentration of the population. Considering the continuous confrontation of the country with the phenomenon of earthquakes, it is always necessary to make efforts to achieve practical methods and coherent solutions to deal with it.. Considering the continuous confrontation of the country with the phenomenon of earthquake, it is necessary to always make efforts to achieve practical methods and coherent solutions to deal rationally and minimize the catastrophic dimensions of such an event (Esadi Nazari, 2013). The United Nations Disaster Relief Coordination Office declares that it can be confidently stated that, during the past decades, the provision of emergency aid related to medicine, nutrition, etc. after a disaster has made significant progress, but an important part has still made little improvement, and that is emergency shelter or, in general, post-disaster shelter. and this is while our villages are highly vulnerable to a 5-magnitude earthquake and our cities are highly vulnerable to a 6-magnitude earthquake. Reducing the side effects of an earthquake, or in other words, reducing damage such as social and infrastructure during an earthquake, will occur when different phases of crisis management are considered at all levels of planning. But every correct decision and planning requires correct, accurate and up-to-date information and their analysis. Because most of the information required in the urban and earthquake categories are mostly spatial in nature, therefore the science and technology of the geographic information system with the ability to collect spatial and non-spatial data, store, update, analyze, model and display spatial information can be used as an optimal science and technology to organize and analyze information comprehensively and quickly and to help make appropriate decisions in crisis management (Aghamohammadi, 2019). On the other hand, it should be noted that the environment of geographic information systems is a static environment and does not have the capability of dynamic simulation. Artificial intelligence, especially intelligent agents, are capable of eliminating weaknesses and can play an effective role in crisis management in interaction and even combination with geographic information systems (Rajabi, 2018).

Intelligent algorithms in GIS have improved its ability to properly regulate decisions, which include complex spatial planning and resource optimization (Birkin, et al., 1996; Bong, et al., 2004).  Among the methods of artificial intelligence, which is referred to as a meta-heuristic method, is the ant colony optimization algorithm ([1] ACO). (Dorigo, et al., 2004).  This method was first developed by Dorrigo in his PhD thesis in 1992 as a multi-agent solution [2] to solve complex optimization problems. Its first successful application is solving the traveling salesman problem (TSP[3]) (Dorigo, 1992), which proved its effectiveness in quickly solving combinatorial optimization problems. In recent years, many applications have been used in complex optimization problems such as object selection and facial expression recognition, vehicle routing (White, et al., 1998), allocation (Maneizzo, et al., 1994), transportation network design and improvement, and machine learning techniques (Parpinelli, et al., 2002) [4] and It has been presented.

According to what was said about the importance and necessity of paying attention to the earthquake crisis and the necessity of planning to deal with its aftermath, in this research, using the capabilities of geographic information systems and the ACO algorithm, the location of temporary accommodation shelters after the earthquake in order to allocate the affected population has been done as an optimization problem in the real world.   

1-2- The need to conduct research:

Today, due to the growing trend of population and population density in urban areas, especially in densely populated and seismically prone cities, the need for an all-round approach to natural disasters and disasters caused by them has become more apparent. Harmful effects caused by excessive concentration of population in specific urban areas, along with the lack of preventive planning and the lack of necessary preparation to deal with events such as earthquakes, are considered a very serious and important threat to the lives of citizens and the continuity of urban life (Bagherpour, 2010).

Among the important issues in crisis management, especially in the field of unexpected events, is the optimal location in order to accommodate citizens in the face of or after an event. Due to the involvement of many factors and parameters in this issue, locating such places is very complicated (Samadzadegan et al., 2014). In Iran, choosing a place for temporary accommodation is done experimentally after an accident and without considering the necessary standards by relief organizations.