Finding fast and efficient solutions has been a hot topic in post-disruption restoration problems. Although some studies attempted to find realistic network restoration planning models (Bienstock and Mattia 2007; Nurre and Sharkey 2014; Nan and Sansavini 2017; Ermagun and Tajik 2021), they never incorporated the effects of routing time on the network performance trajectory after disruptions. Other studies developed models to capture the routing time restoration crews across the network (Özdamar, Tüzün Aksu, and Ergüneş 2014; Kasaei and Salman 2016; Akbari and Salman 2017; Faturechi and Miller-Hooks 2014; Iloglu and Albert 2018; Ermagun and Tajik 2022). Due to the complex nature of routing problems discussed by Morshedlou et al. (2021), new models are designed to calculate efficient bounds for real-world problems. This research proposes a time-dependent restoration scheduling problem to produce a feasible and efficient initial solution to address the following questions: How does the spatial distribution of disruptions affect the complexity of the problem? Does partially activating under restoration links affect the network resilience trajectory?
The model illustrates the network performance as the total flow on an undirected graphwhere is the set of nodes, and is the set of links. Among the nodes, there is a set of origin nodes each with capacity a set of destination nodes each with a demand requirement and a set of transshipment nodes Each link has a capacity of at time before disruptions. After disruptions, a subset represents the set of disrupted links, each with a new capacity The model deploys crews to restore disrupted locations in the residual network in a critically limited time horizon. Only one crew is permitted to restore a disrupted location. Each crew can restore each disrupted link in time units. The main assumption, called Binary Activation, declares that each disrupted link will not return to its operational status unless fully restored. During the restoration process, the model records the routing time of each crew including its traveling time between each pair of consecutives assigned disrupted links The maximum restoration crew routing time must not exceed the given time horizon The goal is to represent a convenient model, called as Binary Active model, to maximize the residual network resilience by recovering the critical disrupted links in a given time horizon per Equation 1. The network resilience measures the network performance as the aggregate difference between the total delivered flow to destination nodes immediately after disruption at the time and the those of at each time period in the restoration horizon over the difference between total network performance before disruptions at time and after disruptions
Other variables required for the mathematical model are as follows:
1: If Crew recovers Link at Time 0: Otherwise (binary)
1: If restoration Crew originates from Depot 0: Otherwise (binary)
Flow on Link in Time period (continuous)
Travel time of Crew on the shortest path between Links (continuous)
Travel time of Crew from its originating depot (continuous)
Travel time on the shortest path between Depot and the disrupted Link (continuous)
Equations 2-7 are network flow balance constraints that send flow from supply nodes to the demand nodes through transshipment nodes and control the flow over the entire network. Equations 8-10 schedule and deploy Table 2.crews to restore the disrupted links. Equations 11-13 record the shortest path traveling time of Crew between two consecutive disrupted locations. Equations 14-15 calculate the routing time of each crew and ensures it does not exceed the given time horizon. Finally, Equations 16-21 constrain the decision variables. An alternative to the Binary Active assumption is allowing disrupted links to become partially operational during restoration, also called the Proportional Active assumption. To implement such an assumption, we introduce a binary variable to activate disrupted Link under restoration by Crew proportional to its restoration progress at time Accordingly, we update the model to a new Proportional Active Model to reflect the new assumption as summarized in
Equation 22 calculates the restoration progress, and consequently the proportion of operationality, of each disrupted linkEquations 22-24 are the counterparts of Equations 8-10, Equations 25-27 are the counterparts of Equations 11-13, and Equations 28-29 are the counterpart of Equations 14-15. Equation 30 constrains the decision variables.
Table 3 shows the computational experiment of the Binary and Proportional active model for gas water and power grid networks in Shelby County, TN (González et al. 2016) as depicted in Figure 1. We incorporate four disruption scenarios to disrupt incrementally 6%, 9%, 17%, and 23% of the links. Both models calculate the total routing time in presence of to 7 restoration crews. The results also indicate the computer processing time (CPU), and the optimality gap percentage (GAP). The (-) stands for instances with nonexistent solutions or the ones that require more than one hour of CPU time. The model is implemented using Gurobi Solver 9.0 in Python 3.6.
The results state a series of empirical observations:
The CPU time in Table 3 confirms that the proposed model provides an efficient initial solution for restoration routing problems that assume multiple crews can work on a single disrupted link to expedite its restoration process.
Despite their larger network size, the computation processing time and the maximum routing time of power grid instances are less than water network instances. This observation corroborates the importance of the geographical distribution of disruptions, given that the disruptions are scattered across the water network while they are relatively located neighboring one another in the power grid.
The proposed model provides a realistic initial solution as it incorporates the routing time of each crew into the restoration scheduling plan. The model optimality gap increases the proportional active feature, reaching high proportional performance earlier than other paths. Although the original model can elevate network performance with a more homogenous rate, the proportional active feature guarantees to restore the spatially distributed disrupted links across a network in a limited time horizon.