Mathematical modeling of the problem of locating temporary accommodation centers and assigning victims after a possible earthquake to safe places and solving using meta-heuristic algorithmsand
Earthquakes, one of the most important natural disasters of the earth, have always caused irreparable damage to human settlements in short time. One of the most important issues that we face after an earthquake is the transfer of earthquake victims and traumatized civilians to safe places and medical centers. The city of Mashhad with different geographical faults and the presence of enormous religious, cultural, historical and industrial assets make Mashhad the most dangerous city in terms of earthquake hazards. In the 9th district of this city, the existence of worn-out structures along the narrow passages and the importance to save time in providing relief proves the need to locate temporary accommodation centers and allocate the injured to safe places.
Material and Methods:
The process of optimizing the accommodation of people includes 2 main steps 1) Determining candidate locations for temporary accommodation 2) Optimal allocation of population blocks (origin). The weight of criteria was calculated using the pairwise comparison method. Then suitable places for deployment are identified. Criterion in the form of giving a specific weight to each, in order to prepare the final map, is of importance. Accordingly, the opinions of experts in the field of urban crisis management have been utilized. Subsequently, using GAMS software and 7 super-innovative algorithms such as SA, PSO, ICA, ACO, ABC, FA, LAFA.
The average process time and cost of 7 algorithms out of ten random problems with 1000 repetitions, and an average of 10 execution times show, that the 3 algorithms ACO, ABC and LAFA have lower cost and process time than the other meta-innovative algorithms. Therefore, we use the above three algorithms to solve the case study
Natural disasters are part of environmental disasters. The great abundance of natural disasters in the world speaks for itself. Despite the advancement of science and technology, humans are still vulnerable to the effects of accidents and disasters caused by natural changes such as floods, earthquakes, storms, as well as disasters caused by their hand-made tools . In accident-prone countries, the consequences of crises are considered a major deterrent to development. Between 2010 and 2020, more than 1734 natural disasters were reported in the Asia-Pacific region, and about 2.2 billion people were directly or indirectly affected by natural disasters. So much so that more than $843 billion has been estimated to be the economic damage for these natural disasters. At the same time, more than 65% of natural disaster-related deaths have occurred in these parts of the world, which means that it can be acknowledged that more than 75% of the effects of natural disasters occur in Asia. According to international organizations, over the past 40 years, the economic damage caused by these natural disasters has exceeded $2 trillion, with earthquakes, floods and tsunamis to blame for more than 92% of the total damage. To date, even with the advancement of science and technology, it has not been possible to completely prevent these accidents or reduce the damage to zero. Though, it is possible to reduce damage to some extent. One of the most important and widely utilized subject in times of crisis are relief, emergency and crisis logistics, which can have a significant impact on reducing the amount of damage by planning and predicting the consequences of these crises .
Earthquake belts cover a large part of Iran and are the most destructive natural phenomenon known. Cities, as they make up the majority of the country's population, generally suffer heavy damage during an earthquake. Poor conditions of physical elements and inappropriate urban utility, dysfunctional urban road network, worn and old urban texture, high urban density, poor condition of urban infrastructure and lack and improper distribution of urban open spaces, are a key role in increasing the vulnerability of cities to various dangers. The central areas of the country's cities, which form the old and main core, generally have worn-out structures and narrow streets with narrow and nested alleys. Other characteristics of these regions in the cities are the lack of open spaces, parks and green space as well as other means of crisis reduction. In urban areas, the usual detrimental effects of natural disasters; involves a combination of physical destruction and disruption of urban elements. Destruction affecting residential structures and buildings, road networks, access points such as bridges, communication roads, basic facilities; Such as water tanks, power plants, telephone lines, electricity, water piping, gas, and so on . One of the most important issues to be considered after the earthquake is to provide a suitable place for temporary accommodation of earthquake victims . Considering that the main need of earthquake victims is to have shelter. Generally, it is not possible to provide suitable accommodations for earthquake victims immediately after an earthquake, it is necessary before such crises, suitable places for considered earthquake victims be located and identified . In the time being, choosing an optimal location for temporary housing after an earthquake in cities, whilst taking into account all important criteria, including before crisis, during crisis and post crisis measures, is a major challenge. In cities, especially metropolises, the issue of temporary housing is of more importance because, in the case of temporary housing, the area with widespread damage, in urban areas, is much larger than in rural areas, locating temporary housing before the accident and in the planning stage can help relevant organizations have a written plan after the accident . In Iran, the allocation of emergency accommodation for citizens is generally done experimentally and after the accident without considering the necessary standards by relief organizations. Obviously, not observing the correct location may lead to another catastrophe, even worse than the initial accident. Therefore, it is necessary to plan, manage and provide appropriate solutions in an emergency for temporary or permanent deployment of affected populations before the earthquake.
One of the most important issues in providing services in hospital systems for temporary accommodation is the design of an optimal hierarchical structure based on management decisions. In fact, organizations tend to implement their organizational level at the service level. According to the plan implemented in the structure of health system services in Iran, the responsible organizations should divide their covered areas into main sections so that management decisions can be made at this level. At each level, there is a need to re-allocate in accordance with the views of managers to ultimately end up providing integrated, hierarchical decisions. In fact, decisions should be made in such a way that primarily a main block is determined following determination of sub-blocks in each block. This makes system management more convenient because, by designating a specific center for each sub-block, operational level decisions are made in the same sub-block and macro-level management is not involved in this type of issue. Of course, by sending the relevant reports, the level of implementation will be informed and if there is a need for fundamental reform, the necessary decisions will be made. Therefore, it is desirable to determine local centers to provide services and then to determine the sub-blocks covered by each hospital in their sub-centers. In this paper, a mathematical model has been developed for the problem of location and optimal allocation of people to medical centers with regard to capacity constraints in the event of an earthquake crisis. The purpose of the issue is to select the best locations for temporary accommodation of people and also the optimal allocation of people to these places, so that the amount of casualties and damage caused by the earthquake and aftershocks is minimized. Subsequently a case study on 9th district of Mashhad is described. Places that have favorable housing conditions are extracted, a super-innovative algorithm is implemented to solve the problem, and at the end, the optimal number of accommodation centers and the optimal allocation of people in the area to these centers, as well as the allocation of people to medical centers in the region, is presented.
The problem of location and allocation began with the Weber problem in 1909 . Weber's study of the problem of location formally began in 1929 with a study of how to locate a resource, and was then followed by Hakimi’s research in 1964. Since the emergence of location and allocation issues, many methods have been introduced, including accurate or innovative methods to solve them. But using precise methods to solve complex and large problems is not very logical due to the long execution times. For this reason, many studies have been done on the application of innovative methods to solve such problems. In an article, Wang et al.  examined the location of facilities by considering the customer's random demand and with the aim of minimizing the total cost of travel and customer waiting time. In this model, the random demand of customers was considered according to the nearest resident facility. The issue of location of facilities for responding to emergencies and crisis situations on a large scale has been raised. In a study on identifying and locating crisis recovery centers, Dekle et al.  proposed a model for a Florida area during a hurricane crisis. The aim of this model is to minimize the final number of crisis recovery centers, in terms of full coverage of the affected areas, taking into account distance limitations. In one study, Mestre et al.  used two models of location and allocation to plan the hospital network. These models are designed to improve geographic access as well as minimize costs. In another study in 2015, the issue of allocating emergency service centers, as well as the location of these bases, was studied through a genetic algorithm with an integrated simulation model. In this issue, different patient classes (demand points) were examined and two supply lines (emergency bases and ambulances) were included in the model. The aim of the problem was to maximize the probability of patient survival, whilst using real data from London emergency services . Boonmee et al.  in an article referred to the occurrence of natural disasters since 1950 and examined the problems caused by it. A model for optimizing the location of facilities in providing emergency situations with a precise algorithm along with an exploratory algorithm was proposed as a solution. Ahmadi et al.  due to the destruction of the transportation network after the earthquake, by presenting a two-stage stochastic model, tried to determine the location of distribution centers and facilities. Camacho-Vallejo et al.  presented a two-tier decision model in the relief supply chain, the first level was to plan distribution of items and goods from designated warehouses to the affected areas. The second level was planning to receive relief items and goods from various countries around the world. Gan et al.  proposed a one-period and definitive routing and scheduling model for the distribution of relief items from a relief center to the affected areas, taking into account the utility function, which allows the service to be provided to any affected area only by a single utility to be considered a tool. Zokaee et al.  considered a three-tier supply chain model, including suppliers, relief centers, and crisis areas, for relief operations and humanitarian aid that have uncertain conditions. Their model seeks to maximize the satisfaction of the affected people while minimizing supply chain costs. Young DaeKo et al.  studied the location, allocation, and capacity decisions of emergency medical facility centers in a given area with specific rules. In this study, it was assumed that each candidate center has a certain initial ability and capacity to perform medical services. Also, the number of patients and their type of disease were considered as a known parameter. In this study, simulation was used to evaluate the performance of the model. Therefore, definitive answers were provided to solve the model under random conditions. In a model, Rezaei Malek et al.  showed that relocating goods and relief sites helps to efficiently distribute relief through the crisis logistics network. This study presented a location-allocation and distribution planning model while providing the best policy for the renewal of perishable goods in the pre-crisis phase. He also used robust methods to deal with the uncertainty of the problem. The efficiency of the model has been shown by a case study in Iran. Rezaei Malek et al.  in a study designed a coherent and strong relief supply chain network with respect to the distribution of goods with a perishable nature. In this study, perishable goods such as medical and food products such as milk have a certain shelf life that is distributed in the relief supply chain network for the use of victims in places of demand. In this study, the catastrophe was considered to have occurred after a long period of time.
MATERIAL AND METHODS
Geographical location of the study area and data were used.
A case study in this study is of district 9 of Mashhad. This area has an area of 4450 hectares in which more than 327 thousand people live in the form of 103 thousand families. District 9 of Mashhad municipality is located in the southwest of the city and its protected area provides services from the north to Malek Abad and Vakil Abad boulevards, from the south to Binalood heights, from the east to Shahid Kalantari highway to Abadgaran and from the west to Vakil Abad garden and Shandiz and Torqabeh intersections are limited (source: https://zone9.mashhad.ir). To plan the first phase of this issue, we first need to identify the conditions in the region and collect the appropriate data. The first step in solving the location problem is to have a map of the area and information about the required data. In this paper, the data required for initial location are: density of existing service centers (hospitals and gas stations), location of faults, location of main roads, location of demand points (source population blocks), population density of each Block and sloped area. After stating the research and problem-solving methods, we will describe the case study. Fig 1 shows a map of the area under study.
Since the research method has been implemented in Mashhad, Table 1 shows the characteristics of important faults in Mashhad
The characteristics of important faults in Mashhad
|Length of Fault||Size||Acceleration of Fault||Fault|
|Max of 100||7.3||0.67||South|
|80||7.4||0.07||North of Nishaboor|
|Max of 100||7.2||0.65||Fariman|
Defining the problem:
In this research, two levels of supply chain network, distribution centers (hospitals) and customers (people affected by the earthquake) have been studied. In fact, areas in a city are divided based on population centers, and each area has a demand rate. In these areas, a number of potential distribution centers called potential field hospitals (temporary accommodation centers) to provide services to people affected by the earthquake have been planned. There are also a number of existing and active physical hospitals in the city. In addition, there is a demand for relief after an earthquake in a city by the affected people that, any existing hospital and temporary accommodation centers should aid the affected people and provide the desired services. The optimal allocation of individuals to existing medical centers is also examined. The process of optimizing the accommodation of people in this research includes 2 main steps:
1) Determining candidate locations for temporary accommodation
2) Optimal allocation of population blocks (origin) to safe places and medical centers.
In addition, in this study, it was assumed that potential distribution centers have a specific and limited capacity.
In the first step, using the available information for the city of Mashhad (maps, aerial photographs, satellite images, etc.), places that have favorable conditions for accommodation were extracted. The data required in this step is obtained from crisis management databases as well as the municipality. In this study, using GIS and remote sensing data, the location of suitable areas for use as a shelter is investigated. It should be noted that the construction of these centers is not possible in all areas. The distance from the fault, the distance from the areas that are likely to explode after an earthquake, such as gas stations and the ability to access all parts of the area relatively well, could be good criteria for determining the right place to build safe places. Also, the proximity of temporary accommodation centers to relief centers and hospitals can play an effective role in saving the lives of the victims of the accident. In the next step, the goal is to find and optimally allocate people to safe areas.
On the other hand, the type of costs considered in this study include the cost of opening (establishment) and the cost of transfer (sending). In the cost of opening, it is assumed that this cost will be used to open temporary accommodation centers, and the cost of transportation, which includes the cost of transporting people affected by the earthquake areas. In fact, the proposed goals in this issue are to optimize the number of safe places for temporary accommodation of people, to minimize the total cost of moving people from building blocks (origin) to safe places and medical centers. In the first step, the proposed locations are selected by ArcGIS software. Then, in the next stage, from the nominated places, the best places for construction of temporary housing centers are selected, and the optimal transfer of people from the building blocks to the housing centers is analyzed. In the meantime, there are a number of fixed-location treatment centers that discuss how to optimally transfer people from building blocks to these centers in the proposed mathematical model.
In order to develop the mathematical model of the relief supply chain in the event of an earthquake, the following hypotheses have been considered:
1. The city is divided into regions based on population centers, and each region has a demand rate.
2. The city is divided into regions based on population centers, and each region has a demand rate.
3. To locate the problem, it is assumed that only spatial criteria affect the problem.
4. In this research, traffic on transit routes is not considered.
5. In the city of Mashhad, there are a number of hospitals with a permanent location that are ready to provide services to the injured.
6. The total population and the population of each building block are known.
7. The total population and the population of each building block are known.
8. Temporary accommodation is not possible in all areas
9. There are two types of costs in this research, one is the cost of initiation, which is used to open potential distribution centers (field hospitals), and the other is the cost of transfer, which includes the cost of transporting people, affected from earthquake-stricken areas to distribution centers intended to benefit from services and goods.
10. Housing planning will cover the entire population in the area.
If a temporary accommodation center is created at the desired point, otherwise it is equal to zero. In the first part of the objective function, the total displacement from the source building block to the housing center is minimized. In the second part, the total transfer from the origin to the medical centers is minimized and finally the fixed cost of equipping a temporary accommodation center is considered. Constraint 1 states that the O percentage of the total population is transferred from n to m. Constraint 2 controls that the sum of people transferred from n to d should be less than equal in capacity d. Constraint 3 indicates that the total number of people transferred to m should be less than the total capacity of the accommodation centers. Constraint 4 states that each source block must be assigned to a secure location. Constraint 5 states how many people from each block to accommodation centers are transferred (are a fixed number and are obtained randomly). Constraint 6 indicates that S is the percentage of the total population is transferred from n to d. According to Constraint 7, the total number of people transferred from n to should be less than its capacity m. According to Constraint 8, the sum of the safe places selected is less than or equal to the number of candidate places for accommodation. Several people from each block are taken to hospitals (are fixed numbers and are obtained at random). Constraint 10 states that unless a location is selected as the accommodation center, individuals from the block will not be assigned to that location.
Criteria required in initial location
Many factors can be considered to determine the location and different criteria can be defined. Accessibility, security, economic considerations, the culture and traditions of the people of the area, green space, and many more are among the factors influencing a location. In this study, five spatial criteria have been considered for initial location. Criteria are: access to main roads, distance from medical centers, distance from gas station, and distance from fault and slope of the area. In order to locate temporary accommodation centers in crisis situations, the weight of criteria is calculated using the pairwise comparison method (the weight of each factor indicates its importance and value compared to other factors in field location operations). Then suitable places for deployment are identified. Using the map of the area, the use of selected locations and candidate locations are introduced and used as input in the next step. After determining the location criteria and preparing the relevant maps, the importance of each criterion in the form of giving a specific weight to each in order to prepare the final map should be done. Accordingly, at this stage, the opinions of experts in the field of urban crisis management were used and weights were extracted as described in Table 2.
Criteria weights for initial location
|Slope of Area||Distance from Main Paths||Distance form Gas station||Distance from medical centers||Distance from Fault||Standards|
Generation of random issues
According to the proposed model, a number of problems at different scales with hypothetical data are randomly generated and solved by different methods. The results obtained in this section will be effective in evaluating solution methods. It is important to note that the problem of locating and allocating an optimization problem is complex. Solving these problems through accurate traditional methods requires a lot of computational time to get an answer. The dimensions of the problem solved by this type of traditional methods are small. It is not possible to use the definitive method due to the long computation time to solve these problems. Therefore, methods for optimal solutions that are based on one or more criteria and are not located in the local optimal region should be presented, among which we can mention evolving algorithms.
Evolutionary algorithms are random search-based methods modeled on natural biological evolution modeling. They work on possible responses that are superior and have longer generation survival, so they get a closer estimate of the optimal response. In each generation, a new set of estimates is generated based on the selection of members with a higher degree of fit, and they are combined together similar to what happens in nature. As a result, this process involves the development of individuals who are more environmentally friendly than their parents, much like those that are in harmony with nature. Evolutionary algorithms model natural processes, including selection, recombination, mutation, migration, location, and neighborhood. Evolutionary algorithms work on populations of individuals rather than a single response, thus, the search can be done in parallel. At the beginning, a number of people in the community are randomly guessed, then the target function for each of these people is calculated and a new generation is created. Individuals are selected based on their level of competence to produce babies.
These people are considered as parents and reproduce to produce babies. Then all babies are genetically modified with a certain amount of probability, ‘the mutation’. Now the level of competence (fitness) of the newborns is determined and they replace the parents in the society and create a new generation. This cycle is repeated until one of the end optimization criteria is obtained. The single-community evolutionary algorithm is robust enough and efficient in a wide range of problems. However, better results will be obtained by creating several sub-communities. Each sub-community is formed on several separate generations (such as the single-community evolutionary algorithm), and before that no member will move between sub-communities. The multi-community evolutionary algorithm models the evolution of species in a more similar way to nature than the single-community evolutionary algorithm.
From the above discussion, it can be seen that evolutionary algorithms are fundamentally different from other conventional optimization and search methods. Some of these differences are: Evolutionary algorithms do not search for a single point, but examine a population of points in parallel; evolutionary algorithms do not require implicit information and other complementary knowledge; only the objective function and the relevant competence affect the search directions. Also, the evolving algorithms take advantage of the possibly changing rules and not the specific ones. The evolving algorithms provide a large number of acceptable answers and the final choice is up to the user.
In this paper, we solved the problem using GAMS software and SA, PSO, ICA, ACO, ABC, FA, LAFA meta-innovative algorithms and compared the solution time and objective function of these algorithms. In addition, the capacity of hospitals, capacity of accommodation centers, cost of transferring from each building block to accommodation centers or hospitals and the fixed cost of building or equipping an accommodation center were also obtained randomly and used in solving the proposed mathematical model. As can be seen, the randomly generated problems are presented in Table 3.
Details of raised problem
Average of final cost for each algorithm
Time to solve each problem using each algorithm (per second)
As we know, the performance of any meta-heuristic algorithm depends on two factors, cost and execution time. Therefore, in order to make a correct comparison between the algorithms, each algorithm is 1000 repetitions and on average is executed 10 times. The maximum computational time allowed is considered. Therefore, according to the coding and analysis of these seven meta-innovative algorithms studied in MATLAB environment, in Tables 4 and 5, respectively, the average final cost of each problem in each meta-heuristic algorithm and time for execution of each issue is placed.
The results of Tables 4 and 5 show that the three algorithms ACO, ABC and LAFA have lower cost and execution time than the other algorithms. Therefore, we use the above three algorithms to solve the case study.
As mentioned before, the case study in this article is District 9 of Mashhad Municipality. According to the information obtained from ARC GIS software and also the data of District 9 of Mashhad, the data of the problem in question are as mentioned underneath. Also, the number of building blocks (origin) according to the data is estimated at 1310 blocks. The distances between the side streets of a block are considered.
Number of building blocks: 1310
Number of candidate accommodation centers: 20
Number of medical centers in the region: 3
Total population of the region: 330,000
According to crisis management databases, about 90% of people are able to move to temporary shelters after a major earthquake. And the remaining 10% suffer from severe injuries and must be taken to a medical facility. Also, in this article, 4 square meters of space is provided for temporary accommodation in each person. The distances between the building blocks and the candidate accommodation centers as well as the medical centers are calculated by the Euclidean distance method according to Eqation 11:
The parameters are the coordinates of the desired points on the map, which are available in the relevant layer in ARC GIS software.
Fig 2 shows the location of the proposed treatment centers in zone 9. The case study problem is solved with three algorithms ACO, ABC and LAFA and the selected accommodation centers, how to allocate building blocks to accommodation centers as well as to medical centers are determined. The runtime performance of the three algorithms is compared in Fig 3.
As can be seen, due to the large population in the 9th district of Mashhad, there is a need to establish accommodation centers with higher reception capacity. Candidate centers for housing in the east and south of the region must all have a high capacity to accept people, otherwise the construction of less than 7 of them is not economical due to the final solution of ultra-innovative algorithms. And the remaining blocks in those areas will have to travel long distances to settle, which, of course, increases the likelihood of casualties to those affected by the earthquake. Therefore, considering the use of the area, it is recommended to allocate a space with a higher capacity for accepting people, in the east, south and west of the region, which are relatively ready to accept people after the crisis.
In this paper, a mathematical model is considered by taking into account the capacity constraint, in crisis situations, for locating and allocating people to temporary accommodation and medical centers, after the earthquake. After designing the model, random problems with hypothetical data are created. These problems are solved using GAMS software and seven meta-innovative algorithms SA, PSO, ICA, ACO, ABC, FA, LAFA. The results obtained in this section show that the solution time and the difference between the final solution of the objective function in the three meta-heuristic algorithms ACO, ABC and LAFA are less than the other meta-heuristic algorithms and the final solution is close to the optimal state. The purpose of these issues is to assess the validity of the proposed model at different scales, as well as to investigate the performance of the meta-heuristic algorithms used according to the results of the model solution. In the continuation of this article, by designing a case study, for district 9 of Mashhad, this problem has been solved in two steps. In order to bring the situation closer to reality, in the first step, the places nominated for housing in District 9 of Mashhad have been identified, and in the next step, considering the purpose and limitations of the model, the best housing and optimal allocation of people to Safe places and medical centers in the region, after solving the model with the three meta-innovative algorithms mentioned above, have been obtained. The results show. Convergence time in LAFA algorithm is less than other meta-algorithms.
All authors contributed to the literature review, design, data collection and analysis, drafting the manuscript, read and approved the final manuscript.
CONFLICTS OF INTEREST
The authors declare no conflicts of interest regarding the publication of this study.
No financial interests related to the material of this manuscript have been declared.