One of the problems in post-earthquake disaster management in developing countries, such as Iran, is the prediction of the residual network available for disaster relief operations. Therefore, it is important to use methods that are executable in such countries given the limited amount of accurate data. The purpose of this paper is to present a multi-objective model that seeks to determine the set of roads of a transportation network that should preserve its role in carrying out disaster relief operations (i.e. known as “emergency road network” (ERN)) in the aftermath of earthquakes.
In this paper, the total travel time of emergency trips, the total length of network and the provision of coverage to the emergency demand/supply points have been incorporated as three important metrics of ERN into a multi-objective mixed integer linear programming model. The proposed model has been solved by adopting the e-constraint method.
The results of applying the model to Tehran’s highway network indicated that the least possible length for the emergency transportation network is about half the total length of its major roads (freeways and major arterials).
Gathering detailed data about origin-destination pair of emergency trips and network characteristics have a direct effect on designing a suitable emergency network in pre-disaster phase.
To become solvable in a reasonable time, especially in large-scale cases, the problem has been modeled based on a decomposing technique. The model has been solved successfully for the emergency roads of Tehran within about 10 min of CPU time.
Nomenclature
- Sets
- A:
set of all links
- Ak:
set of links that provide access to node k
- R:
set of paths
- Ra:
set of paths that include link a
- Rij:
set of paths that connect i to j
- Rid:
set of all paths that can connectdemand point i to service provider d
- I:
set of demand points (origin points) that need to get the service i (at thedestination point)
- J:
set of destination points providing aservice (service provider) j (used forthe goal of providing access)
- D:
set of destination (supply) points for a service d (used for the goal of travel time calculating)
- Kf:
set of coverage points of type f
- Parameters
- Tr:
travel time of path r
- Wid:
the relative weight of emergency route emanating from demand point i of type d in objective function
- la:
length of link a
- L:
maximum length allowable for thenetwork
- Nf:
number of members of set Kf
- ∝f:
proportion of all coverage points oftype f that should be covered
- M:
a large enough positive number
1. Introduction
Natural disasters cause significant fatality and financial losses. Since 1980, these disasters have claimed over 2m lives and caused losses worth $3 trillion (Wirtz et al., 2014). It is worth mentioning that in 2014, about 100m people who were affected by natural disasters were in Asia. Iran is among the five most vulnerable countries susceptible to natural disasters, experiencing major earthquakes in its history such as Bam, Manjil–Rudbar and Tabas (Ibrion et al., 2015). For example, in Bam earthquake, more than 26,000 people, mostly children, lost their lives and more than 30,000 people were injured during this earthquake (Mehrabian and Haldar, 2005). Therefore, in Iran, rescue and relief operations are highly important. Most natural disasters may seem to be out of human control, but the losses and damage caused by them can be controlled significantly. This is directly related to preventive actions taken by people and related organizations. Therefore, the important issues in recent years in all countries, including Iran, have dealt with the issue of disaster management. Disaster management predicts and plans a set of processes before, during and after the occurrence of any disaster to prevent the financial and human casualties of the disaster or to reduce them. Generally, a disaster management system consists of a cycle with four phases: mitigation, preparedness, response and recovery (Kutz, 2004). The main concern in developed countries is to return the city to the pre-disaster conditions quickly but developing countries attempt to rescue more people in the response phase (Khademi et al., 2015). Hence, the transportation network plays a decisive role in the success of disaster relief operations (DRO) carried out in all four phases, especially in developing countries. Identifying the critical transportation infrastructure is important because it will lead to decisions about future investment (Peeta et al., 2010), public resource management and funding prioritization (Psaltoglou and Calle, 2018). Transportation network planning is one of the most important parts of disaster management. The absence of specific (and predetermined) paths as relief routes makes it impossible to respond to damaged areas effectively. Identification of the relief routes (emergency road network (ERN)) has two major advantages (Shariat Mohaymany and Pirnazar, 2007): relief routes can be available only for those trips made between disaster relief centers and damaged areas (demand points), and less important trips can be directed to other routes; and relief routes can be retrofitted before disasters. It should be noted that due to budget constraints it is impossible to retrofit all routes, and therefore identification of ERN as a preventive strategy in the pre-disaster phase will be useful to decide how the limited budget should be assign to retrofit the vulnerable elements of these routes (such as bridges). Most of the strategies based on the timing of decisions relative to prevent DRO disruption can be broadly classified into proactive and reactive strategies. Most of the proactive strategies proposed so far revolve around the supplier selection and preventive disruption frameworks (Elluru et al., 2017). Hence, the proposed work is linked with proactive DRO strategies, and considers the connectivity associated with each point prior to the disaster occurrence as a preventive measure. In this paper, a multi-objective integer programming (IP) problem for emergency road network design problem (ERNDP) is presented. The ERNDP is related to the pre-disaster (mitigation) phase, as classified by Cavdur et al. (2016). The ERNDP, as a special type of the network design problem (NDP), seeks to determine the optimal set of links of a transportation network that should preserve its role in carrying out the DRO within 72 h in the aftermath of an earthquake. The objectives of the model are to minimize the total travel time of emergency trips, the total length of network, and to maximize the number of the relief demand/supply points covered. To solve the proposed three-objective model the ε-constraint method is applied to obtain the solution set. The problem is modeled based on a set covering approach, where a number of feasible (potential) routes that can provide connection between each origin-destination (OD) pair are identified, and then the model is designated to choose between different combinations of the potential routes so that the objective function (i.e. total travel time) is minimized while the constraints are satisfied. The proposed method has been applied to the Tehran’s network with data provided by Tehran Disaster Mitigation and Management Organization.
The rest of the paper is organized as follows. A literature review is presented in Section 2. The proposed model and the solution method are explained in Section 3. In Sections 4 and 5, results of the application of the proposed method on Sioux Falls network and Tehran road network are presented. The conclusion is presented in Section 6.
2. Literature review
As shown in Table I, the related research in the area of the application of operations research in disaster management fall into four categories: facility location, inventory management, distribution and link reinforcement problems. Facility location models (Tzeng et al., 2007; Balcik and Beamon, 2008; Jeong et al., 2014; Xu et al., 2016; Tayal and Singh, 2017) emphasize the prepositioning of emergency stock in the pre-disaster phase. Inventory management models (Ozbay and Ozguven, 2007; Kaur and Singh, 2016) emphasize on determining the item quantities required along the relief chain, procurement quantities and order frequency; they also identify the appropriate amount of safety stock to maintain (Bozorgi-Amiri et al., 2013). Distribution problems (Özdamar et al., 2004; Bozorgi-Amiri et al., 2013; Hasanzadeh and Bashiri, 2016; Kaur and Singh, 2016; Elluru et al., 2017; Mohamadi and Yaghoubi, 2017; Üster and Dalal, 2017; Rahmani et al., 2018; Sabouhi et al., 2018; Safaei et al., 2018; Torabi et al., 2018) include victim evacuation and relief distribution problems (Bozorgi-Amiri et al., 2013). The problem deals with distributing commodities and victims to distribution centers (DC). The pre-disaster reinforcement models (Asakura et al., 2003; Chootinan et al., 2005; Sanchez-Silva et al., 2005; Peeta et al., 2010; Edrissi et al., 2013, 2015; Du and Peeta, 2014; Faturechi and Miller‐Hooks, 2014) dealing with prioritization of facilities that have to be reinforced for mitigating earthquake damages. The emergency NDP (Viswanath and Peeta, 2003; Shariat Mohaymany and Pirnazar, 2007; Nikoo et al., 2018) seeks to determine the optimal design of a transportation network to preserve its role in carrying out logistic operations in the aftermath of disasters. The ERNDP is related to the emergency NDP. A detailed literature review on these problems can be found in Nikoo et al. (2018), and here we review briefly some more related works. Also, some works such as Afshar and Haghani (2012) and Xu et al. (2016) integrate one or more of the above-mentioned problems. The output of the ERNDP can be the input of the emergency distribution problems. For example, in Sabouhi et al. (2018) an integrated evacuation and distribution logistic system is proposed to obtain simultaneous routing and scheduling of vehicles to evacuate people from affected areas to shelters and provide them with necessary relief commodities.
Application of operations research in disaster management
| Application | Technique | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Authors (Year) | Location | Facility location | Inventory management | Emergency distribution | Pre-disaster reinforcement | Emergency network design | Multi-objective | Stochastic | Robust | Maximal covering | Bi-level | Mixed integer Linear programing | Non-linear | Exact solution method | Meta-heuristics solution method | Heuristics solution method |
| Tzeng et al. (2007) | Taiwan | * | * | |||||||||||||
| Balcik and Beamon (2008) | Generated examples (world) | * | * | |||||||||||||
| Jeong et al. (2014) | South Carolina, USA | * | * | |||||||||||||
| Xu et al. (2016) | Lushan, China | * | * | * | ||||||||||||
| Tayal and Singh (2017) | Generated examples | * | * | * | * | |||||||||||
| Ozbay and Ozguven (2007) | Generated examples | * | * | |||||||||||||
| Kaur and Singh (2016) | Generated examples | * | * | * | ||||||||||||
| Özdamar et al. (2004) | Small test instances | * | * | * | ||||||||||||
| Bozorgi-Amiri et al. (2013) | Iran | * | * | * | * | |||||||||||
| Kaur and Singh (2016) | Generated examples | * | * | * | ||||||||||||
| Mohamadi and Yaghoubi (2017) | Iran | * | * | * | ||||||||||||
| Üster and Dalal (2017) | USA, coastal Texas | * | * | * | ||||||||||||
| Rahmani et al. (2018) | Tehran, Iran | * | * | * | * | |||||||||||
| Torabi et al. (2018) | Iran | * | * | * | ||||||||||||
| Hasanzadeh and Bashiri (2016) | Numerical examples | * | * | * | * | |||||||||||
| Elluru et al. (2017) | Numerical examples | * | * | |||||||||||||
| Sabouhi et al. (2018) | Tehran, Iran | * | * | * | ||||||||||||
| Safaei et al. (2018) | Numerical example (a case of flood disaster) | * | * | * | * | |||||||||||
| Asakura et al. (2003) | Numerical examples | * | * | |||||||||||||
| Chootinan et al. (2005) | Example network | * | * | * | * | * | ||||||||||
| Sanchez-Silva et al. (2005) | Colombia | * | * | |||||||||||||
| Peeta et al. (2010) | Istanbul | * | * | |||||||||||||
| Edrissi et al. (2013) | Example network | * | * | |||||||||||||
| Du and Peeta (2014) | Example network (Sioux Falls) | * | * | * | * | |||||||||||
| Faturechi and Miller-Hooks (2014) | Example network (Double-stack container network) | * | * | * | * | |||||||||||
| Edrissi et al. (2015) | Tehran, Iran | * | * | |||||||||||||
| Viswanath and Peeta (2003) | Southwestern Indiana, USA | * | * | * | * | |||||||||||
| Shariat Mohaymany and Pirnazar (2007) | Example network | * | * | * | * | |||||||||||
| Nikoo et al. (2018) | Tehran, Iran | * | * | * | ||||||||||||
To some extent, the ERNDP can be accounted as a pre-disaster reinforcement problem. This problem identifies a subset of links and critical routes of the network by considering some resource limitations along with the network performance after the disaster. Also, the pre-disaster link reinforcement can be defined as the problem of prioritizing facilities to reduce the fatalities and damage caused by disasters (Nagae et al., 2012).
Several works have focused on the problem of identifying a set of links to be reinforced with minimum costs to improve the network performance after the disaster. Asakura et al. (2003) proposed a model framework for optimal link investment problem in order to achieve a reliable network under uncertain conditions. Ukkusuri and Yushimito (2009) assessed the importance of road transport networks using heuristic process with the use of travel time performance indicators. In their study, the Frank–Wolfe assignment method was used. Peeta et al. (2010) modeled the failure of links uncertainty by accounting for the probability of failure as a priority to identify links requiring a retrofit program. They proposed a bi-level model using performance indicators (access and travel time), and an approximate solution method for solving model is presented. Edrissi et al. (2013) minimized the number of injuries after a large earthquake. Reconstruction of damaged buildings, strengthening the existing infrastructure of transport and location/allocation of aid levels were planned for the three major sectors. Du and Peeta (2014) proposed stochastic bi-level optimization model with specific characteristics of the two types of uncertainty associated with any kind of crisis, and rescue network was integrated in order to determine the links to be retrofitted. Because of the complexity of their model, the heuristic two-step algorithm was used to solve the model. The problem was decomposed to the linear programming model and shortest path problem. Chu and Chen (2015) presented a notion that the travel cost of alternative paths and (normal or post-disaster) travel demand can be simultaneously considered in an optimization model. Their methodology was demonstrated with a highway bridge system that is subject to earthquakes. Also, Faturechi and Miller‐Hooks (2014) and Edrissi et al. (2015) provided a variety of models for prioritizing and strengthening the components of transport networks and interested readers can refer to them for more detailed information.
A number of studies that have focused on the design of emergency transportation networks are relatively limited. Viswanath and Peeta (2003) proposed a multi-commodity NDP to plan emergency routes with the following objectives: to minimize the travel time between different demand and supply points, and to maximize the population covered by the routes. Shariat Mohaymany and Pirnazar (2007) proposed another maximal covering NDP for the identification of critical routes that can be used for relief operations after earthquakes. They utilized a goal programming approach to resolve the conflict between the problem objectives which were to minimize the total travel time on selected routes and to maximize the total population covered. Nikoo et al. (2018) developed a three-objective mathematical programming model with the following objective functions: to minimize the emergency network length, to minimize the total travel time to be experienced for making all emergency trips and to minimize the total number of paths requiring a specific link to be passed. They proposed a combined approach to reduce the problem to a single objective problem by using the weighted sum and the lexicographic methods.
In current study, we take into account the access of critical points regardless of the network vulnerability as opposed to that done by Nikoo et al. (2018). This approach is more suitable in case of very critical access points. Also, this paper does not consider any preference between total travel time and total length objective functions, in contrast to Nikoo et al. (2018). Moreover, here the coverage of important access points is considered as an objective function when determining the emergency routes. To do so, the ε-constraint method is applied to obtain different feasible solutions. Also, in the suggested method, we distinguish between destination points providing a service (service providers), and the general destination points.
In more recently evolved methods in the literature, OD data, total number of trips, survived network, travel times and route choice behaviors that are considered as inputs are highly uncertain and, in particular, any modeling technique may be reasonably inaccurate. Although advanced modeling approaches exist for developed countries, little reliable data on the natural disasters risks have been developed for developing and transition countries (Jafari, 2016). The ERN preserve major emergency trips by connecting major relief points (OD). The demand for all types of trips (emergency and evacuation) after a strong earthquake may not be derived correctly. These main points for emergency trips are fixed and the number of paths can be predicted (Nikoo et al., 2018). The recent methods discussed above, need accurate data that may be available only in developed countries. The availability of accurate information about disaster scenarios when natural disasters strike is very limited, especially in developing countries. Therefore, it is important to use methods that are executable in such countries given the limited amount of accurate data that are suitable for analyzing practical emergency NDP under uncertain conditions and expediting the scheduling of DRO and controlling the network.
The problem is a variant of the NDP, which is proved to be NP-hard (Magnanti and Wong, 1984). Considering the complicity of the suggested model in the form of a routing problem or a network flow problem with a traditional formula, solving it using the existing algorithms, especially in large-scale real networks, would be impossible. For this reason, a decomposing technique is presented in this paper which can be used for designing the emergency routes for real applications.
3. Multi-objective emergency road network design problem
The ERNDP aims at determining some links of the roads network to be able to conduct relief/rescue operations in the city. This study addresses ERNDP before the earthquake occurrence, in which supply and demand features of the earthquake are unknown because a detailed information about the number of active emergency vehicles and people after the earthquake, rescue request and the capacity of hospitals is not available. In fact, accessing this information is even difficult after the earthquake and predicting it before the earthquake would be more difficult; hence, according to the type of available information, the following four objectives underpin the design of emergency routes network:
establishing an accessing route between the producing points of emergency rescue demands and service providing points (here called primary nodes);
minimizing the cost (trip time of the ERN);
minimizing the network length; and
maximizing the coverage of other important points (here called secondary nodes), such as schools.
Important trips after a severe earthquake include fire brigade responses, logistic trips, entrance and settlement of the teams from supporter provinces, debris removal trips, organizational and administrative traffic, security initiatives other urban trips, damage assessment after an earthquake and trips related to the reconstruction process (Khademi et al., 2015). All of these trips provide a connection between important nodes engaging emergency relief operations, which we call them “primary nodes.” The main task of the proposed model in this paper is to provide access between the origin and destination points of these primary nodes. The entire existing points and accessing routes between them are identified in the network and its structure is regulated in a way to provide access (with coverage links). As shown in Figure 1(a), using the geographical information system, nodes and links are created with linkage of data. Suppose that the highlighted links in Figure 1(b) are two emergency paths that connect points. In this model, we consider path variable xr for each emergency path r. x1 show path from Node 1 to Node 2 and x2 show path from Node 3 to Node 4. x1 include link variables 1, 5, 12, 19, 20 and 13, so, y1, y5, y12, y19, y20=1. In fact, there is a node at the beginning and end of each link. Also, the important points in this network such as humanitarian aid distribution centers (HADC), hospitals and others are not directly connected to the network and are connected through a set of connector links to the network. The connector links are the arcs drawn to connect the important points to the network. These links have the trip time of 0 and their length has no effect on the results of the proposed model. Zk variable indicates the access to kth secondary node. In Figure 1(b), Z1 and Z2 equal 1, because secondary Nodes 1 and 2 have been covered in the designed emergency network.
Different routes are recognized for each OD points (OD pairs), in which the proposed model is allowed to select a different combination of them and it is looking for routes that:
Objective 1: provide the total minimum travel time.
Objective 2: provide the minimum emergency routes length.
Objective 3: provide the maximum coverage for the secondary points.
The structure of the proposed model has been based on the ε-constraint approach, in a way that the total travel time constitutes the model’s objective function, and the provision of access between the primary points is an essential constraint of the model. Also, a constraint has been defined for the maximum length and minimum overlapping in the response to determine the optimized response using multi-objective decision making after sensitivity analysis and final results achievement. The notation of the model is provided in the nomenclature.
3.1 Mathematical model
As discussed earlier, the objective functions of the model are: to minimize the total trip time (f1), to minimize the total length of the network (f2) and to maximize the coverage of secondary points locating in the vicinity of the emergency routes (f3). A weight (or importance) has been considered for each route connecting origin point i of service type d (denoted by Wid) and it has been multiplied by the product of shortest path time (denoted by tid). Summation over the products (in selected routes) constitutes the first objective function of the model which has to be minimized. The formulation is based on the selection of a number of feasible routes that provide connection between primary nodes (primary OD pairs). The selected routes, which are the connection provider of the model, are selected according to the value of the objective function in a way that the important routes should have less time. Also, it should be noted that as the objective function has been formulated using route variables the travel time of just one connecting path between each OD can be selected as the shortest path in the computation of total (network) travel time; this guarantees that the double counting of the demand is prevented.
Constraints (4) is the controller of only selecting a route to supply the access from a demand point i to service provider point j. As stated before, there are different routes between each origin and destination pair, in which the model is allowed to choose one of them. The set of Constraints (5) and (6) relates route variables to the selected arc decision variables, namely, if route r is selected, the related variable of ya would be selected as well through the set of Ra, which indicates the set of routes encompassing arc a as a part of them.
In this model, each demand point i is connected to several service provider (supply) points j. For example, the connection of a DC point to the three near hospitals have one origin point i and three destinations j. Constraints (7)–(9) transfer the least access time of i to j to the variable tid. This transfer from Tr (trip time on path r) is done using the auxiliary decision variable Prid. Decision variable xr leads to determination of Prid (Constraint (9)), and the value of tid is obtained through the Constraint (7). Constraints (10)–(11) enforce the coverage bounds, so that the coverage of point k (identified by means of decision variable Zk) is determined by selecting the ya arcs using these constraints. Constraint (12) guarantees the binary state of the decision variables.
The focus of the proposed model is placed on ensuring appropriate connectivity for the first responders in the immediate aftermath of an earthquake. In addition, the proposed model can be executed after the occurrence of the disaster, based on the links remaining functional during the response phase (i.e. the survived network). However, the proposed problem does not consider different earthquake scenarios simultaneously in designing the emergency network, and in fact, by means of the proposed model, the emergency network can be designed for each scenario. The resultant emergency network for each scenario is a network that should be controlled by police forces to provide open (in control) set of routes to perform the disaster relief operations. In other words, the design of optimal emergency route networks for different earthquake scenarios (before the occurrence of the earthquake) can help to manage better the position of police forces in the response phase, so that the proposed model has a specific solution for each earthquake scenario.
3.2 Solution method
The proposed multi-objective optimization model is decomposed into two independent sub-problems and is solved using k-shortest path algorithm and a ε-constraint technique.
A large-scale IP problem contains many variables and/or constraints. However, sometimes, special structures in the set of constraints enable us to partition the problem into two or more sub-problems that are independent of each other. Combining solutions to these sub-problems will yield a solution to the original problem. In this way, the problem is greatly simplified (Chen et al., 2010). Note that the decomposing technique discussed in this section is not what is known as decomposition approach. If the coefficient matrix A for the constraint set Ay < b, after rearrangement, takes the form shown in Table II, where A1 and A2 ≠ 0, then the IP problem can be decomposed into two independent sub-problems (P1 and P2) including a shortest path problem (P1) and a multi-objective NDP (P2).
The ERNDP sub-problems
| P1 (shortest path problem) | P2 (multi-objective network design problem) |
|---|---|
| A1 | 0 |
| 0 | A2 |
The sub-problem P1 is solved using the k-shortest path algorithm. This algorithm computes the k-simple shortest paths in weighted directed graphs (Zhang et al., 2015). The formulation is based on the selection of a number of feasible solutions that provide connection between the primary nodes (OD pairs).
The sub-problem P2 is a multi-objective problem. Several approaches can be considered to solve multi-objective programming problems (Marler and Arora, 2004; Miettinen, 2012; Cohon, 2013). The most common approaches for multi-objective optimization problems are the weighted sum method and the ε-constraint method (Heidari et al., 2018). In linear problems, the weighted sum method in the existing region can only find corners solutions, whereas the ε-constraint method in the existing region can also find non-corner solutions (Mavrotas, 2009). In addition, the results of the weighted sum method depend on the choice of the weighting quantities (Heidari et al., 2018). Hence, in order to reduce the proposed three-objective problem (P2) to a single objective one (to be solvable), we have adopted the ε-constraint algorithm proposed by Abounacer et al. (2014). In the ε-constraint method, one of the objective functions is selected to be optimized and all the other objective functions are converted into constraints by setting an upper bound to each of them (Cohon, 2013). The suggested solving methodology in the current paper can effectively reduce the decision maker (DM) role in the determination of the solutions for the multi-objective optimization problem, which can be accounted as an advantageous point in the decision making process. The solutions obtained by this proposed ε-constraint method are Pareto optimal (Miettinen, 2012). In this method, the three objectives are supposed to belong to one class of importance. The two objective functions (i.e. the length of network and the required coverage of secondary points) are converted into constraints (see Constraints (14) and (15)). Then, the other objective function (i.e. f1 or the total travel time) can be considered as the single objective function of the model (see Equation (13)). Constraint (14) in this model is the controller of the maximum length of emergency route network. The sum of selected arcs, in which ya=1, should not be more than L, which is determined by the DM of the system. Also, Constraints (15) calculates the ratio of covered points to the total coverable points and controls the least coverage ∝f for each type of secondary points f. It should be noted that in this paper, the ArcGIS, MATLAB and GAMS software are used for data preparation, the k-shortest path determination and, modeling, respectively. The case studies are tested on a computer with Dual Core CPU at 2.8 GHz with 4 GB RAM:
4. Numerical example
The model is applied to the well-known schematic network of Sioux Falls in order to illustrate its performance. The network has 24 nodes and 38 links. The trip time and the length of each link are considered as inputs. The origin (O) demand point and two types of service provider points are shown in Figure 2. Each demand point (shown by rectangular) must have an access route to both types of services (shown by triangles and circles, respectively), in order to supply the access of rescue demand.
The total length of the network is 1,592 km and all of the links are two-way. Eight shortest routes are determined for each OD pairs using the Dijkastra’s Algorithm method by coding in MATLAB software. As it can be seen, the total time decreases by increasing the emergency road length. The model has not any solution for a length less than 450 km and indeed the problem remains without a feasible solution. The model does not offer a better response with increase of the length to more than 600 units. In this situation, the access route between the whole demand points is built from the best route (the shortest one) and there would be no difference in response of maximum allowable length of 600 units and without L limitation. The ERN for the length of 500 km is shown in Figure 3. If we do not use the proposed model and simply connect all OD pairs to the nearest service provider point through the shortest path (as is a common approach in current applications), the resultant ERN will be that shown in Figure 4. As it can be seen, the suggested network (Figure 3) does not have links 45–57, 53–58, 49–52, 50–55, 2–5, 7–35 and 65–69 comparing to the network without the limitation (Figure 4). Instead, link 62–64 has been added to the ERN. These changes in the selected link indicate that the ERN is different from the shortest route-based network. The access route of demand point is built to the service provider 1 and 2 in Figures 3 and 4. The emergency road length without length limitation is 594 and the length of the ERN is 492 km.
5. Case study: Tehran
The presented study considered a subset of Tehran’s road network, consisting of major arterial roads and freeways which can be controlled by police forces after the occurrence of earthquake. This network has 2,736 links and 1,871 nodes (see Figure 5). As stated in Nikoo et al. (2018), because it is very probable that an earthquake harms two sides of a road at the same time, each pair of directed links is substituted by a two-way link. The freeway network is shown in Figure 6. The road network of Tehran separated by the type of link including major arterials, freeways and connector links is shown in Table III. In order to solve the proposed model for Tehran’s network, sufficient routes were built between each OD pairs so that one can choose the best route for them and introduce it as the emergency route. After conducting the required analysis of Tehran’s network, selected paths between the OD pairs were identified using Dijkstra’s k-shortest path algorithm and introduced as inputs for next analyses. In fact, this model chooses one of the k routes with the aim of minimizing the total trip time as discussed in Section 3. It has to be mentioned that, the proposed model has been evaluated several times and its implementation on the network was done in optimizing and coding the model. The results were obtained achieving optimality in a reasonable time (i.e. almost always less than 10 min). Less CPU times are important when the network should be executed for several scenarios of earthquake or when it should be used as a lower-level problem of a multi-level network planning problem.
5.1 Nearest points and the shortest paths
As we said before, the proposed model is looking for connecting different OD pairs. Some of these points are HADC, disaster management center, city entrances, hospitals and emergency medical services, fire-fighting and Red Crescent stations. Determining the routes for origin and destination points of each trip requires graph modeling of the network. The travel time and the length of each link have been obtained from the Comprehensive Transportation Studies of Tehran, and the shortest paths have been chosen after ensuring that the network is complete and there is no disconnection in it. Identifying the shortest paths has been done using MATLAB software and after that the data have been transferred to ArcGIS software. Another essential step for applying the model in Tehran was identifying the m supply points located in the surrounding area of each demand point. For example, identifying three hospitals close to the demand point. This has been done to build OD pairs of the relief activities.
5.2 Results for different OD pairs in Tehran
Achieving the objective of the model so that it can be responsible for practical goals and policies are one of the important points in each design. In this context, the type of connection between different origin and destination points and the number of available access points between each one of these are considered as important policies. Also, it is assumed that in the case of an earthquake, medical needs and injured people are gathered in 82 HADC, and would be transferred to hospitals and emergency centers, and Red Crescent stations through the designed paths. Three connections for each type of OD pairs are of a great importance to ensure the needed service. Based on the conducted study, it was revealed that connection of each one of the 82 HADC to all three near Red Crescents impose a significant length on the network and its length is two times of the length of HADC to medical centers or fire-fighting stations. In fact, proportion and number of Red Crescent centers in Tehran lead to a significant increase in the length of emergency routes network. The same issue exists for the refugee camps which are temporary settlement points built for receiving refugees in disasters. Despite a defined access from HADC to the nearest refugee camps, the sum of length in all of the routes is about 9,000 km. As a subsidiary result of the current study, navigation and building Red Crescent stations and temporary settlement are suggested in areas with inaccessibility. It has to be noted that access to three near Red Crescent stations imposes a significant length on the network. With clarifying the input data, the proposed model for different maximum length of the network and the minimum overlapping of them was conducted and the results of the multi-objective analysis are provided in Table IV.
Results of model: solutions set
| Coverage: f3 | |||||||
|---|---|---|---|---|---|---|---|
| Solution | L | ∝f | Travel time: f1(minute) | Emergency road length: f2(km) | 1: Mosques | 2: Schools | 3: Others |
| 1 | 700 | 0.5 | 5,034 | 698.7 | 0.639 | 0.585 | 0.697 |
| 2 | 0.6 | No feasible solution | |||||
| 3 | 800 | 0.5 | 4,901 | 800 | 0.696 | 0.648 | 0.749 |
| 4 | 0.6 | 4,901 | 751.1 | 0.637 | 0.6 | 0.717 | |
| 5 | 0.7 | 4,902 | 793.4 | 0.734 | 0.7 | 0.764 | |
| 6 | 0.8 | No feasible solution | |||||
| 7 | 900 | 0.5 | 4,901 | 899.7 | 0.753 | 0.702 | 0.795 |
| 8 | 0.6 | 4,901 | 751.1 | 0.637 | 0.6 | 0.717 | |
| 9 | 0.7 | 4,901 | 899.9 | 0.781 | 0.727 | 0.806 | |
| 10 | 0.8 | 4,903 | 898.9 | 0.802 | 0.803 | 0.813 | |
| 11 | 0.9 | No feasible solution | |||||
| 12 | 1,000 | 0.5 | 4,901 | 909.9 | 0.758 | 0.708 | 0.795 |
| 13 | 0.6 | 4,901 | 751.1 | 0.637 | 0.6 | 0.717 | |
| 14 | 0.7 | 4,901 | 911.5 | 0.753 | 0.705 | 0.759 | |
| 15 | 0.8 | 4901 | 985.9 | 0.843 | 0.803 | 0.833 | |
| 16 | 0.9 | 4,901 | 1,000 | 0.901 | 0.9 | 0.9 | |
| 17 | Solution for minimum length | 5,034 | 698.7 | 0.639 | 0.585 | 0.697 | |
| 18 | Solution for maximum coverage | 4,911 | 1261.5 | 1 | 0.999 | 0.999 | |
5.3 Discussion
The model has been implemented for the length of 700–1,000 km (with distances of 100 km) and the minimum required coverage of 0.5–0.9 and the results of the whole situations of three objectives have been provided in Table IV. The length of 650 KM has not resulted in any feasible solution. The first two columns of the table (from the right side) are inputs and the other columns (on the left side) are outputs of the model. “Emergency Route Length” is the length of network which is essentially less than the determined value for it in the model input (L). The required coverage is also more than the least determined value in input for three types of secondary points like mosques, schools and other important points. Each one of the second priority (secondary) points has different coverage.
The proposed model was executed for different maximum length of the network and the minimum overlapping of them, and the results of multi-objective analysis are provided in Figure 7. An optimal solution is not relevant here and is replaced by the concept of a solution set from which the DMs select the most preferred solution. As shown in Figure 7, a Pareto Frontier is constructed for DM to get a better sense of the set of solutions from which to select.
Generally, the total travel time is reduced with an increase in the maximum allowed length and decrease in allowed value of coverage. In fact, increase in length and decrease of coverage scales up the response interval in the model. Decrease in the time and moving toward the optimized response continues to increase the length and thereafter increase in length would have no impact on solutions. For example, the objective function value has not changed for at least 0.9 of coverage and maximum 1,000 km.
There might be no feasible solution for less length and more minimum coverage. For example, the model has not provided a feasible solution with a minimum coverage of 0.6 and length of fewer than 700 km in the second row of Table IV. It is clear that an increase in the minimum coverage would have no justified response, as well.
One can see that important centers have more coverage than schools. In other words, their distance from the main streets of the city was influential in the value of this index. It can be seen on Row 17 of Table IV that the response of the coverage limitation-free model with the least possible network length provides coverage of more than 58 percent for all three types of the second priority points.
In coverage of 0.6 in length of 800, 900 and 1,000, the length of disaster response network has a significant decrease and the same value of 751.1 km. There is no feasible solution for the maximum length of 700 for 0.6 and more, and this indicates that the coverage of these points is such that for a network with coverage of 0.6 and more, we need a network with a length of more than 700 km. Because the objective is reducing the total travel time, the model seeking the least total travel time for coverage of 0.6 holds the objective function in a fixed and favorable value, because as the length of network decreases the trip time decreases as a consequence.
In Rows 17 and 18 of Table IV, the model solution is presented considering the maximum allowable length and coverage separately. As it can be seen, achieving an almost 100 percent of required coverage for a network of about 1,260 km is possible (Figure 8). This is while the minimum possible length for the network is 699 km. The other solutions are within this range of the designed network length. The value of the objective function has not changed for the length of more than 800 km.
At the end, it should be noted that the presented results in this section are obtained using GAMS software and each runtime on average was about 10 min. However, the implementation of network flow model or vehicle routing is not possible without considering the limitations of emergency roads in networks with more than 25 nodes (in cases with much smaller than the Tehran network).
6. Conclusion
In this paper, a model was presented to identify the links of emergency route network considering the maximum coverage problem and the effective relief operations in first hours of the earthquake. The model provides access between disaster response demand points and destinations, in a way that all of the available points and routes between them are identified in the network. Providing access to the first priority points is an essential constraint of the model. The ERN preserve major emergency trips through connecting major relief points (with shorter travel times) that are pre-located in a city and can be used to carry out disaster relief operations in the aftermath of disasters considering the minimum required coverage of the secondary points. These main points are fixed in all disaster scenarios.
In this paper, an ε-constraint method was used to reduce the three-objective optimization problem to a single objective form. The results of applying the model to Tehran’s highway network indicated that the least possible length for the emergency transportation network is approximately 700 km, which is about half the total length of major roads (i.e. comprising freeways and major arterials). Also, another hint about the implementation of this model in Tehran is that the obtained runtime of the model using GAMS software was about 10 min; hence it can be used for dozens of times and under several scenarios with an acceptable speed.
The Red Crescent and temporary settlement in areas with no accessibility are one of the basic issues which increase the length of the emergency network, thus it is suggested as one of the future items to be studied. Also, the reinforcement of links against earthquake and holding a desirable performance after an earthquake has high importance. One should pay attention that this reinforcement should be under different scenarios and lead to a better performance of the whole ERN if possible. Defining a problem which can be solved simultaneously with the reinforcement and routing is another interesting topic for future studies in this area.
In this paper, a deterministic approach is used, and our model does not include any disaster scenarios explicitly. However, due to a highly uncertain condition in a catastrophic disaster, as all links of the presumed survived network may fail in reality, there would be a great uncertainty in the possible closure of the network links. Therefore, it may be deduced that the existence of more paths would provide a greater likelihood for the connection of each OD pair during the relief operations. Thus, in this paper, the uncertainty in the connectivity of OD pairs can be considered implicitly. The robust optimization approach is a good technique to model disaster scenarios that can be joined with our proposed model as a future study. For example, if one wants to retrofit the network in order to manage the emergency networks during different probable earthquake scenarios, he/she can define a new problem with two levels, the upper level of which concerns with the selection of different retrofitting alternatives while the lower level of which concerns with the determination of a set of emergency route to perform the emergency relief operations optimally given each retrofitting alternative. In fact, the current paper is dealt with the latter (lower-level) problem, and the scenarios can be incorporated in the upper-level problem.
