Time-Dependent Restoration Routing Problem: An Efficient Initial Solution

1. Questions

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?

2. Methods

The model illustrates the network performance as the total flow on an undirected graph $G = (N,A),$ where $N$ is the set of nodes, and $A$ is the set of links. Among the nodes, there is a set of origin nodes $N_{+} \subseteq N,$ each with capacity $O_{i},\ i \in N_{+},$ a set of destination nodes $N_{-} \subseteq N,$ each with a demand requirement $b_{i},\ i \in N_{-},$ and a set of transshipment nodes $N_{=} \subseteq N.$ Each link $(i,j) \in A,$ has a capacity of $u_{ijt_{e}}$ at time $t_{e}$ before disruptions. After disruptions, a subset $A' \subseteq A$ represents the set of disrupted links, each with a new capacity $u_{ijt_{d}} < u_{ijt_{e}}.$ 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 $k \in K$ can restore each disrupted link $(i,j) \in A^{'}$ in $p_{ij}^{k}$ 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 $k \in K,$ including its traveling time between each pair of consecutives assigned disrupted links $(l,h),(i,j) \in A'$ $\left( c_{(lh)(ij)} \right).$ The maximum restoration crew routing time must not exceed the given time horizon $\left( T_{\max} \right).$ The goal is to represent a convenient model, called as Binary Active model, to maximize the residual network resilience $(Я_{\varphi}(t))$ by recovering the critical disrupted links in a given time horizon per Equation 1. The network resilience $(Я_{\varphi}(t))$ measures the network performance as the aggregate difference between the total delivered flow $\left( \varphi_{it_{d}} \right)$ to destination nodes $\left( i \in N_{-} \right)$ immediately after disruption at the time $(t_{d})$ and the those of $\varphi_{it}$ at each time period $(t)$ in the restoration horizon over the difference between total network performance $\left( \varphi_{it_{e}} \right)$ before disruptions at time $(t_{e})$ and after disruptions $\left( \varphi_{it_{d}} \right).$

$$Max\ \sum_{t = 1}^{T_{Max}}{Я_{\varphi}(t)} = \sum_{t = 1}^{T_{Max}}{\sum_{i \in N_{-}}^{}\frac{\varphi_{it} - \varphi_{it_{d}}}{\varphi_{it_{e}} - \varphi_{it_{d}}}}\tag{1}$$

Other variables required for the mathematical model are as follows:

$\alpha_{kijt}:$ 1: If Crew $k \in K$ recovers Link $(i,j) \in A^{'}$ at Time $t;$ 0: Otherwise (binary)

$\vartheta_{d}^{k}:$ 1: If restoration Crew $k \in K$ originates from Depot $d \in D;$ 0: Otherwise (binary)

$\ f_{ijt}:$ Flow on Link $(i,j) \in A'$ in Time period $t$ (continuous)

$\complement_{(lh)\ (ij)}^{k}:$ Travel time of Crew $k \in K$ on the shortest path between Links $(l,h),(i,j) \in A'$ (continuous)

$\complement_{.\ }^{k}:$ Travel time of Crew $k \in K$ from its originating depot $(d \in D)$ (continuous)

$c_{d\ (ij)}:$ Travel time on the shortest path between Depot $d \in D$ and the disrupted Link $\left( i^{\ },j \right) \in A^{'}$ (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 $|K|$ crews to restore the disrupted links. Equations 11-13 record the shortest path traveling time of Crew $k \in K$ 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 $\gamma_{kijt}$ to activate disrupted Link $(i,j)$ under restoration by Crew $k \in K$ proportional to its restoration progress at time $t.$ Accordingly, we update the model to a new Proportional Active Model to reflect the new assumption as summarized in Table 2.

Equation 22 calculates the restoration progress, and consequently the proportion of operationality, of each disrupted link $(i,j) \in A^{'}.$ Equations 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.

3. Findings

Table 3 shows the computational experiment of the Binary and Proportional active model for gas $(N = 16,A = 17),$ water $(N = 49,A = 71),$ and power grid $(N = 129,A = 164)$ networks in Shelby County, TN (González et al. 2016) as depicted in Figure 1. We incorporate four disruption scenarios $M = \{ 1,2,3,4\}$ to disrupt incrementally 6%, 9%, 17%, and 23% of the links. Both models calculate the total routing time $(T)$ in presence of $|K| = 2$ 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.

Figure 1.Critical infrastructure networks of Shelby County, TN: (a) Power grid transmission, (b) Water, and (c) Gas network (González et al. 2016)

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.