Multiobjective Site Selection Model for Wartime Shelters in Urban Areas

Kuo-Chi Yen^*, Wu-Chiao Shih, Wei Chang

Department of Logistics Management, National Defense University, Taipei City.

DOI: 10.4236/cus.2023.113027                

Abstract

Industrial and economic development primarily occurs in densely populated urban areas in Taiwan. The outbreak of war in such areas could have severe consequences. Disaster relief and homeland defense efforts are affected by the location of wartime shelters. This study explored the perceived utility of the evacuation time, the risk-utility of road blocking, and the cost factors associated with constructing shelters related to governance. A location model for wartime shelters in cities was established on the basis of these factors. Because random weights can affect the resolution of a random-weighted genetic algorithm (RWGA), a robust random-weighted method (RRWM) was developed. The validity and feasibility of the location model were examined through numerical analysis. The convergence of the RRWM was analyzed and compared with that of the RWGA and a single-objective genetic algorithm. The results indicate that the proposed algorithm exhibits satisfactory performance and can facilitate evaluation and decision-making related to the selection of urban shelter locations during wartime.

Keywords

Location Problem, Multiobjective Programming, Wartime Shelter

1. Introduction

War is a major human-made disaster that can damage cities, similar to natural disasters such as typhoons and earthquakes (Bashawri, Garrity, & Moodley, 2014) . The war between Russia and Ukraine has demonstrated how during war, large numbers of affected people must immediately take refuge in safe facilities. Shelters are crucial to homeland defense and disaster prevention in urban areas.

The National Science and Technology Center for Disaster Reduction and local governments in Taiwan have created evacuation sites in cities for natural disasters. Evacuation sites for national security issues are also crucial. Homeland defense and refugee sites must be selected to ensure national security and facilitate refugee resettlement. Site selection is a complex and politically sensitive process that requires the careful consideration of multiple factors and stakeholders’ perspectives. Victims’ perspectives and the distance from potential threats must also be considered when selecting appropriate sites. Sites for refugees and other victims of wartime disasters should provide material reserves and resources for basic survival. Supplies should be stockpiled in such facilities to meet safety standards.

Several studies have suggested that the distance and time required to seek refuge should be considered during site selection (Bayram, Tansel, & Yaman, 2015; Kongsomsaksakul, Yang, & Chen, 2005) . However, city residents may also be affected by psychological factors such as panic and fear during a disaster because of the chaos caused by the interruption of urban traffic networks and the breakdown of communication. Lin et al. (2013) suggested that panic following a disaster can cloud individuals’ judgment. The public may not act rationally during a disaster (Chopra, Lovejoy, & Yano, 2004) . According to prospect theory (Kahneman & Tversky, 1979, 2000) , effective decision-making behavior is based on bounded rationality. Studies evaluating shelters have increasingly focused on subjective feelings such as satisfaction with the evacuation time (Shen et al., 2015) . Residents’ decisions regarding shelters are affected by their perceptions of the evacuation time and distance to shelters. The perceived evacuation time must be considered to predict city residents’ preferences for shelters during a war.

War can destroy infrastructure and drastically change urban spaces. City residents may struggle to accurately assess risk in such conditions. Road congestion can prevent residents from reaching shelters and should thus be considered when the location of shelters is selected. Resources should be allocated for constructing environments for refugees that adhere to disaster resistance standards.

This study investigated city residents’ perceived time required to reach a shelter and shelters’ accessibility, costs, and capacity. This study also developed a multiobjective model for site selection for urban shelters during wartime. Shelters should be constructed before the occurrence of a war, and the public should be informed of their location through civil defense activities and policy promotion; this can enable the public to quickly seek refuge in the event of war.

A multiobjective problem involves a trade-off between objectives. The optimal solution can be obtained using the random-weighted genetic algorithm (RWGA; Murata & Ishibuchi, 1995 ). However, because the RWGA is affected by weight, the quality of its solutions is inconsistent. We incorporated the elitism method into the RWGA to develop a robust random-weight method (RRWM). In the RRWM, the coverage and distribution of the solution set are used to evaluate and improve solutions.

The rest of this paper is organized as follows. First, the research topic is analyzed and explained. Second, relevant studies are reviewed. Third, the proposed multiobjective site selection model is described. Fourth, a robust stochastic weighting method is proposed for the developed model, and a method for evaluating the multiobjective solution set is presented. Fifth, an example network is described for Zhongzheng District in Taipei City. This network is used to test the accuracy and applicability of the proposed model. The results obtained using the proposed model are compared with those obtained using other algorithms; the proposed model outperforms the other algorithms. Finally, the conclusions, applications of the proposed model, and directions for future research are presented.

2. Problem Analysis and Literature Review

2.1. Shelter Location Selection Model

Current, Min, & Schilling (1990) used a multiobjective approach to solve the site selection problem. These approaches have been used to solve site selection problems in various fields. Fan (2014) obtained the relative weights of various assessment factors by using an expert questionnaire and the analytic hierarchy process. Their results can serve as reference for the assessment of flood shelters. Farahani et al. (2012) comprehensively examined the models, solutions, and applications of coverage problems for site selection. To solve a site selection problem for disasters, Li et al. (2011a, 2011b) proposed a coverage location model and applied various algorithms.

Sherali, Carter, & Hobeika (1991) studied flood shelters and proposed a bilevel planning model. The upper-level problem is a site selection problem for evacuation facilities that is aimed at minimizing the time required to reach a shelter. The lower-level problem is related to the route between residents’ homes and a shelter. Their study used a genetic algorithm (GA) to solve this two-level problem.

Pérez-Galarce et al. (2017) considered earthquake disasters in urban areas. They developed a flexible model for optimizing the service quality of shelters after disasters. The model also enables the provision of medical assistance and can improve the functioning of shelters. Boonmee, Arimura, & Asada (2017) discussed models for facilities such as distribution centers, warehouses, shelters, and medical centers. They proposed a model that can be used to select sites for shelters based on the characteristics of the disaster, the needs of the victims, and the principle of equity.

2.2. Objective and Limiting Factor Affecting Shelter Site Selection

The public’s perception of the urban environment can change after or during war, and these changes should be considered during shelter site selection. Panic, which can be caused by war, can also affect judgment and can lead to imperfect rationality (Chopra et al., 2004) or bounded rationality (Kahneman & Tversky, 1979, 2000) ; site selection for shelters should also account for this. If a shelter location is selected on the basis of distance (Berman & Krass, 1998) and without considering the public’s perceptions, the site may not be appropriate. Residents’ perceptions of the distance to shelters and the evacuation time constitute their perceptions of the perceived utility of a shelter (Li et al., 2011a, 2011b) . People from affected areas may perceive shelters differently (Ma & Wu, 2006) . Shen et al. (2015) created a linear model based on the evacuation time to evaluate satisfaction with shelters. However, during war, perceptions of space and time change because of various pressures. For this reason, a more accurate method for evaluating the perceptions of shelters during wartime should be developed.

Military combat can disrupt road networks, cause buildings to collapse, and result in the destruction of underground pipelines; one priority during shelter site selection is to minimize risks from these possibilities. Hsu and Lu (2002) explored the risks associated with road blockages due to earthquakes. They created a joint utility function combining the risk of blockages with the effect of traffic congestion to determine the ideal path of earthquake relief. Shen et al. (2015) revealed that road accessibility affected the selection of shelter sites in a chemical industry zone. The government should develop a site selection model based on human vulnerability that maximizes road accessibility. In addition, the appropriate amount of resources should be allocated to shelter construction. Karatas (2017) noted that the cost of construction affects site selection. Chen, Chen, & Li (2010) explored costs and benefits as factors affecting the selection of a shelter site. They identified two priorities, namely minimizing distance and minimizing cost, and they developed three hierarchical site selection models for shelters. Construction cost is a key variable in the model.

Evacuation facilities are limited by the number of people they can accommodate. Therefore, the choice of refuge facilities will be affected by this factor. Capacity is a crucial limiting factor. Current and Storbeck (1988) created a location selection model that accounts for capacity. Wu, Zhang, & Zhang (2006) proposed a location selection model that accounts for capacity and construction costs. Li et al. (2011a, 2011b) indicated that models that account for capacity are superior to other models because they accurately reflect reality.

2.3. Multiobjective Programming Models and Algorithms

Multiobjective programming is a mathematical method for solving decision problems with limited resources and conflicting objectives. Kuhn and Tucker (1951) determined the optimality conditions for effective solutions, which laid the foundation for multiobjective theory. Mathematical programming is used to evaluate trade-offs between objectives and obtain noninferior or nondominated solutions. Multiobjective optimization has been extensively studied and applied to numerous fields. Shukla and Deb (2007) categorized methods of solving multiobjective optimization as either traditional or nontraditional. Evolutionary multiobjective optimization (EMO), a nontraditional method, is based on natural selection. EMO is used to identify optimal Pareto sets from all feasible solutions. The graph surface formed by all nondominant solutions is called the Pareto front.

Alçada-Almeida et al. (2009) explored the safety of evacuation plans by using a multiobjective planning approach involving a geographic information system and multiobjective programming model in a decision support system. Zhou, Liu, & Wang (2010) proposed a multiobjective model for selecting the sites of urban shelters. The model incorporates the maximum-weighted minimum distance as well as the weighted and maximum coverage areas for shelters. Coutinho-Rodrigues, Tralhão, & Alçada-Almeida (2012) developed a multiobjective model for planning evacuation paths and shelter locations by using six objectives, namely risks associated with paths and shelter locations, length of evacuation paths, and evacuation time. Because of the complexity of urban disasters, the locations of shelters are often selected through multiobjective planning.

Most relevant algorithms are based on evolutionary algorithms (EAs). Because of their suitability for complex problems, search algorithms have also been applied to optimization problems (Deb, 2011) . In EAs, adaptive individuals with various genetic characteristics can be selected from a population on the basis of environmental fitness. EAs can be categorized by their design elements into those for individual representation, parent selection, and operating mode. Evolutionary programming, evolutionary strategies, and GAs are examples of EAs, with GAs being the most common EAs.

Multiobjective GAs (MOGAs) are used to develop adaptive functions. Numerous MOGAs have been developed to solve multiobjective problems by evaluating adaptive functions. Konak, Coit, & Smith (2006) categorized MOGAs by their adaptive functions and algorithm programs and compared them. The aggregation function was the first to be developed and is the most direct approach to solving multiobjective optimization problems. In this method, a single-objective solution to a multiobjective problem is obtained by adjusting the weight coefficient through combination or aggregation. The RWGA proposed by Murata & Ishibuchi (1995) is based on weight summation. Murata & Ishibuchi (1995) compared the RWGA with the vector-evaluated GA (VEGA). Their results revealed that the RWGA yielded more efficient solutions than did the VEGA.

2.4. Comprehensive Evaluation and Analysis

On the basis of the literature, this study involved a comprehensive evaluation of site selection based on the P-median problem and service time satisfaction problem (Ma & Wu, 2006; Shen et al., 2015) . Fiedrich, Gehbauer, & Rickers (2000) identified the utility function, in which distance is converted into the perceived utility of the evacuation time, as a key objective in developing a site selection model. A secondary objective would be to consider access to shelters when urban networks are disrupted. This study used the risk of roadblocks to investigate accessibility to shelters. The appropriate resources must also be prepared for each shelter to meet users’ needs. For this reason, this study also considered shelters’ costs.

The purposes of the proposed model are to maximize the perceived utility of evacuation, maximize network access risk, and minimize the cost of shelter construction, which are crucial to protecting those seeking refuge. The model is based on trade-offs. The RWGA, which is based on the MOGA, was adopted for the programming model and improved to facilitate the solution of the multiobjective problem. Here, the model objectives, Constraintss and algorithms of this study are described in Table 1 form as follows.

3. Research Model Construction

Individuals leave areas affected by war to seek shelter. Distance may be the main factor in their search, and the travel time can be neglected. However, changes in urban spaces during war may cause the public to act in a state of bounded rationality, and they may perceive distance incorrectly.

The services provided by shelter j are not determined by its distance from disaster node i. Evacuation time t_ij from disaster node i to shelter j should be the basis for assessment. L_i denotes the longest time people at disaster node i would be willing to travel to evacuate to shelter j; $t_{ij}\le L_i$ indicates that people at disaster node i would feel safe traveling to shelter node j. U(t_ij) is the perceived utility of evacuation from disaster node i to shelter j, and L_i,desired is the desired evacuation time from disaster node i to shelter j. During war, individuals are anxious and expect to reach shelters in the shortest possible time; in addition, the evacuation time is affected by various aspects of war. Through the use of the definitions of Ren, Zeng, & Wang (2016) and Chou, Hsu, & Chen (2008) , this study defined the ideal evacuation time as follows:

$L_{i,desired}=\frac{t_{ij,optimistic}+4t_{ij}+{\text{Max}}_{ij}{t}_{ij}}{k},k=6$ (1)

where t_ij is the actual evacuation time from node i to shelter j, and ${\text{Max}}_{ij}{t}_{ij}$ is the longest evacuation time from node i to shelter j. Psychological factors affecting those seeking shelter are modeled using a trade-off among t_{ij,optimistic}, t_ij, and ${\text{Max}}_{ij}{t}_{ij}$ for evaluating the perceived evacuation time. To normalize the perceived evacuation time, this factor was transformed into a utility value between 0

Table 1. Model and algorithm specification.

and 1. The utility function for the perceived evacuation time is presented in Equation (2).

$U_a\left(t_{ij}\right)={\left[\frac{{\text{Max}}_{ij}{t}_{ij}-t_{ij}}{{\text{Max}}_{ij}{t}_{ij}-L_{i,desired}}\right]}^{k_i}$ (2)

We assumed that the utility function of the perceived evacuation time would be nonlinear. Variable k_i is the sensitivity coefficient for the evacuation time. This parameter represents the sensitivity of people in different regions (e.g., cities and rural areas) to the evacuation time. The higher k_i is, the higher the gradient of the utility function of the perceived evacuation time is, which indicates greater time sensitivity. Ma and Wu (2006) suggested that k_i should be between 0.5 and 1.5. The effect of sensitivity coefficient k_i is illustrated in Figure 1. Individual perceptions of the evacuation time can vary, even among individuals from the same area. However, the aim of the present study was not to estimate interindividual heterogeneity. For this reason, the utility function of the perceived evacuation time was defined with an assumption of homogeneous sensitivity coefficients.

On the basis of the suggestions provided by Hsu and Lu (2002) and Shen et al. (2015) , a roadblock can occur because of the collapse of a building and other factors. For a known roadblock, a utility function is used to convert the corresponding risk value into a utility value. In this study, the utility function for roadblock risk was a decreasing exponential utility function. If the roadblock probability is 0, the link, that is, a section of a path from disaster node i to shelter j, is unaffected, and the utility value is 1. If the roadblock probability is 1, the link is severely damaged, and its safety and reliability are extremely low; thus, the utility value is 0. The utility function of roadblock risk for link a is as follows:

$P_a=-0.198+1.198{\text{e}}^{-R_a}0\le R_a\le 1,\forall a\in A$ (3)

Figure 1. Perceived utility function of evacuation time.

where R_a is the roadblock probability for link a. The utility value of the roadblock risk reflects the safety and reliability of the road. It also represents the probability of successfully passing through a link. The higher the utility of the roadblock risk is for a link, the higher the probability is that the road can be used to reach shelter. In this study, the utility of the roadblock risk of link a is defined as the passability of link a, as presented in Equation (3). Variable $u_k^{ij}$ is the utility value of roadblock risk for path k from disaster node i to shelter j. Similarly, $p_k^{ij}$ is the probability that path k can be used to travel from disaster node i to shelter j. The risk of a roadblock on a link and the utility value of the risk of a roadblock are defined as follows:

$p_k^{ij}={\displaystyle {\prod }_{a=1}{P}_a{\delta }_{ak}^{ij}}\forall i\in I,j\in J,k\in K$ (4)

$u_k^{ij}=p_k^{ij}\forall i\in I,j\in J$ (5)

where ${\delta }_{ak}^{ij}$ indicates whether link a is included in path k from disaster node i to shelter j. If link a is included in path k, then ${\delta }_{ak}^{ij}=1$ ; otherwise, ${\delta }_{ak}^{ij}=0$ . For simplicity, Equation (4) can be rewritten as follows by taking logarithms on both sides:

$\log p_k^{ij}=\log P_1{\delta }_{1k}^{ij}+\log P_2{\delta }_{2k}^{ij}+\cdots +\log P_a{\delta }_{ak}^{ij}\forall i\in I,j\in J,k\in K$ (6)

Equations (5) and (6) can then be combined as follows:

$u_k^{ij}={\displaystyle {\sum }_a\log P_a{\delta }_{ak}^{ij}}\forall i\in I,j\in J,k\in K$ (7)

The cost of constructing shelters is based on the investment of resources at sites to meet certain conditions. If the number of shelters is unknown, construction costs should be used instead, with at least one shelter being constructed. The number of shelters to be constructed depends on construction costs and cannot exceed a maximum number of alternative sites N.

The multiobjective model comprises three objectives, represented by Equations (8)-(10): maximizing the utility of the perceived evacuation time (Objective 1), maximizing the utility of roadblock risk (Objective 2), and minimizing the construction costs of shelters (Objective 3). These objectives are subject to various restrictions, which are presented in Equations (11)-(21).

$\text{Max}{Z}_1={\displaystyle {\sum }_{i\in I}{\displaystyle {\sum }_{j\in J}{h}_{ij}f\left(t_{ij}\right)y_{ij}}}$ (8)

$\text{Max}{Z}_2={\displaystyle {\sum }_{i\in I}{\displaystyle {\sum }_{j\in J}{u}_k^{ij}{y}_{ij}}}$ (9)

$\min Z_3={\displaystyle {\sum }_{j\in J}{C}_j{x}_j}$ (10)

These equations are subject to the following restrictions:

${\displaystyle {\sum }_{j\in J}{y}_{ij}}\ge 1\forall i\in I$ (11)

${\displaystyle {\sum }_i{y}_{ij}}\le n{x}_j\forall i\in I,j\in J$ (12)

${\displaystyle {\sum }_{i\in I}{h}_{ij}}\le ca{p}_j{x}_j\forall j\in J$ (13)

${\displaystyle {\sum }_{j\in J}{h}_{ij}}={\bar{h}}_i\forall i\in I$ (14)

${\displaystyle {\sum }_{i\in I}{h}_{ij}}={\hat{h}}_j\forall j\in J$ (15)

$p_k^{ij}={\displaystyle {\prod }_{a=1}{P}_a{\delta }_{ak}^{ij}}\forall i\in I,j\in J,k\in K$ (16)

$u_k^{ij}={\displaystyle {\sum }_a\log P_a{\delta }_{ak}^{ij}}\forall i\in I,j\in J,k\in K$ (17)

$h_{ij}\ge 0\forall i\in I,j\in J$ (18)

$x_j=\left\{0,1\right\}\forall j\in J$ (19)

$y_{ij}=\left\{0,1\right\}\forall i\in I,j\in J$ (20)

${\delta }_{ak}^{ij}=\left\{0,1\right\}\forall i\in I,j\in J,a\in A$ (21)

According to Equation (11), at least one shelter must be provided for each disaster node i. Equation (12) indicates that multiple nodes can be simultaneously assigned to a single shelter. According to Equation (13), the total capacity of the shelter must be greater than or equal to the total number of individuals seeking shelter. Equations (14) and (15) are conservation constraints for the number of individuals seeking shelter. Equation (16) represents the probability that path k from node i to shelter j can be used. Equation (17) defines the utility of the risk of following path k from node i to shelter j. Equation (18) indicates that the number of individuals traveling from node i to shelter j is nonnegative. As indicated by Equation (19), if shelter j is open, then x_j = 1; otherwise, x_j = 0. According to Equation (20), if individuals travel from node i to shelter j, then y_ij = 1; otherwise, y_ij = 0. As indicated by Equation (21), if link a is part of path k, then ${\delta }_{ak}^{ij}=1$ ; otherwise, ${\delta }_{ak}^{ij}=0$ .

4. Solution Algorithm

4.1. Algorithm Steps

The RRWM has two components. In the first component, a fitness function is calculated through a compromise programming method (CPM; Israeli & Ceder, 1995 ), and the adaptive weight approach (AWA; Gen et al., 2008 ) is used to normalize the values of each objective function. Because the objectives may be in conflict, an approximation of the ideal solution can be obtained using the CPM to calculate the distance between the individual solutions and ideal solution. This approach can be considered an objective search method based on the $L_s^k$ distance function (Israeli & Ceder, 1995; Wu et al., 2006) . All solutions in the set are used to readjust the weights of each objective by using the AWA. The multiobjective EA is designed to tend toward the global solution. Therefore, the fitness function for a multiobjective problem can be redefined as follows to determine the closest ideal solution on the basis of the CPM and AWA:

$Z_i^k={\displaystyle {\sum }_{i=1}^q\frac{z_i^{\max }-z_i^k}{z_i^{\max }-z_i^{\min }}}\forall k\in SOL,i\in 1~q$ (22)

where SOL is the solution set for the multiobjective problem, q is the number of objectives, and $z_i^k$ is the value of the ith objective function of the kth solution in SOL. If objective i is fixed (e.g., i = 1), $z_i^k$ can be considered the result of the standardization of the kth solution in the solution set for objective i. Therefore, we can standardize each objective function as follows:

$z_i^{norm}\left(x\right)=\{\begin{array}{l}\frac{z_i\left(x\right)-z_i^{\min }}{z_i^{\max }-z_i^{\min }},\text{if}{z}_i^{\max }>z_i^{\min }\\ 0,\text{if}{z}_i\left(x\right)=z_i^{\min }\end{array}\forall i=1~k,x\in P$ (23)

$z_i^{norm}\left(x\right)=\{\begin{array}{l}\frac{z_i^{\max }-z_i(x)}{z_i^{\max }-z_i^{\min }},\text{if}{z}_i^{\max }>z_i^{\min }\\ 0,\text{if}{z}_i\left(x\right)=z_i^{\max }\end{array}\forall i=1~k,x\in P$ (24)

$F\left(x\right)={\displaystyle {\sum }_{i=1}^k{w}_i}\cdot z_i^{norm}\left(x\right),i=1~k,x\in P$ (25)

Equations (23)-(25) represent the method of normalizing the values of objective function i for a given solution x. In these equations, $z_i\left(x\right)$ and $z_i^{norm}\left(x\right)$ denote the values of the ith objective function before and after normalization, respectively, and $z_i^{\min }$ and $z_i^{\max }$ denote the minimum and maximum values of the ith objective function for solution x before normalization, respectively. After normalization, the values of the objective functions are between 0 and 1. The values of the normalized objective functions are multiplied by their respective weights, and the results are summed to obtain the fitness value for solution x. The fitness value of the multiobjective problem is presented in Equation (25).

In the second component of the RRWM, the optimal Pareto sets in each generation are adjusted on the basis of the weights randomly generated in each generation. This adjustment is reflected in the quality of the generation’s solution and the overall multiobjective solution. The elitist strategy is used to select the best solution from the optimal Pareto sets in each generation. Finally, the optimal Pareto set is obtained to normalize quality. The steps of the RRWM are as follows:

Step 1: Initiate the algorithm.

Step 2: Calculate the network values.

On the basis of given postdisaster information, the optimistic evacuation time t_{ij,optimistic}, actual evacuation time t_ij, and longest evacuation time ${\text{Max}}_{ij}{t}_{ij}$ between node i and shelter node j can be obtained using the shortest-path algorithm, and the utility function of the perceived evacuation time is derived using Equation (2). The value of the utility for roadblock risk P_a is obtained using the roadblock risk value R_a for each link a.

Step 3: Encode the network nodes.

Binary gene encoding [0, 1] with decision variable y_ij is used under the assumption that the chromosome length is equal to the total number of shelter and disaster nodes, with 0 representing a disaster node and 1 representing a shelter node. Each chromosome represents a feasible solution—a configuration of shelter nodes.

Step 4: Randomly generate an initial population of chromosomes, place the initial population in N_pop, and set the total number of generations T.

Step 5: Evolve the chromosomes.

Subsequently, determine whether the chromosomes conform to the model constraints, and calculate the values of the objective functions for the chromosomes in N_pop that meet these constraints. These values are normalized using Equations (23) and (24). The current Pareto solution set is updated using these normalized values.

Step 6: Calculate the fitness value.

Equation (26) is used to obtain the random weights, which are substituted into Equation (25) to calculate the fitness value for each chromosome. A linear proportional transformation function [presented in Equation (27)] is used to calculate p_i. Next, N_pop/2 pairs of chromosomes are selected from N_pop for mating and mutation.

$w_i=\frac{rando{m}_i(\cdot )}{{\displaystyle {\sum }_{j=1}^{n}rando{m}_j(\cdot )}},i=1,2,\cdots ,n$ (26)

$p_i=\frac{z_i-z_{\min }}{{\displaystyle {\sum }_{j=1}^n\left(z_j-z_{\min }\right)}}$ (27)

Step 7: Select the elite chromosomes (N_elite) from the Pareto optimal solution set.

The chromosomes with the highest fitness values in the Pareto optimal solution set are used as the elite chromosomes (N_elite).

Step 8: Perform mating.

The single-point mating method is applied to the selected chromosomes, with a mating rate R_C of 0.8 and randomly selected mating sites. Two new chromosomes are produced, with the mating site serving as the baseline. This mating mechanism yields new chromosomes for population N_pop.

Step 9: Perform mutation.

A certain number of genes in the chromosome are mutated at mutation rate R_m of 0.06. The selected genes are mutated from 0 to 1 or from 1 to 0.

Step 10: Apply the elitist strategy.

A certain number of N_elite chromosomes are randomly removed from population N_pop. Next, N_elite additional chromosomes are randomly selected from the current Pareto optimal solution set and added to N_pop to replace the chromosomes that were randomly removed.

Step 11: Terminate the algorithm in accordance with the condition.

The condition for termination is reaching the maximum number of generations T. If this condition is satisfied, the algorithm is terminated. If the condition is not satisfied, t is set to t + 1, and the process returns to Step 4. This algorithm yields a set of elite Pareto optimal solutions, from which a suitable compromise solution can be selected.

4.2. Evaluation of Solution Sets for Multiobjective Problem

In the MOGA, solutions are obtained by approaching the Pareto optimal front through continuous evolution. This study assessed solution sets by using the multiobjective problem methods proposed by Zitzler, Deb, & Thiele (2000) . The solution sets were evaluated in terms of diversity and convergence. The evaluation methods are as follows:

1) The convergence of solution sets: Zitzler et al. (2000) proposed an evaluation method based on the convergence of solution sets. Under the assumption that $P^{\prime },P^{″}\subseteq P^{\prime }$ are two solution sets in the multiobjective space, a mapping from $\left(P^{\prime },P^{″}\right)$ to the interval [0, 1] can be used to obtain coverage rate CS of $P^{\prime }$ and $P^{″}$ . Parameter $CS\left(P^{\prime },P^{″}\right)$ is presented as follows:

$CS\left(P^{\prime },P^{″}\right)\triangleq \frac{\left|\left\{x^{″}\in P^{″}|\exists x^{\prime }\in P^{\prime },x^{\prime }\succ x^{″}\text{or}{x}^{\prime }=x^{″}\right\}\right|}{\left|P^{″}\right|}$ (28)

According to Equation (28), if all solutions $x^{\prime }$ in $P^{\prime }$ are dominant or equal to all solutions $x^{″}$ in $P^{″}$ , then the coverage rate is equal to 1. Thus, the coverage rate is between 0 and 1.

2) Spatial distribution of the solution set: In this study, the three objectives were optimized simultaneously. After being normalized, the objective function values were plotted in a three-dimensional space. The method proposed by Zitzler et al. (2000) was used to calculate the spatial distribution of the solution set in the space defined by the normalized objective function values, as presented in Equation (29). The lower the standard deviation is, the lower the average and minimum distances between members of the solution set are, and the more uniform the distribution of the solution set is in the space defined by the normalized objective function values.

$dtrb=\sqrt{\frac{1}{k-1}{\displaystyle {\sum }_{i=1}^k{\left(\bar{d}-d_i\right)}^2}}$ (29)

5. Numerical Analysis

5.1. Test Network Data

This study used Zhongzheng District, Taipei City, as a test network. The network contains 31 villages, 153 nodes, and 481 road links (Figure 2). The green nodes represent the 32 alternative shelters, such as Zhong-Yi Primary School. The network information is presented in Table 2 and Table 3.

5.2. Testing and Analysis

This study used the RRWM to solve the multiobjective problem of selecting urban shelter sites. The number of selected shelters should not exceed the total number of available sites (i.e., 32). The total number of chromosomes in N_pop was set to 500, the number of generations was set to 500, mating rate R_c was set to 0.8, and mutation rate R_m was set to 0.06.

With 500 generations, the RRWM was able to search the entire solution space. The total computation time was 249 s, and 500 feasible solution were obtained.

Figure 2. Network for Zhongzheng District, Taipei City.

Table 2. Network information for Zhongzheng District, Taipei City.

Table 3. Affected nodes.

In this set, all solutions have a fitness value for the multiobjective problem. The fitness value of each solution can be obtained by Equation (25). The fitness value is used to evaluate the degree of compromise solution of multiobjective problem. The minimum fitness value was 0.58, which was obtained in this set. The shelters corresponding to the optimal compromise were shelter numbers 122, 123, 126, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 143, 144, 147, 148, 149, 150, 152, and 153. According to Equations (8)-(10), the total utility of the perceived evacuation time was 19257.55 (Objective 1), the total utility of roadblock risk was 67.92 (Objective 2), and the total construction cost was NT$77 million (Objective 3).

Table 4 presents the assignment of individuals from disaster nodes to shelters. For example, the number of individuals at node 8 was 235. Because of capacity constraints, 144 individuals were assigned to node 132 for shelter. On the basis of the allocation mechanism, the remaining 91 individuals were assigned to node 140, which exhibited the second highest utility of the perceived evacuation time. Overall, the number of individuals assigned to the shelter nodes was equal to the number of individuals at the disaster nodes. Table 5 presents the relationship between the holding status and capacity of shelters, which were consistent. For example, at Guling Park (shelter node 150), individuals from five disaster nodes sought shelter at node 150. The number of individuals was 510. The site selection conditions based on all objectives satisfied the capacity constraints on the shelters.

Table 4. Assignment of individuals from disaster nodes to shelters.

Table 5. Relationship between choice of shelter and capacity of shelters.

5.3. Convergence to the Pareto Optimal Front

The fitness values and normalized target values of two elite Pareto optimal solution sets were input into Equation (28), and a coverage rate of 94% was obtained. This result indicates that the new solution was superior to the previous solution set. Subsequently, the normalized objective function values ( ${Z^{\prime }}_1$ , ${Z^{\prime }}_2$ , ${Z^{\prime }}_3$ ) of the Pareto optimal solution set were input into Equation (29), and a spatial distribution of 0.018972 was obtained. This value indicates the degree to which the nondominated solutions were uniformly distributed in the three-dimensional space defined by the normalized objective values. We used STATISTICA (version 6.1, TIBCO Software, Palo Alto, CA, USA) to plot the spatial distribution of the solution set (Figure 3). The distribution of the solution set near the origin was similar to that of the Pareto optimal front, demonstrating the suitability of the RRWM.

Table 6 presents a comparison of the results of the RRWM, RWGA, and single-objective GA (SOGA). The performance of the optimal solution set obtained using the RRWM was evaluated. Eight weight values from the SOGA were tested. The number of solution sets (N_pop) and the number of generations were 500 for the RRWM, RWGA, and SOGA. Table 6 also presents the adaptation values, spatial distributions, and coverage rates of the algorithms. Equation (25) was used to obtain the RRWM fitness value of 0.58, which was superior (lower) to those obtained for the other algorithms. The coverage rate of the RRWM was 94%, and its spatial distribution was 0.018972. Unlike the RWGA and SOGA, the RRWM achieved robust convergence in terms of solution performance and coverage rate.

Figure 3. Spatial distribution of the RRWM solution set.

Table 6. Convergence of algorithms.

Figure 4. Spatial distribution of the RWGA solution set.

The solution set obtained by the RWGA did not form a Pareto front (Figure 4). The spatial distribution of the SOGA was optimized with weights of 0.92, 0.04, and 0.04 (Figure 5). However, this solution set did not form a Pareto front either. Although the spatial distribution of the RRWM was suboptimal, the solution set was similar to a Pareto front when plotted in the space defined by the normalized objective function values. The solution set of the RWGA was oriented along the ${Z^{\prime }}_1$ -axis, with a suboptimal spatial distribution. For the other weighting strategies, the solution sets were oriented in the direction of the axis with the highest enactment value (i.e., aligned to the specific weight ratio).

Figure 5. Spatial distribution of the soga solution set with different target weights.

6. Conclusion and Recommendations for Future Work

This study developed a model for site selection for shelters during war. The model involves a trade-off among the utility of the perceived evacuation time, the utility of roadblock risk, and the cost of shelter construction. Accordingly, the relationships between these parameters were modeled using a multiobjective model. The locations selected for shelters should be a compromise between these parameters. The number of people required moving from disaster nodes to shelter nodes and the capacities of the shelters were also considered in the model.

Unlike the RWGA, the proposed RRWM includes an elitist mechanism and is designed to evolve an evenly distributed trade-off frontier defined by nonconvex functions. The RRWM yields a nondominated solution set with a satisfactory distribution; therefore, it may provide valuable assistance to decision-makers. The results indicate that the proposed model has flexibility for practical planning problems and is effective in evaluating decision schemes.

Information on the utility of the perceived evacuation time and the utility of roadblock risk should be collected through regular household surveys. The main focus of this study was modeling and algorithm design. Studies can apply and evaluate the model and add parameters after calibration to ensure that the results are suited to each situation.

Acknowledgements

The authors thank anonymous referees for their helpful and constructive comments for improving the paper. In addition, the study was supported by the Ministry of Science and Technology (Project No. 108-2410-H-606-007-). Finally, this manuscript was edited by Wallace Academic Editing.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Alçada-Almeida, L., Tralhão, L., Santos, L., & Coutinho-Rodrigues, J. (2009). A Multiobjective Approach to Locate Emergency Shelters and Identify Evacuation Routes in Urban Areas. Geography Analysis, 41, 9-29. https://doi.org/10.1111/j.1538-4632.2009.00745.x
[2]	Bashawri, A., Garrity, S., & Moodley, K. (2014). An Overview of the Design of Disaster Relief Shelters. Procedia Economics and Finance, 18, 924-931. https://doi.org/10.1016/S2212-5671(14)01019-3
[3]	Bayram, V., Tansel, B. C., & Yaman, H. (2015). Compromising System and User Interests in Shelter Location and Evacuation Planning. Transportation Research Part B: Methodological, 72, 146-163. https://doi.org/10.1016/j.trb.2014.11.010
[4]	Berman, O., & Krass, D. (1998). Flow Intercepting Spatial Interaction Model: A New Approach to Optimal Location of Competitive Facilities. Location Science, 6, 41-65. https://doi.org/10.1016/S0966-8349(98)00047-3
[5]	Boonmee, C., Arimura, M., & Asada, T. (2017). Facility Location Optimization Model for Emergency Humanitarian Logistics. International Journal of Disaster Risk Reduction, 24, 485-498. https://doi.org/10.1016/j.ijdrr.2017.01.017
[6]	Chen, Z. F., Chen, J., & Li, Q. (2010). Study on Hierarchical Location of Urban Emergency Shelters (II)—Three-Hierarchical Location Models. Journal of Natural Disasters, 19, 13-19. (In Chinese)
[7]	Chopra, S., Lovejoy, W., & Yano, C. (2004). Five Decades of Operations Management and the Prospects Ahead. Management Science, 50, 8-14. https://doi.org/10.1287/mnsc.1030.0189
[8]	Chou, T.-Y., Hsu, C.-L., & Chen, M.-C. (2008). A Fuzzy Multi-Criteria Decision Model for International Tourist Hotels Location Selection. International Journal of Hospitality Management, 27, 293-301. https://doi.org/10.1016/j.ijhm.2007.07.029
[9]	Coutinho-Rodrigues, J., Tralhão, L., & Alçada-Almeida, L. (2012). Solving a Location-Routing Problem with a Multi-Objective Approach: The Design of Urban Evacuation Plans. Journal of Transport Geography, 22, 206-218. https://doi.org/10.1016/j.jtrangeo.2012.01.006
[10]	Current, J. R., & Storbeck, J. E. (1988). Capacitated Covering Models. Environment and Planning B: Urban Analytics and City Science, 15, 153-163. https://doi.org/10.1068/b150153
[11]	Current, J. R., Min, H., & Schilling, D. (1990). Multiobjective Analysis of Facility Location Decisions. European Journal of Operational Research, 49, 295-307. https://doi.org/10.1016/0377-2217(90)90401-V
[12]	Deb, K. (2011). Multi-Objective Optimization Using Evolutionary Algorithms: An Introduction. In L. Wang, A. H. C. Ng, & K. Deb (Eds.), Multi-Objective Evolutionary Optimisation for Product Design and Manufacturing (pp. 3-34). Springer. https://doi.org/10.1007/978-0-85729-652-8_1
[13]	Fan, C. A. (2014). A Study on Assessing Rules of Flood Refuge. MSc. Thesis, National Chiao Tung University. (In Chinese)
[14]	Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M., &Goh, M. (2012). Covering Problems in Facility Location: A Review. Computers & Industrial Engineering, 62, 368-407. https://doi.org/10.1016/j.cie.2011.08.020
[15]	Fiedrich, F., Gehbauer, F., & Rickers, U. (2000). Optimized Resource Allocation for Emergency Response after Earthquake Disasters. Safety Science, 35, 41-57. https://doi.org/10.1016/S0925-7535(00)00021-7
[16]	Gen, M., Cheng, R., & Lin, L. (2008). Network Models and Optimization: Multi-Objective Genetic Algorithm Approach. Springer.
[17]	Hsu, T. P., & Lu, G. H. (2002). Development of the Minimal Risk Routing Model for Post-earthquake Traffic Management. Bulletin College of Engineering in National Taiwan University, 85, 33-48.
[18]	Israeli, Y., & Ceder, A. (1995). Transit Route Design Using Scheduling and Multiobjective Programming Techniques. In J. R. Daduna, I. Branco, & J. Piaxão (Eds.), Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems (pp. 56-75). Springer. https://doi.org/10.1007/978-3-642-57762-8_5
[19]	Kahneman, D., & Tversky, A. (1979). Prospect Theory: An Analysis of Decision under Risk. Econometrica, 47, 263-2291. https://doi.org/10.2307/1914185
[20]	Kahneman, D., & Tversky, A. (2000). Choices, Values, and Frames. In L. C. MacLean, & W. T. Ziemba (Eds.), Handbook of the Fundamentals of Financial Decision Making (pp. 269-278). Cambridge University Press. https://doi.org/10.1017/CBO9780511803475
[21]	Karatas, M. (2017). A Multi-Objective Facility Location Problem in the Presence of Variable Gradual Coverage Performance and Cooperative Cover. European Journal of Operational Research, 262, 1040-1051. https://doi.org/10.1016/j.ejor.2017.04.001
[22]	Konak, A., Coit, D. W., & Smith, A. E. (2006). Multi-objective Optimization Using Genetic Algorithms: A Tutorial. Reliability Engineering & System Safety, 91, 992-1007. https://doi.org/10.1016/j.ress.2005.11.018
[23]	Kongsomsaksakul, S., Yang, C., & Chen, A. (2005). Shelter Location-Allocation Model for Flood Evacuation Planning. Journal of the Eastern Asia Society for Transportation Studies, 6, 4237-4252.
[24]	Kuhn, H. W., & Tucker, A. W. (1951). Nonlinear Programming. In Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability (p. 220). University of California Press.
[25]	Li, J. G., Tang, X. M., Liu, Z. G., & Wang, H. B. (2011a). A Refuge Allocation Algorithm Based on Optimal Travel Distance and Limited Capacity Is Studied. Journal of Geodesy and Geoinformation Science, 40, 489-494. https://doi.org/10.1145/3474963.3474989
[26]	Li, X., Zhao, Z., Zhu, X., & Wyatt, T. (2011b). Covering Models and Optimization Techniques for Emergency Response Facility Location and Planning: A Review. Mathematical Methods of Operations Research, 74, 281-310. https://doi.org/10.1007/s00186-011-0363-4
[27]	Lin, Y. Y., Ding, C., Wu, C. G., Ma, T., & Jiang, X. (2013). Analysis on High Density Community Emergency Evacuation Behavior. Planners, 29, 105-109. (In Chinese)
[28]	Ma, Y., & Wu, H. (2006). Definitions and Curve Fitting of Time Satisfaction Functions in Facility Location Problems. In 2006 International Conference on Management Science and Engineering (pp. 429-433). IEEE.
[29]	Murata, T., & Ishibuchi, H. (1995). MOGA: Multi-Objective Genetic Algorithms. In Proceedings of 1995 IEEE International Conference on Evolutionary Computation. IEEE.
[30]	Pérez-Galarce, F., Canales, L. J., Vergara, C., & Candia-Véjar, A. (2017). An Optimization Model for the Location of Disaster Refuges. Socio-Economic Planning Sciences, 59, 56-66. https://doi.org/10.1016/j.seps.2016.12.001
[31]	Ren, Q. L., Zeng, K., & Wang, K. (2016). Model of Evacuation Route Choice in Emergency Traffic Based on Prospect Theory. Journal of Chongqing Jiaotong University (Natural Sciences), 35, 100-104. (In Chinese)
[32]	Shen, Y., Wang, Q., Yan, W., & Wang, J. (2015). A Transportation-Location Problem Model for Pedestrian Evacuation in Chemical Industrial Parks Disasters. Journal of Loss Prevention in the Process Industries, 33, 29-38. https://doi.org/10.1016/j.jlp.2014.11.008
[33]	Sherali, H. D., Carter, T. B., & Hobeika, A. G. (1991). A Location-Allocation Model and Algorithm for Evacuation Planning under Hurricane/Flood Conditions. Transportation Research Part B: Methodological, 25, 439-452. https://doi.org/10.1016/0191-2615(91)90037-J
[34]	Shukla, P. K., & Deb, K. (2007). On Finding Multiple Pareto-Optimal Solutions Using Classical and Evolutionary Generating Methods. European Journal of Operational Research, 181, 1630-1652. https://doi.org/10.1016/j.ejor.2006.08.002
[35]	Wu, L.-Y., Zhang, X.-S., & Zhang, J.-L. (2006). Capacitated Facility Location Problem with General Setup Cost. Computers & Operations Research, 33, 1226-1241. https://doi.org/10.1016/j.cor.2004.09.012
[36]	Zhou, Y. F., Liu, M., & Wang, L. (2010). Study of Urban Shelter Location Planning Based on Multi-Objective Approach. Journal of Safety Environment, 10, 205-209. (In Chinese)
[37]	Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8, 173-195. https://doi.org/10.1162/106365600568202