Prioritizing Road Network Restorative Interventions Using a Discrete Particle Swarm Optimization

The consequences of extreme events on transportation networks largely depend on (1) the level of damage to the assets after the event, and (2) the developed program to restore the demanded level of service. An optimal restoration program helps infrastructure managers in assigning the priority and the level of service recovery to damaged assets in the network such that the network functionality is restored as fast as possible and with minimal consequences that are usually monetized (Cavdaroglu et al. 2011).

Researchers have mostly focused on two approaches in developing postdisaster restoration programs. Some have used simple policies and guidelines based on engineering or economic criteria to find the order of restoring the damaged assets, for example prioritizing the recovery of the assets with higher damage levels (Buckle et al. 2006), or higher average daily traffic volumes (Miller 2014), or prioritizing the recovery of the more important or critical assets in the network (Liu et al. 2020; Scott et al. 2006). These approaches are favored in real-world practices because they are relatively fast; however, they often do not result in optimal solutions.

Others have tried to reach the optimal solution among a pool of feasible intervention sequences (Bocchini and Frangopol 2012; Çagnan and Davidson 2004; Chen and Miller-Hooks 2012; Fang et al. 2019; Fang and Sansavini 2017; Gomez and Baker 2019; Hayat et al. 2019; Liao et al. 2018; Tan et al. 2019; Vugrin et al. 2014; Xu et al. 2007; Yan and Shih 2009; Burkhalter et al. 2020). This approach needs a mathematical model whose optimal solution will provide the best compromise among the decision criteria. Researchers have implemented a multitude of objective functions with varying goals, such as the minimization of the additional travel time, disconnected links, and the overall direct and indirect costs, to develop optimal postdisaster restoration programs for transportation networks.

In this approach, an algorithm is used to search among the feasible solutions to the problem and find the optimal solution. These algorithms are divided into exact and approximate algorithms. Exact algorithms guarantee to find the globally optimal solution, whereas approximate algorithms (heuristics and metaheuristics) have some randomness, and although they will find a good solution, it may not be the best (the global optimum). However, approximate algorithms are characterized by their shorter computation time and thus are more efficient for problems with a large solution space, including selecting the optimal way to restore the demanded service in large transportation networks, after extreme events.

In the present literature, various algorithms are used to minimize the consequences of extreme events on transportation infrastructure and develop restoration programs; including stochastic mixed-integer programs (Chen and Miller-Hooks 2012; Zhang et al. 2021), genetic algorithms (GAs) (Chen and Tzeng 1999; Mao et al. 2021; Moghtadernejad et al. 2020), ant colony system (ACS) (Yan and Shih 2012), or simulated annealing (SA) (Hackl et al. 2018; Vugrin et al. 2014). According to the studies, these algorithms have been successful in finding good solutions for transportation network recovery. However, except for a few of these studies (Hackl et al. 2018; Orabi et al. 2009), the proposed algorithms were tested for their efficiency on small networks with fewer than a dozen edges; hence, more investigation is needed to assess the performance of the algorithms in real-world problems. Moreover, it is difficult to determine how well-suited each algorithm is for a specific problem because it is not possible to compare the performance of various algorithms based on the results of different studies that look at different networks and objective functions.

Since the late 1990s, computational swarm intelligence has been receiving increasing attention due to the improvements in swarm intelligence theory and is been used by researchers to solve real-world optimization problems. Particle swarm optimization (PSO) is a stochastic algorithm that is normally used in continuous search spaces but can also be implemented in combinatorial optimization problems with a discrete search space. In infrastructure management, PSO has been previously applied to the electrical energy distribution systems by Lambert-Torres et al. (2008), to maximize the supplied load and minimize the energy loss. Ahmed et al. (2019) implemented a discrete particle swarm optimization (DPSO) algorithm for pavement maintenance activities, and Hu et al. (2012) used PSO for an optimal allocation of earthquake emergency shelters. Edrisi and Askari (2020) used a model for critical infrastructure that integrated the predisaster mitigation and preparedness actions with postdisaster response operations during earthquakes and found the optimal budget allocation using PSO.

In a study by Chang (2018), GA and PSO were used to optimize network optimization scheduling, where the suitability of the algorithms was compared in 12 network instances that were generated using a random geometric graph algorithm. However, despite the current applications of PSO in the infrastructure sector, its application in the postdisaster restoration of real-world transportation networks has not been investigated yet. The difference between the nature of these studies is due to the traffic interruptions that are considered in the latter but not in the former studies and have a strong influence on the complexity and the overall computation time.

Consequently, this paper investigates the application of a DPSO algorithm in developing suitable restoration programs with regards to the overall direct and indirect costs for real-world transportation networks. The suitability of the algorithm is examined in a road network in Switzerland for multiple flood events with different damage levels, and the results are compared with a benchmark model and the SA algorithm that was previously studied on the same network by Hackl et al. (2018).

The structure of the paper is as follows. First the objective function of the model for developing the restoration programs is reviewed. Then the PSO algorithm is adjusted to reach a good solution for the objective function. The proposed restoration model is tested on a case study in Chur, Switzerland, and the introduced DPSO algorithm is used to minimize the overall costs after three flood events. The results are then compared with a benchmark model and the SA algorithm and the advantages and limitations of the DPSO are discussed along with some suggestions for future work.

Optimal restoration programs propose the sequence and level of interventions that will result in restoring the functionality of the network with minimal consequences (in this paper the functionality is defined in terms of flow capacity). The objective function of the restoration model in this study was previously introduced by Hackl et al. (2018). This function minimizes the sum of the direct and indirect costs [Eq. (1)], i.e., the cost of the restoration work [Eq. (2)] and the costs related to the loss/reduction of service [Eq. (3)] from the time the hazard happens until the restoration work is finishedwhere $C_{n,i}$ = overall cost of intervention $i$ on object $n$ with a damage state $s$ and comprises the overall fixed, variable, and resource-related costs (Hackl et al. 2018). In each time period $t$, only one intervention $i\in I(n|s)$ can be executed for the damaged object $n\in N^s$. If in the time period $t$, the intervention $i$ is executed on the object $n$ with a damage state $s$, then the variable ${\delta }_{n,i,t}=1$; otherwise, ${\delta }_{n,i,t}=0$

The indirect costs $(C^{\mathrm{IC}})$ are caused by additional travel time $\mathrm{\Pi }-{\mathrm{\Pi }}^0$ for all paths $p\in P_{od}^{s\backslash g}$, or the loss of connectivity $\mathrm{\Lambda }$ for all paths $p\in P_{od}^g$, where $P_{od}^{s\backslash g}\subseteq P_{od}$ is the set of origin–destination (od) paths with some traffic flow that does not comprise any objects with no functionality $g$, and $P_{od}^g$ is the set of all disconnected od-paths.

The indirect costs are calculated from the time the hazard starts until the time all the damaged objects in the network are restored. This value is equal to the difference between the indirect costs in period $t$ and $t=0$ when the network was fully functional (Hackl et al. 2018). Here, $x_{e,t}$ represents the link flow on edge $e$ in period $t$ (hence, $x_{e,0}$ refers to the link flow at $t=0$ where the hazard has not happened yet) and is estimated by solving a user equilibrium assignment as indicated in Eq. (4)where $C_e^T$ = travel cost function for edge $e$ and can be determined from Eq. (5) (BPR 1964)where $t_e^0$ = free-flow travel duration; $t_{e,t}$ = travel duration on edge $e$ in each period $t$; $y_{e,t}=\mathrm{edge}$ capacity in period $t$; and parameters $\alpha$ and $\beta$ are for calibration.

The costs related to the loss in connectivity $\mathrm{\Lambda }$ [Eq. (3)] are estimated by multiplying the estimated labor productivity value $\upsilon$ and the number of lost demands $f_{od}(P)$ due to disconnected paths $P_{od}^g$ in period $t$ (Freeman 2008), as indicated in Eq. (6)

The costs due to the additional travel time $\mathrm{\Pi }$ [Eq. (3)] are the summation of the costs due to travel prolongation $\mathrm{\Phi }$ [Eq. (7)], and the related increase in vehicle operating costs $\mathrm{{\rm Y}}$ [Eq. (8)]where ${\mu }_{e,w}$ = percentage of each vehicle type $w$ on edge $e$; ${\xi }_{e,w}$ = travel costs per time unit for each vehicle type $w$ on edge $e$; $l_e$ = length of each edge; and $F_w$, $h$, and ${\rho }_w$ = average fuel consumption, average fuel price, and the operating and maintenance costs for each vehicle type without considering fuel consumption, respectively.

It can be observed that the objective function above is a bilevel optimization problem, where the minimization of the indirect costs in Eq. (1) is constrained to the optimization of the traffic flow assignment in Eq. (4). To solve this problem, an optimization algorithm should be implemented to reach a good solution for the objective function in Eq. (1), and a proper traffic model should be used to solve the link-flow assignment in Eq. (4).

The following section will provide a brief overview of the classification of optimization methods and a detailed description of how the continuous PSO algorithm is adjusted to be used in discrete combinatorial problems.

The suitability of approximate algorithms for identifying the optimal restoration programs is dependent on the computation time (i.e., efficiency) and the closeness of the solution to the global optimum, which is problem-specific and depends on the objective function, the size of the network under study, the number of damaged assets and intervention options, and the choice of parameters for the optimization algorithm.

Choosing the right parameters for metaheuristic algorithms is a challenging task and requires considerable time and effort. Eiben et al. (1999) categorized the principal ways of setting parameter values into parameter tuning and parameter control. In parameter tuning, the parameter values are found and set before running the algorithm, whereas in parameter control, the parameter values change while the algorithm is being executed. For example in PSO, the inertia coefficient ($m$) is normally controlled, and it is widely accepted in literature to gradually decrease it from 0.9 to 0.4 (Rezaee-Jordehi and Jasni 2013). The individual $({\gamma }_1)$ and social $({\gamma }_2)$ coefficients are, however, problem-dependent and are normally tuned before executing the algorithm.

In this section, a road network located in Chur, Switzerland, was selected as the area of study to test the suitability of the proposed DPSO algorithm in developing restoration programs. This network is near the Rhine River, and the historical records indicated that the zone is susceptible to annual floods and landslides (Hackl et al. 2018).

In total, the network contains approximately 610 km of roads (motorway, main, and minor roads) which comprises 2,011 road sections and 116 bridges (Fig. 4). The road network information was taken from the VECTOR25 data set, provided by swisstopo (2019).

In this paper, parameter tuning was conducted for three flood scenarios with different levels of damage to the network. However, reality is more complex and a more rigorous effort must be made in considering various hazard scenarios beforehand to tune the parameters for postdisaster decision making. The following scenarios were only considered as illustrative examples of the effect of the number of damaged assets on the parameters of PSO:

The suitability of the parameters was tested in terms of the overall direct and indirect costs and the average computation time. The direct costs of restoration work were estimated using Eq. (2) and by using the data provided in Table 1. The total indirect costs were calculated using Eq. (3) and Table 2. It was assumed that there were six working crews available, each working 8 h per day. Three intervention options were considered to restore the damaged objects, namely high-priority, normal-priority, and low-priority interventions. The number of available work crews and types of interventions were solely selected as an illustrative example in this study and can always be changed. The availability of more work crews will result in a shorter restoration period (because the damaged objects can be restored faster) and hence lower the imposed indirect costs without affecting the computation time. On the other hand, adding multiple intervention types will enlarge the search space and hence will add to the computation time.

A conjugate direction Frank–Wolfe (CFW) method (Mitradjieva and Lindberg 2013) suitable for convex optimization problems such as in traffic assignments (Gawron 1998) was employed for the traffic flow modeling. This user equilibrium traffic assignment model was selected because it is relatively fast and widely used in practice. $C_e^T$ was estimated using cost–flow relationship presented in Eqs. (4) and (5), i.e., the lower-level optimization. The calibration parameters in Eq. (5) were set as $\alpha =0.15$ and $\beta =4$ as suggested by the Highway Capacity Manual (Horowitz 1991; Hackl et al. 2018).

As suggested by Rezaee-Jordehi and Jasni (2013), the inertia coefficient ($m$) was set to gradually decrease from 0.9 to 0.4. The choice of individual $({\gamma }_1)$ and social $({\gamma }_2)$ coefficients and the population size are affected by the size of the search space, which is mainly dependent on the number of damaged objects that need to be restored (regardless of the hazard type), and the intervention options. In this study, the population size was examined for $n\in \{5,10,15\}$ particles to provide a balance between accuracy and computation speed. The ${\gamma }_1$ and ${\gamma }_2$ coefficients in PSO were tested in the range [$1.8-2.2$] with 0.2 increments, as suggested by Babazadeh et al. (2011) to converge to a good solution within 100 iterations. To allow for better comparability of the results, the same seed for the random generator of the initial state was used for all tests in each scenario. Fig. 5 shows the movement of the particles in the search space in each iteration for the worst-case scenario (largest search space and smallest population size), i.e., 50 damaged objects and a swarm with five particles. The figure illustrates that the swarm a reaches a (good) solution within 100 iterations.

Because it was not possible to find the global optimum for this problem, the quality of the solutions were compared with a benchmark model that is the standard approach in practice (Table 3). The solutions are in terms of million monetary units. The adopted benchmark model uses a prioritization rule where it first sorts the damaged objects based on their average traffic flow and then among the objects with the same traffic flow, it prioritizes the restoration of the objects with major damage. The best solutions reached for each combination of parameters for the three scenarios are summarized in Table 3 and illustrated in Fig. 6.

Comparing the solutions from DPSO with the benchmark model confirmed that with a good choice of parameters, the algorithm can reach a good solution (better than the existing benchmark model) within 100 iterations. The results suggest that in this network when smaller population sizes are selected, to reach a good solution, larger values of ${\gamma }_1$ and ${\gamma }_2$ coefficients should be used. However, when the number of particles is increased, relatively smaller ${\gamma }_1$ and ${\gamma }_2$ values would reach better solutions. Moreover, as the number of particles is increased, the solutions improve [except for Scenario 1 with 15 particles, where the best solution was 2.268 million monetary units ($mu$)], which was identical with the best solution reached with 10 particles in this scenario. This makes sense because as the number of particles increases, more agents are searching for a good solution, and the algorithm can conduct a wider search and would probably find better solutions. However, the computation time of the algorithm significantly increases by increasing the number of particles. Consequently, a compromise must be made between cost-minimization and the time to reach a good solution because in reality, delays in developing a restoration program would add to the inflicted indirect costs. One possible way to ensure achieving good solutions with a fewer number of particles is to introduce a good initial state such as the solutions developed by simple prioritization rules (benchmark model).

All tests were conducted on a shared $2\times 10$ server running on Linux 64 bit operating system with a Core Intel Xenon E5-2690v2 3.0 GHz, with 384 GB DDR2. Therefore, in addition to the number of damaged objects and particles, the computation time was also influenced by the number of users at the time the tests were running. However, the average computation time (Table 3) can provide a fair estimation of the time required to develop a suitable restoration program for each case.

By comparing the best-achieved solution and the average computation time with respect to the population size for each scenario, the following parameters were chosen for the DPSO algorithm in this case study:

Because metaheuristic algorithms do not guarantee finding the globally optimal solution, it is almost impossible to learn how close the attained solutions are to the global optimum. Consequently, the stand-alone implementation of the algorithms will not demonstrate how well-suited each algorithm is for a specific problem. So far, many researchers have studied the application of a single metaheuristic algorithm for developing restoration programs for their networks; also, many of these studies have been conducted on illustrative examples for small networks with few edges and not on real-world networks, which makes the tailored algorithms unsuitable for making comparisons in real-world case studies.

To test the suitability of the proposed DPSO algorithm, the method was compared with the SA algorithm proposed by Hackl et al. (2018), which was tested on the same network as this study (Chur, Switzerland), to find which one is more suitable in the postdisaster restoration of road networks. Moreover, for both algorithms, the initial state was selected using the benchmark model to show how much improvement can be attained over the current practice if heuristic algorithms are used instead of relying only on the prioritization rules. For both algorithms, computation times were considered in calculating the imposed indirect costs to allow for a fair demonstration of the potential added benefit that can be attained if optimization approaches are used on top of the existing benchmarks models. This biased initiation will also save computation time and ensure that the search outcome will not be worse than the solution by the conventional prioritization rules that are used by decision makers in real life. This is especially significant in situations where, due to high computation time, the number of particles in DPSO and the iterations per step in SA are decreased.

The implementation of the SA algorithm in the Chur network was discussed in detail by Hackl et al. (2018) and is illustrated in the flowchart in Fig. 7. In this study, the same cooling schedule was selected for the SA algorithm as used by Hackl et al. (2018), where at every $j$th iteration out of $J$, the initial temperature $T_0$ is multiplied by $e^{(k.(j/J))}$, where $\kappa$ is the decay rate and is calculated as:The temperature parameters for the cooling schedule, i.e., $T_{\max }=2,500$ and $T_{\min }=2.5$, were adopted as proposed by Ben-Ameur (2004) and Hackl et al. (2018).

The number of steps (for the original temperature $T_{\max }$ to reach $T_{\min }$) and iterations per step for the three case studies were selected as follows:

These parameters (steps and iterations per step) were adjusted with the goal that the maximum computation time per scenario would be 15 h to allow for better comparability with DPSO. The results and the improvements of the algorithms over the benchmark model are summarized in Table 4.

The results suggest that when a good initial state (benchmark model) is introduced, DPSO can reach significantly better solutions than when a random initial state is used (Table 3). The best solutions attained by DPSO with a random initial state for the three scenarios were 2.268, 7.095, and 18.225, respectively, without considering the additional costs imposed due to the delays (Table 3). These values for the DPSO with biased initiation were 2.280, 6.792, and 17.621, including the imposed indirect costs due to the delays related to the computation time (Table 4). Even with random initiation, DPSO reached better solutions than the benchmark model, i.e., 2.375, 7.484, and 19.745 for the three scenarios, respectively.

DPSO is a slower algorithm in comparison with SA, but due to benefiting from the swarm intelligence, it needs fewer iterations to reach a good solution.

In Scenario 1, for the network with few damaged objects to restore, both algorithms reached the same solution, but SA took 42% less time to reach this solution. Consequently, SA seems to be a better choice. In Scenario 2, SA reached a slightly better result, but it took 40% more time to reach this solution. Considering that at time $t=10\mathrm{h}$, the solution found by SA was 7.405, perhaps the DPSO is more suitable because the cost difference is not that significant to compensate for the longer computation time. In the last scenario, the DPSO reached a better solution (around 2%) but the computation time was approximately 14% more. In this scenario, although DPSO seems more suitable, the choice of the algorithm may be dependent on decision makers’ preference based on the time or budget constraints.

This paper proposed a discrete particle swarm algorithm to find the optimal postdisaster restoration programs for transportation networks. The parameters of the algorithm were tuned for a case study on a road network in Chur, Switzerland, and the performance of the algorithm was compared with SA that was previously investigated on this network to develop suitable restoration programs. The results suggest that each iteration for DSPO takes longer than SA but because the algorithm is using the collective information from the particles that are simultaneously searching for a better solution, the algorithm converges to a good solution with fewer iterations in comparison with SA. However, this advantage would be significant in networks with a medium to a large number of damaged objects.

The proposed model is an improvement over the current state of the art and also contributes to risk-informed decision making, however, it has the following limitations that should be kept in mind:

All data, models, or codes that support the findings of this study are available from the corresponding author upon reasonable request.

This work has received funding from the European’s Union Horizon 2020 research and innovation program under the Grant Agreement No. 769373 (FORESEE project), the Natural Sciences and Engineering Research Council of Canada (NSERC), and the Fonds de recherche du Québec - Nature et Technologie (FRQNT).