CONTACT US: Contact info
|
Citation |
Chen C, Li Q, Kaneko S, Chen J, Cui X. Fire Safety J. 2009; 44(1): 113-120. |
|
Copyright |
(Copyright © 2009, Elsevier Publishing) |
|
DOI |
|
PMID |
unavailable |
|
Abstract |
aKey Laboratory of Environmental Change and Natural Disaster, Ministry of Education of China, Beijing Normal University, Beijing 100875, China bInternational Development and Cooperation (IDEC), Hiroshima University, 1-5-1 Kagamiyama, Higashi-Hiroshima 739-8529, Japan Although emergency signs are believed to play an important role in ensuring public safety in facilities during emergencies, in practice, specific and clear standards for placing emergency signs have not yet been established. This paper developed a heuristic algorithm based on the Lagrangian relaxation algorithm for optimizing emergency sign locations with consideration of light-occlusion effects. A cellular automaton (CA) evacuation model was then introduced, and based on this model, the evacuation efficiency of the optimized locations of emergency signs derived from the algorithm was verified, and was compared with the evacuation efficiencies of the same supermarket without and with existing emergency signs. The results showed that the proposed algorithm greatly enlarged the coverage of emergency signs and improved the evacuation efficiency. It was concluded that the proposed algorithm with consideration of light-occlusion effects is valid for application to the problem of location optimization of emergency signs in single-floor facilities. Keywords: Public safety; Evacuation; Emergency signs; Maximal covering location problem; Lagrangian relaxation algorithm Even following these general guidelines, it is still hard to obtain a solution for locating emergency signs in such a way as to respond exactly to the actual layout of a public facility. Besides, although some studies have pointed out the important role of emergency signs in the evacuation process and way finding [7], [8], [9], [10], [11] and [12], few studies have attempted to explore the theory and methods for determining the best locations of emergency signs. As a result, the locations of emergency signs in public facilities are still limited to experts’ experience, which sometimes may not effectively help people to evacuate when an accident happens. It is highly desirable to solve the location optimization problem for emergency signs in public facilities, especially for developing countries, where budgets for emergency management are limited. The location optimization for emergency signs can be considered as being of the maximal covering location problem (MCLP) type, which was originally proposed by Church and ReVelle [13] and is a well-studied problem in the field of location–allocation modeling [14] and [15]. In MCLP, some discrete demand points in general are assumed covered by a facility if these points are within a predefined distance from at least one of the existing facilities. The objective of MCLP is to locate p facilities in the best places so that the maximal possible demand points can be covered. Similarly, the objective of location optimization for emergency signs is to maximize the light coverage of signs by locating emergency signs in the best places, where more coverage is assumed to allow more possibility for evacuees to be guided, to lead to more efficient evacuation. Therefore, it is reasonable to regard the location problem of emergency signs as a MCLP. However, it should be noted that emergency sign location optimization is more complicated than conventional MCLP because of the existence of obstacles, such as high shelves and hanging posters, which may influence the light coverage of emergency signs. Based on what is mentioned above, this paper presents a Lagrangian relaxation algorithm to find the best locations for emergency signs in public facilities with consideration of the light-occlusion effect. Further, to assess the validity of the locations of emergency signs calculated by the new algorithm, a computer-based evacuation simulation with a cellular automaton (CA) model was employed and applied to compare the evacuation efficiencies in the case of a supermarket under three scenarios of emergency sign locations: (1) no emergency signs, (2) the existing locations, and (3) optimized locations. The location optimization problem of emergency signs can be described as follows: in a given network G(V, A), V is the index set of all vertices, |V|=m the number of vertices in the network, and A the index set of all edges. Any vertex k (kV) is defined both as a potential location of an emergency sign, as well as a demand point that must be covered by an emergency sign. I is the index set of all demand points and J the index set of all potential locations of emergency sign. IV, JV, and IJ=V. The maximal covering location model for emergency signs may be formulated as follows: The objective function (1) maximizes the coverage of emergency signs, which means that more demand points may be covered. Constraint (2) states that demand at point i cannot be covered unless point j, which could cover point i, is selected as the point locating one of the emergency signs. Constraint (3) states that the number of emergency signs to be located should be no more than P. Finally, constraints (4) and (5) are the integrality constraints on the decision variables Xj and Zi. Assume that if a barrier higher than the average human height exists in the line linking an emergency sign and an evacuee, it could occlude light so that sign cannot guide the evacuee. Assume that the coordinates of the emergency sign A, evacuee P, and any barrier Bi between A and P are (xl, yl), (xp, yp), and (xbi, ybi), respectively; di is the vertical distance from barrier Bi to the linking line between the emergency sign A and evacuee P, and can be calculated as: As with the example shown in Fig. 1, assume that d=mini(di), i=1, 2, 3. If d is less than a specified threshold, it means that the barrier is almost on (or close to) the line linking the emergency sign and the evacuee, and can occlude the light from the emergency sign. To obtain the threshold, we selected a place in the supermarket as shown in Fig. 2. First, d for each grid around a sign and barriers were calculated according to Eqs. (6), (7), (8) and (9). Second, a survey was conducted in the actual location. A person stood in the center of each grid and judged whether he could see the emergency sign or not. The grids where he could see the sign were marked as green areas in Fig. 2. Then, the threshold can be set in this way according to the survey of the real scenario. Based on several similar experiments, the threshold was set at 0.9, which proved to be reasonable in our experiments. In general, emergency signs can be divided into two categories: exit signs, usually located near exits and set on a wall or door; and direction signs, showing the way to an exit and usually attached to the ceiling. Therefore, the light coverage areas of an exit and a direction sign can be considered as a sector and a circular region, respectively, as shown in Figs. 3a and b. The coverage of emergency signs without or with consideration of light-occlusion effects is shown in Figs. 4a and b. The light coverage in Fig. 4b is obviously lesser than that of Fig. 4a, suggesting that the light-occlusion effects should certainly be taken into account for locating emergency signs optimally. MCLP is an NP-complete problem [14]. There is no polynomial time algorithm for its optimal solution, and heuristic algorithms are generally used, such as the greedy adding algorithm, greedy adding and substitution algorithm, or the Lagrangian relaxation algorithm [15]. The Lagrangian relaxation algorithm provides an upper and a lower bound to the value of the objective function. The main steps of the Lagrangian relaxation algorithm involve: (1) relaxing one or more constraints through multiplying the constraint(s) by Lagrangian multiplier(s) and bringing the constraint(s) into the objective function; (2) obtaining upper and lower bounds to the original objective function; and (3) modifying the Lagrangian multiplier(s) to approach the optimal solution [16]. As this algorithm can simplify the problem and reduce the time cost, Lagrangian relaxation-based heuristics have been applied to many optimization and location problems [17], [18], [19] and [20]. In applying the Lagrangian relaxation algorithm to the problem of locating emergency signs, constraint (2) was selected to be relaxed because it links the location variables Xj and the coverage variables Zi, to complicate the analysis. After relaxing constraint (2) by using Lagrangian multipliers λi, the following problem P2 was obtained from P1: For the given values of the Lagrangian multipliers λi, the original problem P1 decomposes into problems about Zi and Xj, each of which may be readily solved. The solution of Zi is For the solution of Xj, Σiαijλi can be treated as the coefficient of Xj. The top P coefficient was selected and the corresponding Xj was set to be 1, and for the remaining sites, Xj was set to be 0. By far, the relaxed problem P2 was solved. For any given values of Lagrangian multipliers λi (λi>0), it was known that With this step size, the values of λi were updated using the following relationship: To find a better solution for the emergency sign location problem, the number of iterations was not restricted. The algorithm terminates only when one of the following conditions is satisfied: (1) UB–LB<1 or (2) the value of UB–LB remains the same in 10 consecutive iterations. Because of the advantages of interactive data language (IDL), it was used to implement the Lagrangian relaxation algorithm in the complicated matrix calculation, and the calculation results were directly applied in the simulation scenarios through a file-sharing mechanism. A simulation model to analyze evacuees’ behaviors in a public facility was developed based on the CA model [21]. CA is a discrete, decentralized, and spatially extended system consisting of large numbers of simple identical components with local connectivity. One of the advantages of CA-based simulation is that it is carried out according to several specified regulations instead of complex differential equations [22], [23], [24] and [25]. In addition, the CA-based evacuation model is grid based and is capable of tracing individual movement in the evacuation process. The main frame of the evacuation model is composed of three parts: namely, the enclosure; the evacuees; and the physical conditions during evacuation. The enclosure is defined as the place where the evacuation takes place, and the evacuees are defined as the people who take part in the evacuation. The physical conditions take into consideration several external factors that may influence the evacuation, such as the presence of emergency signs, illumination conditions, etc. In the CA-based simulation model, the enclosure was partitioned uniformly into grids. Each grid represents a cell. The size of cell corresponds to approximately 0.5 m×0.5 m, which is the typical space occupied by a pedestrian in a dense crowd [26]. Taking a supermarket as an example, the cells may be occupied by walls, high barriers, low barriers, evacuees, emergency signs, exits, or may be empty. Barriers (shelves) were divided into two categories based on whether they are occluding the light from the emergency signs. Smoke is not taken into consideration in our simulation because in emergency events except fire disaster, such as terrorist attack, sudden earthquake and so on, the impact of smoke is neglectable. Moreover, in the case of fire disasters, the occurrence and diffusion of smoke are random and unknown before the accident report of fire disaster comes out. Thus, smoke is not included in the description of enclosure. All the settings of the enclosure were saved as data files and used directly at later times. The description of evacuees includes their total number, location, and personal characteristics. The personal characteristics are important because that determines who will occupy the optimal objective grid when competition happens. The evacuees were divided into weak or strong group according to their different personal characteristics, determined by age, sex, and health condition in a complicated manner. The adults were usually grouped into the strong group, while the aged, the children, and people with disabilities were usually grouped into the weak one. The location of evacuees was recorded in the form of coordinates. The description of evacuees may be either set randomly or pre-assigned according to reality. The movement of each evacuee was simulated simultaneously in the model. Each evacuee was supposed to move only one cell in a time step. As the walking speed of an evacuee is 1 m/s under normal conditions [27], the time step was set to 0.5 s, considering the size of the grid. The possible movement of each evacuee was defined in eight directions, as in the Moore neighborhood shown in Fig. 5. The presence of the emergency signs was taken into consideration in the simulation model. As mentioned before, there are mainly two types of emergency signs. The coverage areas of the exit sign and the direction sign may be considered, respectively, as a sector and a circular region. The type, location, and coverage area of emergency signs can be set according to the real enclosure conditions. Without any guidance, the evacuees generally take three possible modes for evacuating the enclosure, according to their prompt judgment and experiences. Those familiar with the enclosure will take mode I, because they can choose the shortest route for evacuation. Those who are not so familiar with the enclosure will take mode II; i.e., they just follow the same route by which they entered to evacuate. For those who do not know how to react in an emergency, they have to take mode III; i.e., they do nothing but follow the others. The guidance by emergency signs is thought to be necessary for helping those taking mode II and mode III to evacuate. Because the route they know is not the shortest and the emergency signs will lead them to the shortest route, evacuation efficiency may significantly improve a lot overall. An evacuee's movement under emergency is very complicated, and is decided not only by familiarity with the enclosure, but is also affected by the movements of other evacuees. The basic movement rule in the evacuation model is that each evacuee will select the grid with the highest attraction probability in the Moore neighborhood of its current grid as the objective grid of the next time step. The attraction probability was determined by the status of both the current grid and all the grids in the Moore neighborhood. Moreover, using the CA model, an evacuee can move only one grid in each time step, and competition inevitably happens when more than one evacuee choose the same objective grid. In this case, the evacuee with the highest competitive capability will exclusively take the grid with highest attraction probability as his objective grid, whereas the others have to compete for the suboptimal grid continuously. The suboptimal grid was defined as the grid with the second-highest attraction probability. If some evacuees have the same competitive capabilities for the same objective grid, one of them will be selected randomly to take the common objective grid, and the others must compete for the suboptimal grid continuously. If no cell is available around the evacuee, he will remain in the same place, which reflects the fact that the movement of evacuees will become difficult in a crowded area during an emergency, as competition becomes increasingly serious when the space becomes more crowded. In this method, the movement speed variation caused by the variation of evacuees’ density was taken into consideration in our evacuation system. The calculations of attraction probability and competitive capability are described below. The attraction probability P(i, j) of grid N(i, j) is defined as follows: Pdis(i, j) was calculated by the path distance from grid N(i, j) to any exit, and defined as Because three evacuation modes were taken into account, the conformity behavior was defined in the model that an evacuee will choose to move as the same direction chosen by most of the evacuees in his Moore neighborhood. Pdir(i, j) in a certain Moore neighborhood was defined as follows: As mentioned above, competition inevitably happens when more than one evacuee chooses the same grid as their objective. The competitive capability of evacuees is determined by the complicated personal characteristics and the relative position of evacuees in a Moore neighborhood. The definition of competitive capability C is Taking the supermarket shown in Fig. 7 as a case, the location optimization for emergency signs was analyzed, and its effect on guiding evacuation was evaluated using the CA-based evacuation model described in Section 3. The evacuation was simulated and the results were compared under three guidance scenarios: without emergency signs; with real existing emergency signs; and with optimized emergency signs. Fig. 7 presents the layout of a supermarket case with length 73 m and width 49 m. There are two exits in the supermarket; the main one is located on the northwest side with a width of 9 m near some points of sells (POS), while the other, designed for emergency, is located on the west side with a width of 4 m. The shelves used for different commodities were characterized by different colors and were finally attributed to two types in the simulation based on their light-occlusion effects. In Fig. 8, the higher shelves, shown in light yellow, were thought to occlude the light of emergency signs, and the lower shelves, shown in dark yellow, have no light-occlusion effect. The total number of evacuees in the supermarket was assumed to be 1800, according to the related design code [28]. In the first scenario simulating the supermarket without emergency signs, it was assumed that all evacuees randomly take any one of the three above-mentioned evacuation modes. The original position and the personal characteristics of the evacuees were also assumed randomly before the simulation. The simulation result shown in Fig. 9 is based on 10 simulations for the same scenario. It showed the number of evacuees remaining in the supermarket at every minute of the evacuation process. The second scenario reflected the real situation of emergency signs in the supermarket. As shown in Fig. 8, the total number of emergency signs was 16, including two exit signs. The exit signs were located at each exit door and several direction signs attached to the ceiling were distributed along corridors with an effective radius of 10 m. The result of this simulation is also shown in Fig. 9. The third scenario simulated the supermarket with optimized emergency signs. Being the same as the second scenario, the total number of emergency signs was also 16. Allowing for light-occlusion effects, the optimized location for each emergency sign was obtained by applying the Lagrangian relaxation algorithm described above and is shown as squares in Fig. 8. The result of this simulation is also shown in Fig. 9. Besides, the standard deviation of each minute, from the first minute to the 11h minute, in the 10 simulations for three scenarios is listed in Table 1. Comparing the simulation results shown in Fig. 9, it was obvious that the number of evacuees remaining in the supermarket in the third scenario in every minute is much smaller than that either in the first or the second scenario, especially in the final minutes. Moreover, the total evacuation time was found to reduce from 11 min in the first scenario to 9 min in the second scenario, and to less than 8 min in the third scenario. The results proved that the optimized location of emergency signs might cover maximal areas of the supermarket, to effectively guide the evacuees taking evacuation modes II and III to choose the shortest route for evacuation. Consequently, the total evacuation time was reduced and evacuation efficiency was improved. Besides, the standard deviations shown in Table 1 are relatively small comparing to the number of evacuees in the supermarket, which means the result of our simulation is constant to some extent for each scenario and thus reasonable. For further explanation, these variations are generally caused by the randomness induced in the movement rules of evacuees. Therefore, it is reasonable to believe that the emergency signs could help to dispel evacuees’ panic and have an effect on evacuation in emergencies. Although emergency signs play an important role in ensuring safety in public facilities, there are no specific and clear standards for emergency sign location, which may inhibit the expected function of emergency signs to some extent. Because the problem of locating emergency signs is quite similar to the MCLP, this paper proposed a heuristic algorithm based on the Lagrangian relaxation algorithm allowing for light-occlusion effects, which can be applied to emergency signage location in public facilities. Furthermore, taking the case of a supermarket, this paper simulated scenarios without emergency signs and with the existing emergency signs as references, and compared the results for the scenario with optimized emergency signs by using a CA-based evacuation model to evaluate evacuation efficiencies. The results showed that emergency signs indeed performed their function in improving evacuation efficiency, and that the coverage of emergency signs could be greatly expanded with location optimization. It needs to be mentioned that our study is based on the assumption that the installation of emergency lighting will make a difference to the total evacuation time, which is a common accepted assumption. And its validity can be proved from two aspects. First, the same assumption is also generally used in many other relative researches about emergency lighting, such as its visibility, designation, and so on [29] and [30]. Second, the importance of the installation of emergency lighting is emphasized in the national design codes around the world, which can be an indirect proof of our assumption. For instance, in design code for fire protection of high-rise civil architectures in China, it is stated that exit signs are needed at the exits of a large public building [5]. And in Life Safety Code in USA, it is also dictated that emergency lighting facilities shall be arranged to provide initial illumination that is at least an average of 1 fc and a minimum at any point of 0.1 fc measured along the path of egress at floor level [31]. In conclusion, from the results in the study, it is expected that the new algorithm could be applied to fire alarm or monitor camera location problems. And for further study, when focusing in particular on fire disasters, the impact of smoke needs to be carefully considered, including its occurrence, dispersion, obstruction to the evacuees’ view, and so on. This study was supported by National Science and Technique Supporting Program (2006BAJ10B03), Ministry of Science and Technique, China. |