Keywords

1 Motivation

Disaster management has become an important topic due to the growing frequency and intensity of natural and man-made disasters. The reasons for this negative trend are various: Environmental problems such as global warming cause bush fires or floods. Poor planning of buildings or cities increases the consequences of hurricanes or earthquakes. Moreover, humans themselves are intentionally (e.g., terrorist attacks) or unintentionally (e.g., chemical disasters) responsible for a multitude of disasters. The Federal Emergency Management Agency of the United States reports annually 45–75 disasters in recent years that require state and federal assistance and may lead to an evacuation [2]. Furthermore, the United Nation Office for Disaster Risk Reduction reported for the years 1995–2015 that over 606,000 people were killed and over four billion people were affected by natural disasters worldwide [6].

This work focuses on the mass evacuation of urban areas. The two major issues faced during such an evacuation scenario are the following: First, evacuees lack both information and experience regarding such an extreme situation. Second, people might act in a selfish way and choose a route which is the best for themselves. Thus, they might choose an evacuation route which might be the best route during normal traffic, but not during an extraordinary evacuation situation. The main task of evacuation planning is the guidance of the evacuees through the street network to reduce casualty risks and increase the performance of the evacuation process. The guidance includes instructions to evacuees when to leave their homes and start their evacuation process, which evacuation routes to take and which shelter to head to. Careful and rigorous evacuation planning is an important task to ensure an effective implementation of the evacuation process and to save the life and health of the exposed population.

One major issue of this research field is the estimation of realistic scenarios as the relevant input data is highly stochastic. We focus in this work on the consideration of uncertainties regarding the supply conditions of the street network during an evacuation process. These supply variations might be caused by the catastrophe itself (e.g., (partial) flooding of streets, limited visibility or debris on the road) or by factors that also affect daily traffic such as a wide variety of traffic accidents or technical failures. The current evacuation literature usually assumes the identical street capacities for an evacuation scenario as for daily traffic situations which is in fact a quite unrealistic assumption. One consequence of these reduced capacities is a lower traffic volume that can be transferred by the streets. This is even worse for urban evacuation scenarios as the main evacuation routes are mostly utilized up to their capacity limit. Mattson and Jenelius [4] state that traffic systems become less robust (=  more vulnerable) if the capacity utilization is increased. Therefore, it is important to anticipate these supply condition uncertainties in the urban evacuation planning process.

2 Balanced Street Network Utilization for Increasing Robustness

The contribution of this work lies in designing a deterministic optimization model that is more robust against supply uncertainties in the street network without the explicit definition of these uncertainties. On the modelling level no explicit index exists that affects or improves the robustness of a traffic assignment. Therefore, we try to adopt an idea that has already been successfully applied among others to robust network design: The robustness of street networks is enhanced by a better utilization of the available network capacities and by reducing interdependencies in the network [5]. The general idea is to utilize the available street capacities in a more balanced way to reduce the consequences of disruptions in the street network during the evacuation process. Therefore, we extend the initial evacuation model basing on the Cell-Transmission model [1] by considering the utilization of the street network during the evacuation process. The resulting model has two new properties compared to the initial evacuation model: First of all, it bases on predefined evacuation paths. The consideration of these evacuation paths is necessary to prevent unreasonable routes induced by utilizing the network capacities in a more balanced way. Unreasonable routes include e.g., circles or utilize streets in both directions, which is normally not meaningful in an evacuation scenario. Therefore, we also present a special path generation algorithm to generate a reasonable number of paths meeting our individual defined requirements. Secondly, the new model includes two objective functions to handle the evacuation performance as well as the robust aspect. For handling these two objectives we apply the lexicographic 𝜖-Constraint Method. The main following research objective is to answer the question if the robustness of the evacuation guidance can be increased if the street network capacities are utilized in a more balanced way. Evacuation performance (e.g., the total evacuation time) is not our only objective and we are willing to sacrifice some of it to enhance the robustness in the face of unpredictable capacity disruptions.

3 Approximated Pareto Sets

The lexicographic 𝜖-Constraint Method gives us no information about the trade-off concerning the evacuation performance and the robust aspect. Therefore, we present two approaches approximating the optimal Pareto set. The advantage of approximated Pareto sets is that not the complete optimal Pareto set has to be determined which is usually computational burdensome. The first approach is the box algorithm which is based on the work of [3]. In this approach a coordinate system is considered where each axes represent one objective function. One solution of the extended evacuation model is specified by the two objective function values so that each solution is represented by one definite point in the coordinate system. We determine for each adjacent solution point pair a rectangle that represents the solution space of all non-dominated solutions between these points. These rectangles are iteratively divided into smaller rectangles by this approach. The objective of this approach is to reduce the total area of all rectangles. The smaller the total area of all rectangles, the better the approximation of the optimal Pareto set. This approach is based on optimal solutions so that it may suffer from long computational times. Thus, we additionally present the staircase algorithm. The general idea of this second approach is identical to the box algorithm: We consider the entire solution space and reduce this space by generating more solutions iteratively. In contrast to the box algorithm we consider lower and upper bounds instead of optimal Pareto solutions. Thus, the solution quality of one iteration of the staircase algorithm is usually lower than in one iteration of the box algorithm, but the computational times of one iteration can be reduced enormously. Both bounds are determined by individual problem-specific heuristics. Figure 1 shows two typical results for each algorithm to visualize the general differences of the approaches. The points p 1–p 5 represent each one optimal solution and the points lb 1–lb 5, respectively, ub 1–ub 5 represent each one solution of the individual bounds. Thus, the grey marked area visualizes the solution space of the approximated Pareto set. The small the area, the better is the approximated Pareto set.

Fig. 1
figure 1

Typical solutions of the box-algorithm (left side) and the staircase algorithm (right side)

Full size image

4 Computational Results

We conduct an extensive computational study that is subdivided into three single studies. First, we investigate the effects of various parameter settings regarding the evacuation performance and the robust aspect. Based on these results, we arrange a test bed for the upcoming two studies. In the second study we compare the performance of both approaches approximating Pareto sets. Thirdly, we test the benefits of the robust evacuation concept with the help of our individual test procedure.

By evaluating the various parameter settings we detect that the population size, the distribution of the evacuees within the networks and the tolerance factor, which determines the predefined set of evacuation paths, mainly affect the evacuation performance and the robust aspect. Thus, we design a test bed consisting of 252 instances mainly varying in these parameters. The main results of the computational studies are the following: By comparing both solution approaches the staircase algorithm archives in 80.5̄% of all considered instances a better solution quality than the box algorithm. In the average the staircase algorithm represents the solution space 31.8% better than the box algorithm. This result confirms the general idea of the staircase algorithm as meaningful. By evaluating the benefits of the robust concept, we observe that a more balanced capacity utilization does not naturally lead to a more robust solution. However, we detect that the lexicographic solution, considering the optimal evacuation performance and the corresponding best balanced network utilization, performs always better or at least as well as if only the evacuation performance is considered. This result confirms our concept as beneficial and we recommend to apply at least this lexicographic solution, because no additional hazard has to be accepted. However, the absolute benefits of these solutions are marginally, but they can be increased if an additional hazard is accepted. Unfortunately, we cannot give a general advise for the exact level of additional hazard. The reason is that a more balanced capacity utilization naturally leads to a higher accepted hazard level compared to the optimum which is harder to catch up in the average. Actually, there is a (small) range in the additional accepted hazard level in which the robust concept performs better than the safe concept. Unfortunately, this range depends on the unknown scenario and the unknown capacity disruption(-s) (levels). Nevertheless, the computational study shows that several parameter settings affect the performance of the robust concept positively. Thus, the benefits of the robust concept naturally increase if higher capacity disruption levels or multiple capacity disruptions occur at once. We also detect that the more unbalanced the vehicles are initially distributed within the networks, the more beneficial is the robust concept. This is due to the fact that the potential to utilize the network capacities in a more balanced way is the greatest for these scenarios. Interestingly, the results of the staircase algorithm are also the best for these instances. Nevertheless, we cannot clearly predict the benefits of the robust concept for a given evacuation scenario, but we can at least partially estimate whether the robust concept is worthwhile or not.

5 Conclusion and Future Research

We focus on short-term uncertainties in the street network capacities and implement the robust aspect in a unique way: We consider a deterministic cell-based evacuation model that sacrifices a certain amount of the optimal evacuation performance to utilize the street capacities in a more balanced way. Thus, we reduce the consequences of disruptions and design the evacuation plan more robust. The results are evaluated in a computational study and show that the resulting evacuation plans are (in the average) less sensitive to disruptions than the evacuation plans only focusing on the performance.

Future research can be conducted in many fields: First of all, we investigate various characteristics regarding 16 networks that differ, e.g., in the network size or network structure. However, we cannot determine any significant variations in the computational study results among these networks, although we suppose that some network characteristics affect the evacuation planning concept. Thus, the investigation of these network characteristics is an interesting starting point for future research projects. Additionally, no universal test bed exists for cell-based evacuation planning approaches. Thus, the arrangement of a comprehensive test bed that comprises a multitude of the mentioned characteristics will help to compare various cell-based evacuation approaches in the future. Here, the results of our test bed generation might help.

Second, our results of problem-specific lower and upper bounds are inconstant. In the average the gap between the lower and upper bound is about 6.7% in our computational study, but we detect variations in the results regarding various parameter settings. Thus, this result is also a starting point to improve or extend the computation of the bounds. Perhaps, also the investigation of other solution approaches is purposeful.