# Adaptive Variable Neighborhood Search-Based Supply Network Reconfiguration for Robustness Enhancement

Authors: Ping Lou; Yuting Chen; Song Gao
Journal: Complexity
 (2020)

---

## Abstract

Robustness of a supply network highly depends on its structure. Although structural design methods have been proposed to create supply networks with optimal robustness, a real-life supply network can be quite different from these optimal structural designs. Meanwhile, real cases such as Thailand floods and Tohoku earthquake demonstrate the vulnerability of supply networks in real life. Obviously, it is urgent to enhance the robustness of existing real-life supply networks. Thus, in this paper, a supply network reconfiguration method based on adaptive variable neighborhood search (AVNS) is proposed to enhance the structural robustness of supply networks facing both random and target disruptions. Firstly, a supply network model considering the heterogeneous roles of entities is introduced. Based on the model, two robustness metrics,Rr and Rt, are proposed to describe the tolerance of supply networks facing random and target disruptions, respectively. Then, the problem of reconfiguration-based supply network robustness enhancement is described. To solve the problem effectively and efficiently, a new heuristic based on general variable neighborhood search, namely, AVNS, is proposed. Finally, a case study based on three real-life supply networks is presented to verify the applicability and effectiveness of the proposed robustness enhancing method.


---

## Body

## 1. Introduction

A supply network is created when two or more entities are connected by resource flows, such as product flows, material flows, or information flows, to fulfill the demands of downstream customers [1]. With the development of international trade and lean manufacture, a modern supply network can be large-scale and extremely complex [2]. Thousands of entities such as suppliers, manufacturers, and retailers are interconnected to form a complex system.At the same time, disruptions often descend upon supply networks, especially for the global and large-scale ones [3–5]. A related survey indicates that nearly 75% of companies experience at least one supply network disruption a year [6]. These supply network disruptions can mainly be classified into two categories: random disruptions and target disruptions [7–9]. Usually, random disruptions refer to disruptions caused by unintentional destruction, such as natural disasters or accidental events. Target disruptions denote disruptions caused by intentional attacks, like terrorist or military attacks. In a supply network, a disruption may damage only one or a very few number of entities at first, but its impact may propagate through the interconnected entities and even cause massive loss to the entire network [10]. In 2011, Thailand floods damaged several hard disc suppliers, leading multiple computer manufacturers depending on them unable to continue the production [7]. Around the same year, Tohoku earthquake affected almost all major automobile manufacturers globally, because several Japanese suppliers were damaged severely in the earthquake [11]. In 2018, the main plant of an automobile supplier, Meridian Magnesium, caught fire. This incident also forced multiple automobile manufacturers to stop production including BMW, Mercedes-Benz, General Motors, Fiat Chrysler Automobiles, and Ford Motor Co. [12]. There are also real cases of man-made supply network disruptions. In 2016, the production of three plants of Volkswagen in German was halted due to supply disruptions [5]. These production halts were caused by a legal dispute with a supplier which belonged to a prevent group. Therefore, the robustness of a supply network against disruptions is critically important, and it has gained much attention from supply network managers and researchers in the past decades.Traditionally, supply network disruptions are investigated from the perspective of risk management. These studies mainly focus on identifying, assessing, and mitigating of risks [13, 14]. Recently, the investigation of supply network disruptions has been expanded to network level [15–18]. From the perspective of network, a supply network can be described as a complex network composed by entities (e.g., manufacturers and suppliers) and inter-entity relations (e.g., product transmitting relations). Using the complex network modeling and analysis methods, it has been revealed that the structural characters of a supply network, such as random and scale-free, affect its robustness greatly [19–23]. To find an optimal structure of supply networks which can withstand both random and target disruptions, supply network structural designs based on various complex network models have been proposed in the past decades [8, 9, 24, 25]. In spite of these proposed optimal structural designs, efforts on structural robustness optimization for existing real-life supply networks are very limited. In reality, the construction of a supply network is the result of various processes, which may be not correlated with the robustness against disruptions. Thus, a real-life supply network can be quite different from these optimal designs. For example, according to the research of Shi et al., supply networks whose degree distribution obeys Poisson distribution are robust to both random and targeted disruptions [25]. However, empirical studies found that degree of many real-life supply networks exhibits power-law distribution [26, 27]. In addition, real cases also reveal the vulnerability of real-life supply networks. One possible method to deal with such a problem is designing an entirely new supply network, which can be costly and time-consuming. It seems more realistic to take the existing structure into consideration and reconfigure the existing supply network. For example, after the great loss in 2011 Tohoku earthquake, Toyota realized the fragility of its supply network [28]. Then, Toyota decided to exam and redesign the current supply network, rather than designing an entirely new supply network to replace the existing one.Based on these previous works, this study adopts the complex-network view of supply networks and proposes a supply network reconfiguration method based on adaptive variable neighborhood search (AVNS) for robustness enhancement. Firstly, a supply network model considering different roles of entities like manufacturers, suppliers, and retailers is introduced. Based on the model, two metrics are proposed to evaluate the robustness of a supply network facing random and target disruptions, respectively. Then, an AVSN-based supply network reconfiguration method is presented for robustness enhancement. Finally, a case study based on real-life supply networks is presented. The out-performance of the AVSN-based reconfiguration method is validated by comparative experiments.The remainder of this paper is listed as following. The related works are expounded in Section2. Section 3 presents the supply network model and robustness evaluation. Section 4 shows the AVNS-based supply network reconfiguration method. Section 5 presents the case study. Section 6 gives a brief conclusion.


## 2. Related Works

### 2.1. Supply Network Disruptions and Robustness

Supply network disruptions are unpredictable, unavoidable, and varied, which can be caused by both natural and man-made disasters [29–31]. It has been observed that supply network disruptions occur more frequently and incur more severe damages in the past decades. According to a report of the Centre for Research on the Epidemiology of Disasters, it has been observed that disasters including both natural and man-made disasters have increased exponentially all over the world in the past decades [32]. Considering the varied nature and the severe impacts of supply network disruptions, it is critically important to analyze and enhance the robustness of supply networks facing disruptions.In the context of supply networks, robustness refers to the ability to maintain the basic function under various situations, including disruptions [33, 34]. A robust supply network should be capable of absorbing disruptions to minimize the negative impact on its performance. In the past years, robustness and several other similar concepts, like resilience and reliability, have been defined broadly [22, 23, 33, 35, 36]. The definitions are varied from author to author. For example, resilience has been defined as the capacity of a supply network to recover from disruptions [37]. A supply network is reliable when it can maintain its basic operation under a minimum service level [35].To analyze supply network robustness from the view of complex network structure, the robustness of a supply network is defined as its ability to keep the basic function and connectivity under the loss of some structures or functions due to natural and man-made disasters, as it is indicated by Zhao et al. [8, 9, 24].


### 2.2. Robustness Analysis of Supply Networks from the Perspective of Complex Network

Due to the capability to reveal the inherent laws of complex systems, complex network theory provides an effective tool to analyze complex systems in real life. Along with the wide application of complex network theory in many areas like ecological system [38], communication network [39], and vehicle routing [40], supply network managers and researchers also consider to apply complex network theory into supply network researches.From the perspective of complex network, a supply network can be described as a set of nodes and edges, which represent entities such as manufacturers and suppliers and inter-entity relations like product transmitting relations, respectively. Using complex network modeling and analysis methods, researchers try to analyze the correlation between supply network structure and robustness so as to find an optimal structure of supply networks, which can withstand both random and target disruptions [22, 23, 25, 41]. As a pioneer, Thadakamalla et al. firstly introduced complex network theory into supply network robustness analysis [36]. Based on the growth models of complex network, they proposed a supply network model based on a hybrid growth mechanism of preferential attachment [42] and random attachment [43]. In addition, they also introduced standard network connectivity measurements, average length in the largest connected component (LCC), and the size of LCC (SLCC) to analyze the tolerance of supply networks facing both random and target disruptions. To analyze the impact of structural characters on supply network robustness, Nair and Vidal constructed twenty supply networks based on agent-based modeling, which includes ten supply networks generated using preferential attachment and ten networks generated using random attachment [22]. SLCC was also adopted to evaluate supply network robustness. They found that the average length of paths connecting nodes in a supply network is negatively correlated with its robustness. Kim et al. also analyzed the robustness of four basic supply network structures to find the optimal supply network structure [20]. They found that scale-free supply network is most robust facing random disruptions. Most of these previous researches describe a supply network as a unipartite network, neglecting the heterogeneous roles of entities in a supply network. Such simplification is extremely unrealistic and also limits the analysis of supply network robustness [23]. Due to the unipartite modeling method, robustness evaluation of supply networks has to use standard network connectivity measurements, such as SLCC. Several researchers have begun to consider the role differences of entities in a supply network, when describing supply networks using complex network models [8, 25, 44, 45]. Zhao et al. proposed a supply network model considering the roles of demanding and supplying nodes [8, 9, 24]. Based on the model, largest functional subnetwork (LFSN) is defined as the largest connected component containing at least one node of supplying nodes and demanding nodes. Then, LFSN-based measurements were used as performance metrics to verify the effectiveness of proposed supply network modeling method. However, in the supply network model proposed by Zhao et al., only two types of nodes are taken into consideration. In reality, a supply network can include multiple types of entities. Based on the study by Shi et al., we proposed a supply network model considering multiple types of entities [25]. Based on the model, they gave the definition of largest all-role connected component (LACC). LACC is defined as a LCC in which all role types of nodes exist. Based on the definition of LACC, size of LACC (SLACC) was introduced as a performance metric to verify the effectiveness of proposed grow-mature-decline (GMD) supply network model.In spite of these proposed optimal structural designs, efforts on structural robustness optimization for existing real-life supply networks are very limited. Recently, with the emergent of third-party supply network information platforms, empirical studies of supply network structures have been proposed. It is revealed that supply networks in real life can be quite different from these optimal designs [46, 47]. In addition, real cases also present the vulnerability of supply networks in real life. Clearly, it is urgent to develop methods for enhancing the robustness of supply networks in real life. Thus, this study contributes to propose a supply network reconfiguration method based on AVNS for robustness enhancement and the effectiveness of it is validated using supply networks in real life.


## 2.1. Supply Network Disruptions and Robustness

Supply network disruptions are unpredictable, unavoidable, and varied, which can be caused by both natural and man-made disasters [29–31]. It has been observed that supply network disruptions occur more frequently and incur more severe damages in the past decades. According to a report of the Centre for Research on the Epidemiology of Disasters, it has been observed that disasters including both natural and man-made disasters have increased exponentially all over the world in the past decades [32]. Considering the varied nature and the severe impacts of supply network disruptions, it is critically important to analyze and enhance the robustness of supply networks facing disruptions.In the context of supply networks, robustness refers to the ability to maintain the basic function under various situations, including disruptions [33, 34]. A robust supply network should be capable of absorbing disruptions to minimize the negative impact on its performance. In the past years, robustness and several other similar concepts, like resilience and reliability, have been defined broadly [22, 23, 33, 35, 36]. The definitions are varied from author to author. For example, resilience has been defined as the capacity of a supply network to recover from disruptions [37]. A supply network is reliable when it can maintain its basic operation under a minimum service level [35].To analyze supply network robustness from the view of complex network structure, the robustness of a supply network is defined as its ability to keep the basic function and connectivity under the loss of some structures or functions due to natural and man-made disasters, as it is indicated by Zhao et al. [8, 9, 24].


## 2.2. Robustness Analysis of Supply Networks from the Perspective of Complex Network

Due to the capability to reveal the inherent laws of complex systems, complex network theory provides an effective tool to analyze complex systems in real life. Along with the wide application of complex network theory in many areas like ecological system [38], communication network [39], and vehicle routing [40], supply network managers and researchers also consider to apply complex network theory into supply network researches.From the perspective of complex network, a supply network can be described as a set of nodes and edges, which represent entities such as manufacturers and suppliers and inter-entity relations like product transmitting relations, respectively. Using complex network modeling and analysis methods, researchers try to analyze the correlation between supply network structure and robustness so as to find an optimal structure of supply networks, which can withstand both random and target disruptions [22, 23, 25, 41]. As a pioneer, Thadakamalla et al. firstly introduced complex network theory into supply network robustness analysis [36]. Based on the growth models of complex network, they proposed a supply network model based on a hybrid growth mechanism of preferential attachment [42] and random attachment [43]. In addition, they also introduced standard network connectivity measurements, average length in the largest connected component (LCC), and the size of LCC (SLCC) to analyze the tolerance of supply networks facing both random and target disruptions. To analyze the impact of structural characters on supply network robustness, Nair and Vidal constructed twenty supply networks based on agent-based modeling, which includes ten supply networks generated using preferential attachment and ten networks generated using random attachment [22]. SLCC was also adopted to evaluate supply network robustness. They found that the average length of paths connecting nodes in a supply network is negatively correlated with its robustness. Kim et al. also analyzed the robustness of four basic supply network structures to find the optimal supply network structure [20]. They found that scale-free supply network is most robust facing random disruptions. Most of these previous researches describe a supply network as a unipartite network, neglecting the heterogeneous roles of entities in a supply network. Such simplification is extremely unrealistic and also limits the analysis of supply network robustness [23]. Due to the unipartite modeling method, robustness evaluation of supply networks has to use standard network connectivity measurements, such as SLCC. Several researchers have begun to consider the role differences of entities in a supply network, when describing supply networks using complex network models [8, 25, 44, 45]. Zhao et al. proposed a supply network model considering the roles of demanding and supplying nodes [8, 9, 24]. Based on the model, largest functional subnetwork (LFSN) is defined as the largest connected component containing at least one node of supplying nodes and demanding nodes. Then, LFSN-based measurements were used as performance metrics to verify the effectiveness of proposed supply network modeling method. However, in the supply network model proposed by Zhao et al., only two types of nodes are taken into consideration. In reality, a supply network can include multiple types of entities. Based on the study by Shi et al., we proposed a supply network model considering multiple types of entities [25]. Based on the model, they gave the definition of largest all-role connected component (LACC). LACC is defined as a LCC in which all role types of nodes exist. Based on the definition of LACC, size of LACC (SLACC) was introduced as a performance metric to verify the effectiveness of proposed grow-mature-decline (GMD) supply network model.In spite of these proposed optimal structural designs, efforts on structural robustness optimization for existing real-life supply networks are very limited. Recently, with the emergent of third-party supply network information platforms, empirical studies of supply network structures have been proposed. It is revealed that supply networks in real life can be quite different from these optimal designs [46, 47]. In addition, real cases also present the vulnerability of supply networks in real life. Clearly, it is urgent to develop methods for enhancing the robustness of supply networks in real life. Thus, this study contributes to propose a supply network reconfiguration method based on AVNS for robustness enhancement and the effectiveness of it is validated using supply networks in real life.


## 3. Supply Network Model and Robustness Evaluation

### 3.1. Supply Network Model

In this study, a supply network is modeled as a networkG = (V, E), where V=v1,v2,…vv is the node set, representing the entities in the supply network. |V| represents the total number of nodes. E is the edge set, representing product transmitting relations. E=vi,vj, where vi,vj∈E, if there is a product transmitting relation between node vi and vj.Since entities in a supply network can play various roles like manufacturers, suppliers, and retailers, node type is introduced as a node attribute to describe the specific roles nodes playing. Node type is presented asRole=rolevi, where rolevi∈type1,type2,…,typeM denotes the specific role of node vi in the supply network G and M is the total number of node types in the network.Figure1 presents an example to illustrate the modeling method. The supply network presented in Figure 1 is composed of 3 different types of entities, namely, retailers, manufacturers, and suppliers. The three types of entities are represented by green, red, and yellow nodes, respectively. Edges connecting these entities represent product transmitting relations between them. It is observed that edges exist not only between different types of nodes but also same types of nodes in the network. The main reason is that, with technological developments, the inter-entity relations can be various and complex in a supply network. Product transmitting relation can exist between different types of entities as well as same types of entities [8, 25].Figure 1
Illustration of the supply network model.


### 3.2. Robustness Evaluation

The robustness of a supply network is defined as its ability to keep the basic function and connectivity under the loss of some structures or functions due to natural and man-made disasters [8, 9, 24]. When evaluating the robustness of a supply network, two aspects need to be considered: disruption models for simulating the risk scenarios and evaluation metrics to measure the network’s ability to withstand disruptions. Thus, in this section, two commonly used disruption models, random and target disruption models, are introduced. Then, the robustness evaluation metrics corresponding to the two disruption models are also proposed.


#### 3.2.1. Disruption Models

When evaluating the robustness of a supply network, most current studies consider two typical disruption models: random disruption model and target disruption model. They are corresponding to two risk scenarios: unintentional destruction and intentional attack [8, 36, 37]. Based on these previous works, the two types of disruption model are adopted in this study.Before introducing the disruption models, the following assumptions are made.Assumption 1.
The disruption of a node in a supply network is treated as the complete damage of it. That is to say, once a node is disrupted, it will lose all the functions of it and it will not recover anymore. Thus, the disruption of a node is modeled as the removal of it.Assumption 2.
The adaptive behaviour of nodes, such as making temporary connections with alternative nodes and so on, is not considered in this study.
(1) Random disruption model. Random disruptions refer to unintentional destruction, such as natural disasters (e.g., earthquakes and floods), unexpected economic events (e.g., recessions and bankruptcy), and accidents (e.g., power blackout and fire). For such disruptions, the places where disruptions descend upon are usually unpredictable. In general, random disruptions are modeled using random node removals, where each node has an equal probability to be disrupted. The procedure of simulating random disruptions can be described as follows:(a)
Ranking nodes randomly.(b)
Nodes are removed from the network progressively following the random ranking calculated in step a. When a node is removed, all of its links in the network are also removed.(c)
The process is iterated until all nodes in the network have been removed.
(2) Target Disruption Model. On the other hand, target disruptions refer to intentional attacks, like terrorist and military attacks, which are aimed at maximizing the damage to the entire supply network by targeting nodes in the network believed to be “important.” Usually, the node “importance” is measured by degree, namely, the number of edges attached to it [48]. The procedure of simulating target disruptions is listed as follows:(a)
Ranking nodes according to degree centrality in the descending order. The degree of a given nodevi is presented using the following equation:(1)ki=φi,whereφi represents the node set connected to node vi and |φi| represents the number of nodes in φi.(b)
Nodes are removed progressively following the degree-based ranking. When a node is removed, all of its links in the network are also removed.(c)
The process is iterated until all the nodes in the network have been removed.


#### 3.2.2. Evaluation Metrics

Based on the two disruption models used in this study, two robustness metrics are proposed to evaluate supply networks’ tolerance of random and target disruptions, respectively.Traditionally, network robustness evaluations are mainly based on LCC. Since nodes can play heterogeneous roles in a supply network, the definition of LCC has been extended into the context of supply networks by many previous works. In this study, we will use the definition of LACC and SLACC proposed by Shi et al. to measure the performance of a supply network facing disruptions [25].Definition 1.
LCC is defined as the largest subnetwork in which any pair of nodes can be connected. The expression of LCC is presented using the following equation:(2)GccV,E=GV,E|∀vi∈V,∀vj∈V,∃path connectingviandvj,(3)GLCCV,E=GCCV,E|∀GV,E∈GccV,E,GV,E<=GCCV,E,where equation (2) denotes the connected component set, which is composed of subnetworks in which any pair of nodes can be connected and equation (3) denotes the set of LCC.Definition 2.
LACC is defined as a LCC that includes at least one node of each role type. The expression of LACC is presented using the following equation:(4)GAV,E=GccV,E|∃vi1∈V,rolevi1=type1∧⋯∧∃viM∈V,roleviM=typeM,(5)GLACCV,E=GAV,E|∀GV,E∈GAV,E,GV,E<=GAV,E,where equation (4) denotes the all role connected component set, which is composed of subnetworks, in which any pair of nodes can be connected and contain all role types and equation (5) denotes the set of LACC.
Based on the definition of LACC, SLACC of a given supply networkG is defined as the number of nodes in LACC. The expression is presented using the following equation:(6)SLACCG=GLACCV,E,where |GLACC (V,E)| represents the number of nodes in LACC.
The illustration of LACC and SLACC is presented in Figure2. Figures 2(a) and 2(b) present a supply network before disruption and after disruption, respectively. As presented in Figure 2(a), all 13 nodes form a connected component which contains all types of nodes. Thus, SLACC of the network in Figure 2(a) is 13. As presented in Figure 2(b), due to the disruption of node 6, the supply network presented in Figure 2(a) is divided into three connected components. Component 1 contains nodes 1, 2, 5, 8, 9, and 10. Component 2 is composed of nodes 11 and 12. Component 3 contains nodes 3, 4, 7, and 13. Among all three connected components, Component 1 and Component 3 contain all types of nodes, so they can maintain the basic function. The sizes of Component 1 and Component 3 are 6 and 4, respectively. Thus, the size of Component 1 is larger than that of Component 3. So, LACC of the network presented in Figure 2(b) is Component 1 and SLACC of it is 6.
After introducing the definition of SLACC, two robustness metricsRr and Rt are proposed to measure the tolerance of a supply network facing random and target disruptions, respectively.
Based on the definition of SLACC and random disruption model, the robustness of supply networkG against random disruptions is given as follows:(7)RrG=1V∑j=1VSLACCrjSLACC0,where j = 1, 2, …, |V| represents the times of random disruptions on the supply network G, |V| is the number of nodes in the original network G, SLACC0 represents the SLACC of original network G SLACCr, (j) represents the SLACC of network G after the jth random disruption, namely, removing the jth nodes under random disruptions, and SLACCr (j)/SLACC0 is the normalized SLACC of network G after the jth random disruption.,
In the same way, the robustness of supply networkG against target disruptions is defined as(8)RtG=1V∑j=1VSLACCtjSLACC0,where j = 1, 2, …, |V| represents the times of target disruptions on the network G, |V| is the number of nodes in the original network G, SLACC0 represents the SLACC of original network G. SLACCt (j) represents the SLACC of network G after the jth target disruption, namely, removing the jth node under target disruptions, and SLACCt (j)/SLACC0 is the normalized SLACC of network G after the jth target disruption.Figure 2
Illustration of LACC and SLACC. (a) Original supply network. (b) Supply network after the disruption of node 6.
(a)(b)


## 3.1. Supply Network Model

In this study, a supply network is modeled as a networkG = (V, E), where V=v1,v2,…vv is the node set, representing the entities in the supply network. |V| represents the total number of nodes. E is the edge set, representing product transmitting relations. E=vi,vj, where vi,vj∈E, if there is a product transmitting relation between node vi and vj.Since entities in a supply network can play various roles like manufacturers, suppliers, and retailers, node type is introduced as a node attribute to describe the specific roles nodes playing. Node type is presented asRole=rolevi, where rolevi∈type1,type2,…,typeM denotes the specific role of node vi in the supply network G and M is the total number of node types in the network.Figure1 presents an example to illustrate the modeling method. The supply network presented in Figure 1 is composed of 3 different types of entities, namely, retailers, manufacturers, and suppliers. The three types of entities are represented by green, red, and yellow nodes, respectively. Edges connecting these entities represent product transmitting relations between them. It is observed that edges exist not only between different types of nodes but also same types of nodes in the network. The main reason is that, with technological developments, the inter-entity relations can be various and complex in a supply network. Product transmitting relation can exist between different types of entities as well as same types of entities [8, 25].Figure 1
Illustration of the supply network model.


## 3.2. Robustness Evaluation

The robustness of a supply network is defined as its ability to keep the basic function and connectivity under the loss of some structures or functions due to natural and man-made disasters [8, 9, 24]. When evaluating the robustness of a supply network, two aspects need to be considered: disruption models for simulating the risk scenarios and evaluation metrics to measure the network’s ability to withstand disruptions. Thus, in this section, two commonly used disruption models, random and target disruption models, are introduced. Then, the robustness evaluation metrics corresponding to the two disruption models are also proposed.


### 3.2.1. Disruption Models

When evaluating the robustness of a supply network, most current studies consider two typical disruption models: random disruption model and target disruption model. They are corresponding to two risk scenarios: unintentional destruction and intentional attack [8, 36, 37]. Based on these previous works, the two types of disruption model are adopted in this study.Before introducing the disruption models, the following assumptions are made.Assumption 1.
The disruption of a node in a supply network is treated as the complete damage of it. That is to say, once a node is disrupted, it will lose all the functions of it and it will not recover anymore. Thus, the disruption of a node is modeled as the removal of it.Assumption 2.
The adaptive behaviour of nodes, such as making temporary connections with alternative nodes and so on, is not considered in this study.
(1) Random disruption model. Random disruptions refer to unintentional destruction, such as natural disasters (e.g., earthquakes and floods), unexpected economic events (e.g., recessions and bankruptcy), and accidents (e.g., power blackout and fire). For such disruptions, the places where disruptions descend upon are usually unpredictable. In general, random disruptions are modeled using random node removals, where each node has an equal probability to be disrupted. The procedure of simulating random disruptions can be described as follows:(a)
Ranking nodes randomly.(b)
Nodes are removed from the network progressively following the random ranking calculated in step a. When a node is removed, all of its links in the network are also removed.(c)
The process is iterated until all nodes in the network have been removed.
(2) Target Disruption Model. On the other hand, target disruptions refer to intentional attacks, like terrorist and military attacks, which are aimed at maximizing the damage to the entire supply network by targeting nodes in the network believed to be “important.” Usually, the node “importance” is measured by degree, namely, the number of edges attached to it [48]. The procedure of simulating target disruptions is listed as follows:(a)
Ranking nodes according to degree centrality in the descending order. The degree of a given nodevi is presented using the following equation:(1)ki=φi,whereφi represents the node set connected to node vi and |φi| represents the number of nodes in φi.(b)
Nodes are removed progressively following the degree-based ranking. When a node is removed, all of its links in the network are also removed.(c)
The process is iterated until all the nodes in the network have been removed.


### 3.2.2. Evaluation Metrics

Based on the two disruption models used in this study, two robustness metrics are proposed to evaluate supply networks’ tolerance of random and target disruptions, respectively.Traditionally, network robustness evaluations are mainly based on LCC. Since nodes can play heterogeneous roles in a supply network, the definition of LCC has been extended into the context of supply networks by many previous works. In this study, we will use the definition of LACC and SLACC proposed by Shi et al. to measure the performance of a supply network facing disruptions [25].Definition 1.
LCC is defined as the largest subnetwork in which any pair of nodes can be connected. The expression of LCC is presented using the following equation:(2)GccV,E=GV,E|∀vi∈V,∀vj∈V,∃path connectingviandvj,(3)GLCCV,E=GCCV,E|∀GV,E∈GccV,E,GV,E<=GCCV,E,where equation (2) denotes the connected component set, which is composed of subnetworks in which any pair of nodes can be connected and equation (3) denotes the set of LCC.Definition 2.
LACC is defined as a LCC that includes at least one node of each role type. The expression of LACC is presented using the following equation:(4)GAV,E=GccV,E|∃vi1∈V,rolevi1=type1∧⋯∧∃viM∈V,roleviM=typeM,(5)GLACCV,E=GAV,E|∀GV,E∈GAV,E,GV,E<=GAV,E,where equation (4) denotes the all role connected component set, which is composed of subnetworks, in which any pair of nodes can be connected and contain all role types and equation (5) denotes the set of LACC.
Based on the definition of LACC, SLACC of a given supply networkG is defined as the number of nodes in LACC. The expression is presented using the following equation:(6)SLACCG=GLACCV,E,where |GLACC (V,E)| represents the number of nodes in LACC.
The illustration of LACC and SLACC is presented in Figure2. Figures 2(a) and 2(b) present a supply network before disruption and after disruption, respectively. As presented in Figure 2(a), all 13 nodes form a connected component which contains all types of nodes. Thus, SLACC of the network in Figure 2(a) is 13. As presented in Figure 2(b), due to the disruption of node 6, the supply network presented in Figure 2(a) is divided into three connected components. Component 1 contains nodes 1, 2, 5, 8, 9, and 10. Component 2 is composed of nodes 11 and 12. Component 3 contains nodes 3, 4, 7, and 13. Among all three connected components, Component 1 and Component 3 contain all types of nodes, so they can maintain the basic function. The sizes of Component 1 and Component 3 are 6 and 4, respectively. Thus, the size of Component 1 is larger than that of Component 3. So, LACC of the network presented in Figure 2(b) is Component 1 and SLACC of it is 6.
After introducing the definition of SLACC, two robustness metricsRr and Rt are proposed to measure the tolerance of a supply network facing random and target disruptions, respectively.
Based on the definition of SLACC and random disruption model, the robustness of supply networkG against random disruptions is given as follows:(7)RrG=1V∑j=1VSLACCrjSLACC0,where j = 1, 2, …, |V| represents the times of random disruptions on the supply network G, |V| is the number of nodes in the original network G, SLACC0 represents the SLACC of original network G SLACCr, (j) represents the SLACC of network G after the jth random disruption, namely, removing the jth nodes under random disruptions, and SLACCr (j)/SLACC0 is the normalized SLACC of network G after the jth random disruption.,
In the same way, the robustness of supply networkG against target disruptions is defined as(8)RtG=1V∑j=1VSLACCtjSLACC0,where j = 1, 2, …, |V| represents the times of target disruptions on the network G, |V| is the number of nodes in the original network G, SLACC0 represents the SLACC of original network G. SLACCt (j) represents the SLACC of network G after the jth target disruption, namely, removing the jth node under target disruptions, and SLACCt (j)/SLACC0 is the normalized SLACC of network G after the jth target disruption.Figure 2
Illustration of LACC and SLACC. (a) Original supply network. (b) Supply network after the disruption of node 6.
(a)(b)


## 3.2.1. Disruption Models

When evaluating the robustness of a supply network, most current studies consider two typical disruption models: random disruption model and target disruption model. They are corresponding to two risk scenarios: unintentional destruction and intentional attack [8, 36, 37]. Based on these previous works, the two types of disruption model are adopted in this study.Before introducing the disruption models, the following assumptions are made.Assumption 1.
The disruption of a node in a supply network is treated as the complete damage of it. That is to say, once a node is disrupted, it will lose all the functions of it and it will not recover anymore. Thus, the disruption of a node is modeled as the removal of it.Assumption 2.
The adaptive behaviour of nodes, such as making temporary connections with alternative nodes and so on, is not considered in this study.
(1) Random disruption model. Random disruptions refer to unintentional destruction, such as natural disasters (e.g., earthquakes and floods), unexpected economic events (e.g., recessions and bankruptcy), and accidents (e.g., power blackout and fire). For such disruptions, the places where disruptions descend upon are usually unpredictable. In general, random disruptions are modeled using random node removals, where each node has an equal probability to be disrupted. The procedure of simulating random disruptions can be described as follows:(a)
Ranking nodes randomly.(b)
Nodes are removed from the network progressively following the random ranking calculated in step a. When a node is removed, all of its links in the network are also removed.(c)
The process is iterated until all nodes in the network have been removed.
(2) Target Disruption Model. On the other hand, target disruptions refer to intentional attacks, like terrorist and military attacks, which are aimed at maximizing the damage to the entire supply network by targeting nodes in the network believed to be “important.” Usually, the node “importance” is measured by degree, namely, the number of edges attached to it [48]. The procedure of simulating target disruptions is listed as follows:(a)
Ranking nodes according to degree centrality in the descending order. The degree of a given nodevi is presented using the following equation:(1)ki=φi,whereφi represents the node set connected to node vi and |φi| represents the number of nodes in φi.(b)
Nodes are removed progressively following the degree-based ranking. When a node is removed, all of its links in the network are also removed.(c)
The process is iterated until all the nodes in the network have been removed.


## 3.2.2. Evaluation Metrics

Based on the two disruption models used in this study, two robustness metrics are proposed to evaluate supply networks’ tolerance of random and target disruptions, respectively.Traditionally, network robustness evaluations are mainly based on LCC. Since nodes can play heterogeneous roles in a supply network, the definition of LCC has been extended into the context of supply networks by many previous works. In this study, we will use the definition of LACC and SLACC proposed by Shi et al. to measure the performance of a supply network facing disruptions [25].Definition 1.
LCC is defined as the largest subnetwork in which any pair of nodes can be connected. The expression of LCC is presented using the following equation:(2)GccV,E=GV,E|∀vi∈V,∀vj∈V,∃path connectingviandvj,(3)GLCCV,E=GCCV,E|∀GV,E∈GccV,E,GV,E<=GCCV,E,where equation (2) denotes the connected component set, which is composed of subnetworks in which any pair of nodes can be connected and equation (3) denotes the set of LCC.Definition 2.
LACC is defined as a LCC that includes at least one node of each role type. The expression of LACC is presented using the following equation:(4)GAV,E=GccV,E|∃vi1∈V,rolevi1=type1∧⋯∧∃viM∈V,roleviM=typeM,(5)GLACCV,E=GAV,E|∀GV,E∈GAV,E,GV,E<=GAV,E,where equation (4) denotes the all role connected component set, which is composed of subnetworks, in which any pair of nodes can be connected and contain all role types and equation (5) denotes the set of LACC.
Based on the definition of LACC, SLACC of a given supply networkG is defined as the number of nodes in LACC. The expression is presented using the following equation:(6)SLACCG=GLACCV,E,where |GLACC (V,E)| represents the number of nodes in LACC.
The illustration of LACC and SLACC is presented in Figure2. Figures 2(a) and 2(b) present a supply network before disruption and after disruption, respectively. As presented in Figure 2(a), all 13 nodes form a connected component which contains all types of nodes. Thus, SLACC of the network in Figure 2(a) is 13. As presented in Figure 2(b), due to the disruption of node 6, the supply network presented in Figure 2(a) is divided into three connected components. Component 1 contains nodes 1, 2, 5, 8, 9, and 10. Component 2 is composed of nodes 11 and 12. Component 3 contains nodes 3, 4, 7, and 13. Among all three connected components, Component 1 and Component 3 contain all types of nodes, so they can maintain the basic function. The sizes of Component 1 and Component 3 are 6 and 4, respectively. Thus, the size of Component 1 is larger than that of Component 3. So, LACC of the network presented in Figure 2(b) is Component 1 and SLACC of it is 6.
After introducing the definition of SLACC, two robustness metricsRr and Rt are proposed to measure the tolerance of a supply network facing random and target disruptions, respectively.
Based on the definition of SLACC and random disruption model, the robustness of supply networkG against random disruptions is given as follows:(7)RrG=1V∑j=1VSLACCrjSLACC0,where j = 1, 2, …, |V| represents the times of random disruptions on the supply network G, |V| is the number of nodes in the original network G, SLACC0 represents the SLACC of original network G SLACCr, (j) represents the SLACC of network G after the jth random disruption, namely, removing the jth nodes under random disruptions, and SLACCr (j)/SLACC0 is the normalized SLACC of network G after the jth random disruption.,
In the same way, the robustness of supply networkG against target disruptions is defined as(8)RtG=1V∑j=1VSLACCtjSLACC0,where j = 1, 2, …, |V| represents the times of target disruptions on the network G, |V| is the number of nodes in the original network G, SLACC0 represents the SLACC of original network G. SLACCt (j) represents the SLACC of network G after the jth target disruption, namely, removing the jth node under target disruptions, and SLACCt (j)/SLACC0 is the normalized SLACC of network G after the jth target disruption.Figure 2
Illustration of LACC and SLACC. (a) Original supply network. (b) Supply network after the disruption of node 6.
(a)(b)


## 4. Adaptive Variable Neighborhood Search-Based Supply Network Reconfiguration for Robustness Enhancement

In this section, an AVNS-based reconfiguration method is presented for robustness enhancement. Firstly, the problem description of supply network reconfiguration-based robustness enhancement is given. Then, an AVNS algorithm is proposed to solve the problem.


### 4.1. Problem Description

To enhance the robustness of a supply network, the network structure will be reconfigured by introducing a limited number of new product transmitting relations between existing entities. This is a commonly used supply network reconfiguration approach. In this study, a supply network is modeled asG = (V,E), where V and E represent entities and product transmitting relations between entities. Based on the model, two robustness evaluation metrics, Rr and Rt, are proposed to describe the tolerance of a supply network facing random and target disruptions, respectively. Thus, the network reconfiguration-based robustness enhancement of a given supply network G is a typical optimization problem, which is aimed at finding a limited subset of edges S whose addition can maximize both Rr and Rt of the reconfigured network G∪S. The problem is described as follows:(9)maxSHS,(10)s.t.S=K,(11)S∩E=∅,(12)HS=αRrG∪S+1−αRtG∪S,where S represents any possible subset of edges to be added into network G, |S| denotes the number of edges in S, K is a predefined number of edges to be added in to G, and G∪S represents the reconfigured supply network G after adding edge set S. Constrain (10) denotes the number of added edges should be equal to the predefined number. Constrain (11) denotes the added edges cannot be edges which already exist in the network. Rr (G∪S) and Rt (G∪S) denote the tolerances of reconfigured network facing random and target disruptions, respectively. α ∈ [0, 1] is a weighting parameter. If 0 ≤ α < 0.5, the network’s robustness mainly depends on its tolerance of random disruptions. If 0.5 < α ≤ 1, then the network’s robustness mainly depends on its tolerance of target disruptions. In this study, the tolerances of random and target disruptions are considered to be equally important. Thus, the value of α is set to be 0.5. In the following text, H (S) will be used as the objective function, namely, the fitness function in the proposed AVNS algorithm.


### 4.2. Adaptive Variable Neighborhood Search

Variable neighborhood search (VNS) is a type of heuristic algorithm, which is based on the idea of neighborhood change to avoid trapping in local optimums [49–51]. Due to the efficiency and effectiveness of it, it has been applied in many areas and achieved high performance. Thus, an improved VNS algorithm, namely, AVNS is proposed to solve the problem of supply network reconfiguration-based robustness enhancement. To solve the problem effectively and efficiently, an adaptive search-based solution improvement is proposed, which contains a local neighborhood search based on community closeness, a global neighborhood search and an adaptive neighborhood determination scheme.


#### 4.2.1. Solution Representation and Fitness Evaluation

In the AVNS, each possible reconfiguration solution is coded using the string coding method. A solution can be represented asS = [p1,p2,…,pK], where pi = vx,vy is the ith element of the solution, representing an edge to be added into G and K is the predefined number of edges to be added. Figure 3 presents an example to illustrate the string-based coding. In the Figure 3, the red dotted lines represent edges to be added into the network.Figure 3
Illustration of string-based solution coding.In terms of searching for the optimal reconfiguration solution, operations are performed to search for the optimal edge subset whose addition will improve both robustness metricsRr and Rt most greatly. Thus, each solution will be evaluated using a fitness value; those solutions with bigger fitness values are considered to be better ones. Thus, the fitness values are calculated using equation (12).


#### 4.2.2. General Scheme of Adaptive Variable Neighborhood Search

As presented in Algorithm1 and Figure 4, the proposed AVNS algorithm is mainly composed of a solution initialization procedure and an adaptive search-based solution improvement. The adaptive search-based solution improvement includes two neighborhood search methods and an adaptive neighborhood determination scheme. The two neighborhood search methods are community closeness-based local neighborhood search and global neighborhood search. To realize the adaptive neighborhood determination, a rating is associated to each neighborhood search, where PL and PG represent the ratings for local and global search, respectively. The rating is correlated with the possibility to perform each search method. The probability of performing local search is PL/(PL + PG), while the probability of performing global search is PG/(PL + PG). Thus, search method with a higher rating indicates a higher chance to be performed. These ratings are dynamically updated according to results encountered during the iterations. The search method leading to new optimal solutions is enhanced by increasing its rating, while the search method unable to improve solutions will be weakened by decreasing its rating.Algorithm 1:Adaptive variable neighborhood search.
Input: G = (V,E), Role, K, Ninitial, PL, PG, p1, p2,thresholdOutput: SS ⟵ Solution initialization (G, K, Ninitial)while (end condition is not met) doifPL/(PL + PG) > a random number δ ∈ (0, 1)S∗ ⟵ Community closeness-based local neighbourhood search (G, S)if fitness (S∗) > fitness (S)S ⟵ S∗;PL = PL − p1;elsePL = PL − p2;end ififPL < ThresholdPL = Thresholdend ifelseS∗ ⟵ Global neighborhood search (G, S)if fitness (S∗) > fitness (S)S ⟵S∗;PG = PG + p1elsePG = PG + p2;end ififPG < ThresholdPG = Threshold;end ifend ifend whileReturnSFigure 4
Flowchart of the proposed AVNS.


#### 4.2.3. Solution Initialization

The quality of an initial solution not only affects the accuracy of an algorithm but also the converging speed. An initial solution with high quality is vitally important. Thus, a random search algorithm is used to find an initial solution with high quality. Firstly, the random solution generation procedure allows solutions in the entire solution space to be obtained. Subsequently, best solution is selected from the randomly generated solutions. The solution initialization procedure is presented in Algorithm2.Algorithm 2:Solution initialization.
Input: G = (V, E), Role, K and NinitialOutput: SPOP = ∅;fori = 1: NinitialSi ⟵ Generate a solution randomly;ifSi is different from any solutions in POP;AddSi into POP;elseModifySi and add it into POP;end ifend forevaluate solutionSi according to fitness function;//Identify the best solutionSb in the POP;b = argmaxi∈(1, 2,…,Ninitial) fitness (Si);S ⟵ Sb;returnS


#### 4.2.4. Community Closeness-Based Local Neighborhood Search

To ensure an effective and efficient improvement of solutions, a local neighborhood search method based on community closeness is proposed in this study. As presented in Algorithm3, the proposed community closeness-based local neighborhood search is composed of three steps: community closeness-based neighborhood determination, degree weighting-based candidate identification, and random swap strategyAlgorithm 3:Community closeness-based local neighborhood search.
Input: G = (V, E), S and KOutput: S∗Neighborhood ⟵ Community closeness-based neighborhood determination (G, S);candidate ⟵ Degree weighting-based candidate search (G, S, Neighborhood);//Random swapGenerate a random integer c ∈ {1, 2,…,K};S∗ ⟵ S;S∗⟵S∗ − {pc};S∗ ⟵ S∗∪candidate;returnS∗(1) Community Closeness-Based Local Neighborhood Determination. Neighborhood refers to the solution space for candidate solutions. The performance of a local search highly depends on its neighborhood structure. Thus, a community closeness-based neighborhood determination is designed in this study, which is both smaller in size and more focused in terms of the optimization objective. In this study, performance of a supply network is measured by SLACC, which is also a network connectivity metric. Community in a network refers to groups of nodes within which connections are dense, but between which connections are sparser. Intuitively, adding edges between two unconnected communities will help to increase the connectivity. It may benefit the enhancement of supply network robustness. As a result, when swapping an edge vx,vy ∈ S with a candidate edge vx1,vy1, it may be more preferable to consider an edge connecting two unconnected communities. Based on such consideration, a local neighborhood determination method based on community closeness is proposed. As presented in Algorithm 4, the method is composed of the following steps:(a)
Community detection forG∗ = G∪S. Due to the accuracy and efficiency, Louvin algorithm is adopted in this study for community detection. The details of the algorithm are presented in [52].(b)
Calculate closeness for each pair of community. Closeness of a pair of communities is defined as the number of edges connecting the pair of communities.(c)
Based on the closeness of community pairs, community pair with minimal closeness is selected.(d)
Based on the community pair with minimal value of closeness, the neighborhood for generating candidate solutions is determinedAlgorithm 4:Community closeness-based neighborhood determination.
Input: G=(V, E), K and SOutput: NeighborhoodG∗ = G∪S;//Community detection{C1,C2,…,Cn} ⟵ Louvin-based community detection (G∗)//Calculate closeness for each pair of communitiesfor each pair (Ce, Cf) doCloseness (Ce, Cf) = 0;for each node vx ∈ Cedofor each node vy ∈ Cfdoif (vx, vy) ∈ E∪SdoCloseness (Ce, Cf) = Closeness (Ce, Cf) + 1;end ifend forend forend for//Neighborhood determination(φ1, φ2) ⟵ find the pair of community with the minimal closeness;Neighborhood ⟵ ∅for each vx ∈ φ1dofor each vy ∈ φ2doif (vx, vy) ∉ E∪SdoNeighborhood ⟵ Neighborhood∪(vx,vy);end ifend forend forreturnNeighborhood(2) Degree Weighting-Based Candidate Identification. After determination of the community pair with minimal closeness, a connection will be built between them to increase network connectivity. Previous studies indicate that low degree-based edge addition can increase network robustness more effectively [53]. Thus, adding edges between less connected nodes is considered to be more satisfactory. The procedure of degree weighting-based candidate identification is presented in Algorithm 5.Algorithm 5:Desgree weighting-based candidate identification.
Input: G = (V, E), S and NeighborhoodOutput: candidateG∗ = G∪S;for each pair (vx, vy) ∈ Neighborhooddod (vx) ⟵ Number of nodes connected to vx in G∗;d (vy)⟵Number of nodes connected to vy in G∗;D_score (vx, vy) ⟵ d (vx) × d (vy);end forcandidate ⟵ Identify the node pair (vx1, vy1) with the minimal value of D_score;returncandidate


#### 4.2.5. Global Neighborhood Search

Solution improvement based on a single neighborhood search could easily lead to local optimums. To avoid trapping in local optimums, global neighborhood search is also adopted in this study. The procedure of global neighborhood search is presented in Algorithm6.Algorithm 6:Global neighborhood search.
Input: G = (V,E),Output: S∗(vx,vy) ⟵ Select a pair nodes from V × V − (E∪S) randomly;whilevx == vydo(vx,vy) ⟵ Select a pair nodes from V × V − (E∪S) randomly;end whileGenerate a random integerc ∈ {1, 2, …, K);S∗ ⟵ S;S∗ ⟵ S∗−pc;S∗ ⟵ S∗∪vx,vyreturnS∗


### 4.3. Computational Complexity of AVNS

To analyze the computational complexity of the proposed AVNS, we consider the main steps in one generation in the main loop of Algorithm1.As displayed in Algorithm1, each generation of AVNS performs four subroutines: determination of search method, neighborhood search, optimal solution update, and rating update. The determination of search method takes time O (1). In the neighborhood search procedure, the time complexity of global neighborhood is O [|V|3]. The time complexity of community closeness-based local neighborhood search procedure is O [2 (|V|+|E|) + K + (n)∗(n − 1)/2 + |V|3], where n denotes the current community number determined by Louvin algorithm. Thus, the time complexity of neighborhood search is bounded by O [2 (|V| + |E|) + K + (n)∗(n − 1)/2 + |V|3]. The optimal solution update and rating update take time O (1). Hence, for each generation, the total complexity of AVNS is O [2 (|V| + |E|) + K + (n)∗(n − 1)/2 + |V|3].


## 4.1. Problem Description

To enhance the robustness of a supply network, the network structure will be reconfigured by introducing a limited number of new product transmitting relations between existing entities. This is a commonly used supply network reconfiguration approach. In this study, a supply network is modeled asG = (V,E), where V and E represent entities and product transmitting relations between entities. Based on the model, two robustness evaluation metrics, Rr and Rt, are proposed to describe the tolerance of a supply network facing random and target disruptions, respectively. Thus, the network reconfiguration-based robustness enhancement of a given supply network G is a typical optimization problem, which is aimed at finding a limited subset of edges S whose addition can maximize both Rr and Rt of the reconfigured network G∪S. The problem is described as follows:(9)maxSHS,(10)s.t.S=K,(11)S∩E=∅,(12)HS=αRrG∪S+1−αRtG∪S,where S represents any possible subset of edges to be added into network G, |S| denotes the number of edges in S, K is a predefined number of edges to be added in to G, and G∪S represents the reconfigured supply network G after adding edge set S. Constrain (10) denotes the number of added edges should be equal to the predefined number. Constrain (11) denotes the added edges cannot be edges which already exist in the network. Rr (G∪S) and Rt (G∪S) denote the tolerances of reconfigured network facing random and target disruptions, respectively. α ∈ [0, 1] is a weighting parameter. If 0 ≤ α < 0.5, the network’s robustness mainly depends on its tolerance of random disruptions. If 0.5 < α ≤ 1, then the network’s robustness mainly depends on its tolerance of target disruptions. In this study, the tolerances of random and target disruptions are considered to be equally important. Thus, the value of α is set to be 0.5. In the following text, H (S) will be used as the objective function, namely, the fitness function in the proposed AVNS algorithm.


## 4.2. Adaptive Variable Neighborhood Search

Variable neighborhood search (VNS) is a type of heuristic algorithm, which is based on the idea of neighborhood change to avoid trapping in local optimums [49–51]. Due to the efficiency and effectiveness of it, it has been applied in many areas and achieved high performance. Thus, an improved VNS algorithm, namely, AVNS is proposed to solve the problem of supply network reconfiguration-based robustness enhancement. To solve the problem effectively and efficiently, an adaptive search-based solution improvement is proposed, which contains a local neighborhood search based on community closeness, a global neighborhood search and an adaptive neighborhood determination scheme.


### 4.2.1. Solution Representation and Fitness Evaluation

In the AVNS, each possible reconfiguration solution is coded using the string coding method. A solution can be represented asS = [p1,p2,…,pK], where pi = vx,vy is the ith element of the solution, representing an edge to be added into G and K is the predefined number of edges to be added. Figure 3 presents an example to illustrate the string-based coding. In the Figure 3, the red dotted lines represent edges to be added into the network.Figure 3
Illustration of string-based solution coding.In terms of searching for the optimal reconfiguration solution, operations are performed to search for the optimal edge subset whose addition will improve both robustness metricsRr and Rt most greatly. Thus, each solution will be evaluated using a fitness value; those solutions with bigger fitness values are considered to be better ones. Thus, the fitness values are calculated using equation (12).


### 4.2.2. General Scheme of Adaptive Variable Neighborhood Search

As presented in Algorithm1 and Figure 4, the proposed AVNS algorithm is mainly composed of a solution initialization procedure and an adaptive search-based solution improvement. The adaptive search-based solution improvement includes two neighborhood search methods and an adaptive neighborhood determination scheme. The two neighborhood search methods are community closeness-based local neighborhood search and global neighborhood search. To realize the adaptive neighborhood determination, a rating is associated to each neighborhood search, where PL and PG represent the ratings for local and global search, respectively. The rating is correlated with the possibility to perform each search method. The probability of performing local search is PL/(PL + PG), while the probability of performing global search is PG/(PL + PG). Thus, search method with a higher rating indicates a higher chance to be performed. These ratings are dynamically updated according to results encountered during the iterations. The search method leading to new optimal solutions is enhanced by increasing its rating, while the search method unable to improve solutions will be weakened by decreasing its rating.Algorithm 1:Adaptive variable neighborhood search.
Input: G = (V,E), Role, K, Ninitial, PL, PG, p1, p2,thresholdOutput: SS ⟵ Solution initialization (G, K, Ninitial)while (end condition is not met) doifPL/(PL + PG) > a random number δ ∈ (0, 1)S∗ ⟵ Community closeness-based local neighbourhood search (G, S)if fitness (S∗) > fitness (S)S ⟵ S∗;PL = PL − p1;elsePL = PL − p2;end ififPL < ThresholdPL = Thresholdend ifelseS∗ ⟵ Global neighborhood search (G, S)if fitness (S∗) > fitness (S)S ⟵S∗;PG = PG + p1elsePG = PG + p2;end ififPG < ThresholdPG = Threshold;end ifend ifend whileReturnSFigure 4
Flowchart of the proposed AVNS.


### 4.2.3. Solution Initialization

The quality of an initial solution not only affects the accuracy of an algorithm but also the converging speed. An initial solution with high quality is vitally important. Thus, a random search algorithm is used to find an initial solution with high quality. Firstly, the random solution generation procedure allows solutions in the entire solution space to be obtained. Subsequently, best solution is selected from the randomly generated solutions. The solution initialization procedure is presented in Algorithm2.Algorithm 2:Solution initialization.
Input: G = (V, E), Role, K and NinitialOutput: SPOP = ∅;fori = 1: NinitialSi ⟵ Generate a solution randomly;ifSi is different from any solutions in POP;AddSi into POP;elseModifySi and add it into POP;end ifend forevaluate solutionSi according to fitness function;//Identify the best solutionSb in the POP;b = argmaxi∈(1, 2,…,Ninitial) fitness (Si);S ⟵ Sb;returnS


### 4.2.4. Community Closeness-Based Local Neighborhood Search

To ensure an effective and efficient improvement of solutions, a local neighborhood search method based on community closeness is proposed in this study. As presented in Algorithm3, the proposed community closeness-based local neighborhood search is composed of three steps: community closeness-based neighborhood determination, degree weighting-based candidate identification, and random swap strategyAlgorithm 3:Community closeness-based local neighborhood search.
Input: G = (V, E), S and KOutput: S∗Neighborhood ⟵ Community closeness-based neighborhood determination (G, S);candidate ⟵ Degree weighting-based candidate search (G, S, Neighborhood);//Random swapGenerate a random integer c ∈ {1, 2,…,K};S∗ ⟵ S;S∗⟵S∗ − {pc};S∗ ⟵ S∗∪candidate;returnS∗(1) Community Closeness-Based Local Neighborhood Determination. Neighborhood refers to the solution space for candidate solutions. The performance of a local search highly depends on its neighborhood structure. Thus, a community closeness-based neighborhood determination is designed in this study, which is both smaller in size and more focused in terms of the optimization objective. In this study, performance of a supply network is measured by SLACC, which is also a network connectivity metric. Community in a network refers to groups of nodes within which connections are dense, but between which connections are sparser. Intuitively, adding edges between two unconnected communities will help to increase the connectivity. It may benefit the enhancement of supply network robustness. As a result, when swapping an edge vx,vy ∈ S with a candidate edge vx1,vy1, it may be more preferable to consider an edge connecting two unconnected communities. Based on such consideration, a local neighborhood determination method based on community closeness is proposed. As presented in Algorithm 4, the method is composed of the following steps:(a)
Community detection forG∗ = G∪S. Due to the accuracy and efficiency, Louvin algorithm is adopted in this study for community detection. The details of the algorithm are presented in [52].(b)
Calculate closeness for each pair of community. Closeness of a pair of communities is defined as the number of edges connecting the pair of communities.(c)
Based on the closeness of community pairs, community pair with minimal closeness is selected.(d)
Based on the community pair with minimal value of closeness, the neighborhood for generating candidate solutions is determinedAlgorithm 4:Community closeness-based neighborhood determination.
Input: G=(V, E), K and SOutput: NeighborhoodG∗ = G∪S;//Community detection{C1,C2,…,Cn} ⟵ Louvin-based community detection (G∗)//Calculate closeness for each pair of communitiesfor each pair (Ce, Cf) doCloseness (Ce, Cf) = 0;for each node vx ∈ Cedofor each node vy ∈ Cfdoif (vx, vy) ∈ E∪SdoCloseness (Ce, Cf) = Closeness (Ce, Cf) + 1;end ifend forend forend for//Neighborhood determination(φ1, φ2) ⟵ find the pair of community with the minimal closeness;Neighborhood ⟵ ∅for each vx ∈ φ1dofor each vy ∈ φ2doif (vx, vy) ∉ E∪SdoNeighborhood ⟵ Neighborhood∪(vx,vy);end ifend forend forreturnNeighborhood(2) Degree Weighting-Based Candidate Identification. After determination of the community pair with minimal closeness, a connection will be built between them to increase network connectivity. Previous studies indicate that low degree-based edge addition can increase network robustness more effectively [53]. Thus, adding edges between less connected nodes is considered to be more satisfactory. The procedure of degree weighting-based candidate identification is presented in Algorithm 5.Algorithm 5:Desgree weighting-based candidate identification.
Input: G = (V, E), S and NeighborhoodOutput: candidateG∗ = G∪S;for each pair (vx, vy) ∈ Neighborhooddod (vx) ⟵ Number of nodes connected to vx in G∗;d (vy)⟵Number of nodes connected to vy in G∗;D_score (vx, vy) ⟵ d (vx) × d (vy);end forcandidate ⟵ Identify the node pair (vx1, vy1) with the minimal value of D_score;returncandidate


### 4.2.5. Global Neighborhood Search

Solution improvement based on a single neighborhood search could easily lead to local optimums. To avoid trapping in local optimums, global neighborhood search is also adopted in this study. The procedure of global neighborhood search is presented in Algorithm6.Algorithm 6:Global neighborhood search.
Input: G = (V,E),Output: S∗(vx,vy) ⟵ Select a pair nodes from V × V − (E∪S) randomly;whilevx == vydo(vx,vy) ⟵ Select a pair nodes from V × V − (E∪S) randomly;end whileGenerate a random integerc ∈ {1, 2, …, K);S∗ ⟵ S;S∗ ⟵ S∗−pc;S∗ ⟵ S∗∪vx,vyreturnS∗


## 4.2.1. Solution Representation and Fitness Evaluation

In the AVNS, each possible reconfiguration solution is coded using the string coding method. A solution can be represented asS = [p1,p2,…,pK], where pi = vx,vy is the ith element of the solution, representing an edge to be added into G and K is the predefined number of edges to be added. Figure 3 presents an example to illustrate the string-based coding. In the Figure 3, the red dotted lines represent edges to be added into the network.Figure 3
Illustration of string-based solution coding.In terms of searching for the optimal reconfiguration solution, operations are performed to search for the optimal edge subset whose addition will improve both robustness metricsRr and Rt most greatly. Thus, each solution will be evaluated using a fitness value; those solutions with bigger fitness values are considered to be better ones. Thus, the fitness values are calculated using equation (12).


## 4.2.2. General Scheme of Adaptive Variable Neighborhood Search

As presented in Algorithm1 and Figure 4, the proposed AVNS algorithm is mainly composed of a solution initialization procedure and an adaptive search-based solution improvement. The adaptive search-based solution improvement includes two neighborhood search methods and an adaptive neighborhood determination scheme. The two neighborhood search methods are community closeness-based local neighborhood search and global neighborhood search. To realize the adaptive neighborhood determination, a rating is associated to each neighborhood search, where PL and PG represent the ratings for local and global search, respectively. The rating is correlated with the possibility to perform each search method. The probability of performing local search is PL/(PL + PG), while the probability of performing global search is PG/(PL + PG). Thus, search method with a higher rating indicates a higher chance to be performed. These ratings are dynamically updated according to results encountered during the iterations. The search method leading to new optimal solutions is enhanced by increasing its rating, while the search method unable to improve solutions will be weakened by decreasing its rating.Algorithm 1:Adaptive variable neighborhood search.
Input: G = (V,E), Role, K, Ninitial, PL, PG, p1, p2,thresholdOutput: SS ⟵ Solution initialization (G, K, Ninitial)while (end condition is not met) doifPL/(PL + PG) > a random number δ ∈ (0, 1)S∗ ⟵ Community closeness-based local neighbourhood search (G, S)if fitness (S∗) > fitness (S)S ⟵ S∗;PL = PL − p1;elsePL = PL − p2;end ififPL < ThresholdPL = Thresholdend ifelseS∗ ⟵ Global neighborhood search (G, S)if fitness (S∗) > fitness (S)S ⟵S∗;PG = PG + p1elsePG = PG + p2;end ififPG < ThresholdPG = Threshold;end ifend ifend whileReturnSFigure 4
Flowchart of the proposed AVNS.


## 4.2.3. Solution Initialization

The quality of an initial solution not only affects the accuracy of an algorithm but also the converging speed. An initial solution with high quality is vitally important. Thus, a random search algorithm is used to find an initial solution with high quality. Firstly, the random solution generation procedure allows solutions in the entire solution space to be obtained. Subsequently, best solution is selected from the randomly generated solutions. The solution initialization procedure is presented in Algorithm2.Algorithm 2:Solution initialization.
Input: G = (V, E), Role, K and NinitialOutput: SPOP = ∅;fori = 1: NinitialSi ⟵ Generate a solution randomly;ifSi is different from any solutions in POP;AddSi into POP;elseModifySi and add it into POP;end ifend forevaluate solutionSi according to fitness function;//Identify the best solutionSb in the POP;b = argmaxi∈(1, 2,…,Ninitial) fitness (Si);S ⟵ Sb;returnS


## 4.2.4. Community Closeness-Based Local Neighborhood Search

To ensure an effective and efficient improvement of solutions, a local neighborhood search method based on community closeness is proposed in this study. As presented in Algorithm3, the proposed community closeness-based local neighborhood search is composed of three steps: community closeness-based neighborhood determination, degree weighting-based candidate identification, and random swap strategyAlgorithm 3:Community closeness-based local neighborhood search.
Input: G = (V, E), S and KOutput: S∗Neighborhood ⟵ Community closeness-based neighborhood determination (G, S);candidate ⟵ Degree weighting-based candidate search (G, S, Neighborhood);//Random swapGenerate a random integer c ∈ {1, 2,…,K};S∗ ⟵ S;S∗⟵S∗ − {pc};S∗ ⟵ S∗∪candidate;returnS∗(1) Community Closeness-Based Local Neighborhood Determination. Neighborhood refers to the solution space for candidate solutions. The performance of a local search highly depends on its neighborhood structure. Thus, a community closeness-based neighborhood determination is designed in this study, which is both smaller in size and more focused in terms of the optimization objective. In this study, performance of a supply network is measured by SLACC, which is also a network connectivity metric. Community in a network refers to groups of nodes within which connections are dense, but between which connections are sparser. Intuitively, adding edges between two unconnected communities will help to increase the connectivity. It may benefit the enhancement of supply network robustness. As a result, when swapping an edge vx,vy ∈ S with a candidate edge vx1,vy1, it may be more preferable to consider an edge connecting two unconnected communities. Based on such consideration, a local neighborhood determination method based on community closeness is proposed. As presented in Algorithm 4, the method is composed of the following steps:(a)
Community detection forG∗ = G∪S. Due to the accuracy and efficiency, Louvin algorithm is adopted in this study for community detection. The details of the algorithm are presented in [52].(b)
Calculate closeness for each pair of community. Closeness of a pair of communities is defined as the number of edges connecting the pair of communities.(c)
Based on the closeness of community pairs, community pair with minimal closeness is selected.(d)
Based on the community pair with minimal value of closeness, the neighborhood for generating candidate solutions is determinedAlgorithm 4:Community closeness-based neighborhood determination.
Input: G=(V, E), K and SOutput: NeighborhoodG∗ = G∪S;//Community detection{C1,C2,…,Cn} ⟵ Louvin-based community detection (G∗)//Calculate closeness for each pair of communitiesfor each pair (Ce, Cf) doCloseness (Ce, Cf) = 0;for each node vx ∈ Cedofor each node vy ∈ Cfdoif (vx, vy) ∈ E∪SdoCloseness (Ce, Cf) = Closeness (Ce, Cf) + 1;end ifend forend forend for//Neighborhood determination(φ1, φ2) ⟵ find the pair of community with the minimal closeness;Neighborhood ⟵ ∅for each vx ∈ φ1dofor each vy ∈ φ2doif (vx, vy) ∉ E∪SdoNeighborhood ⟵ Neighborhood∪(vx,vy);end ifend forend forreturnNeighborhood(2) Degree Weighting-Based Candidate Identification. After determination of the community pair with minimal closeness, a connection will be built between them to increase network connectivity. Previous studies indicate that low degree-based edge addition can increase network robustness more effectively [53]. Thus, adding edges between less connected nodes is considered to be more satisfactory. The procedure of degree weighting-based candidate identification is presented in Algorithm 5.Algorithm 5:Desgree weighting-based candidate identification.
Input: G = (V, E), S and NeighborhoodOutput: candidateG∗ = G∪S;for each pair (vx, vy) ∈ Neighborhooddod (vx) ⟵ Number of nodes connected to vx in G∗;d (vy)⟵Number of nodes connected to vy in G∗;D_score (vx, vy) ⟵ d (vx) × d (vy);end forcandidate ⟵ Identify the node pair (vx1, vy1) with the minimal value of D_score;returncandidate


## 4.2.5. Global Neighborhood Search

Solution improvement based on a single neighborhood search could easily lead to local optimums. To avoid trapping in local optimums, global neighborhood search is also adopted in this study. The procedure of global neighborhood search is presented in Algorithm6.Algorithm 6:Global neighborhood search.
Input: G = (V,E),Output: S∗(vx,vy) ⟵ Select a pair nodes from V × V − (E∪S) randomly;whilevx == vydo(vx,vy) ⟵ Select a pair nodes from V × V − (E∪S) randomly;end whileGenerate a random integerc ∈ {1, 2, …, K);S∗ ⟵ S;S∗ ⟵ S∗−pc;S∗ ⟵ S∗∪vx,vyreturnS∗


## 4.3. Computational Complexity of AVNS

To analyze the computational complexity of the proposed AVNS, we consider the main steps in one generation in the main loop of Algorithm1.As displayed in Algorithm1, each generation of AVNS performs four subroutines: determination of search method, neighborhood search, optimal solution update, and rating update. The determination of search method takes time O (1). In the neighborhood search procedure, the time complexity of global neighborhood is O [|V|3]. The time complexity of community closeness-based local neighborhood search procedure is O [2 (|V|+|E|) + K + (n)∗(n − 1)/2 + |V|3], where n denotes the current community number determined by Louvin algorithm. Thus, the time complexity of neighborhood search is bounded by O [2 (|V| + |E|) + K + (n)∗(n − 1)/2 + |V|3]. The optimal solution update and rating update take time O (1). Hence, for each generation, the total complexity of AVNS is O [2 (|V| + |E|) + K + (n)∗(n − 1)/2 + |V|3].


## 5. Case Study

To verify the effectiveness of proposed AVNS-based supply network reconfiguration method, a case study based on three real-life supply networks is carried out. Firstly, the general characteristics of empirical supply networks are analyzed. Then, comparative experiments are performed based on the supply networks.


### 5.1. Three Real-Life Supply Networks

Three real-life supply networks used in this study, Chain 14, Chain 21, and Chain 25 are from an existing set of real-life cases [54]. Chain 14 describes a logistic supply network. Chain 21 presents a supply network of toilet preparations. Chain 25 is a supply network of farm machinery and equipment. The general characters of the three supply networks are presented in Table 1. All of them are composed of multiple types of entities, and the number of each type is varied. For example, in the Chain 14, the number of distributors is only 5, while the number of retailers is 66. Since the degree distribution of a supply network has been considered as a main factor affecting its robustness, the degree distributions of these networks are analyzed. It is found that all degree distributions can be fitted by truncated power-law [55]. The observed distributions and fitting curves are presented in Figure 5. Such character indicates that in these real-life supply networks, only a few nodes are intensively connected, while many others only have a few number of connections. According to the previous studies [8, 36], such a heterogeneous supply network can be robust against random disruptions but is vulnerable when entities with high degrees are damaged. In addition, the average degree [48] and H metric [56] of each network are also analyzed. The average degree can reflect the density of networks; the expression of it is presented by equation (13). The H metric is used to define the structural heterogeneity in a network; the definition of it is presented by equation (14). As presented in Table 1, Chain 25 is the most dense and heterogeneous network. Comparing with Chain 21 and Chain 25, Chain 14 is sparser and less heterogeneous:(13)k=1N∑iVki,where |V| is denotes the total number of nodes in network and ki is the degree value of node vi:(14)H=k2k2.where 〈k〉 denotes the average degree of a network, H reflects the level of the structural heterogeneity in a network, and the larger H, the more heterogeneous the network exhibits. From the definition, it is obvious that, in a homogeneous network, H is equal to one.Table 1
Basic characters of the three real-life supply networks.
Network nameNumber of each type of nodesTotal number of nodesTotal number of edges〈k〉HDistributorManufacturerSupplierRetailerTransporterChain 1459—66361161192.0521.983Chain 2117597634—1863593.8602.158Chain 253114294142—4098534.1714.653Figure 5
Degree distributions of real-life supply networks. (a) Chain 14. (b) Chain 21. (c) Chain 25.
(a)(b)(c)


### 5.2. Evaluation of AVNS-Based Supply Network Reconfiguration Method

To verify the effectiveness of AVNS-based supply network reconfiguration method, comparison with other edge addition-based network reconfiguration methods is made, specifically low degree-based reconfiguration method (LD) [53], low betweenness-based reconfiguration method (LB) [57], and simulated anneal-based reconfiguration method (SA) [58].The performances of AVNS-based and SA-based method can be influenced by several important parameters. In this study, the parameters of AVNS are set as follows: termination condition is 250 generations,Ninitial = 50, PL = 0.7, PG = 0.3, p1 = 0.1, p2 = 0.01, and Threshold = 0.1. The parameters of SA are set as follows: initial temperature T = 100, iteration time n = 5, cooling factor θ = 0.95, and low temperature T0 = 0.01. These parameters are set based on the trial-and-error method, which has been widely used to select the parameter values for heuristic algorithms in many previous works [59].Considering the number of added edges may affect the performance of reconfiguration methods, experiments based on the different fraction of added edges were performed. Fraction of added edge (fa) is defined as the fraction of the number of edges of original network before edge addition. The expression of fa is presented using equation (15). To achieve statistically significant results, each experiment was repeated 20 times. The final experimental results are calculated based on the 20 independent experiments. All experiments were performed using MATLAB R2014a and run on a PC equipped with an Intel Core i7 and 16 GB of memory, running Windows 7.(15)fa=SE,where E denote the edges in the original network, S represents the added edges, and |E| and |S| represent the number of edges in set E and S, respectively.


#### 5.2.1. Experimental Results Based on Chain 14

Figures6 and 7 illustrate the robustness of Chain 14 and the reconfigured ones facing random disruptions and target disruptions, respectively. Figures 6(a)–6(c) show the responses of five supply networks facing random disruptions, including original Chain 14 and four reconfigured ones, under fa = 5%, fa = 10%, and fa = 15%, respectively. In Figures 6(a)–6(c), the horizontal axes denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Similar to Figure 6, Figures 7(a)–7(c) show the responses of five supply networks facing target disruptions, including original Chain 14 and four reconfigured ones, under fa = 5%, fa = 10%, and fa = 15%, respectively. For presenting a quantitative comparison, Table 2 summarizes the average values, the best values, and the worst values of Rr and Rt of the 20 independent experiments based on Chain 14.Figure 6
Responses of chain 14 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 7
Responses of chain 14 and reconfigured ones facing target disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 2
Robustness comparison of chain 14 and reconfigured ones.
fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.26230.34650.15030.01350.01680.01145LD0.27140.35660.15350.01850.02130.0158LB0.27720.35020.16530.02990.03570.0245AVNS0.28520.35870.17350.04790.05440.0385SA0.27940.35840.16150.03320.03510.031110LD0.28540.37450.17680.03700.04120.0256LB0.28890.38770.16440.03920.04050.0335AVNS0.30490.37490.17930.06030.06120.0514SA0.29860.37590.18170.04770.04870.039215LD0.29810.37320.21110.04440.04870.0337LB0.29630.37980.20550.04250.04450.0372AVNS0.31690.37690.24530.06350.06450.0534SA0.30700.37040.24100.05790.06080.0518Firstly, in both Figures6 and 7, the performances of all networks decrease when nodes are removed sequentially from the networks. It is also observed that a higher fraction of the added edge leads to a better performance for all reconfiguration methods. Besides, by comparing Figures 6 with 7, it is found that all networks are more vulnerable to target disruptions. For example, In Figure 6(a), when 15% nodes are disrupted under random disruptions, the function of original Chain 14 is also well preserved as the majority of remaining nodes are still connected to form a functional component. As presented in Figure 7(a), the value of normalized SLACC becomes 0, when less than 15% nodes are disrupted under target disruptions. By comparing the performances of different reconfiguration methods, it is observed that the networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table2, the average values and the best values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for the worst values of Rr, only when fa = 10%, the performance of the proposed AVNS-based method is slightly worse than SA-based method. Except for the instance under fa = 10%, the AVNS-based method also achieves the best performance. As for Rt, the proposed AVNS-based method achieves the best performance with respect to all of the three indicators. Such results are consistent with Figures 6 and 7.


#### 5.2.2. Experimental Results Based on Chain 21

Figures8 and 9 present the robustness of Chain 21 and the reconfigured ones facing random disruptions and target disruptions, respectively. Similar to Figures 6 and 7, in all the figures of Figures 8 and 9, the horizontal axes denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Table 3 also summarizes the average values, the best values, and the worst values of both Rr and Rt of the 20 independent experiments based on Chain 21.Figure 8
Response of chain 21 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 9
Response of chain 21 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 3
Robustness comparison of chain 21 and reconfigured ones.
Fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.34760.39490.31650.09800.10240.09195LD0.34910.38030.30600.16520.17410.1558LB0.35700.40350.30710.16830.17660.1518AVNS0.36110.39930.32270.21790.22550.2119SA0.35590.39290.30210.16940.17520.161910LD0.36520.40590.30150.18810.19340.1799LB0.36740.39970.30940.18330.18620.1779AVNS0.37380.41840.32200.25180.25900.2423SA0.35370.40930.30100.18790.19390.181115LD0.38190.41460.34900.20340.20760.1980LB0.37920.41350.32520.19720.20350.1903AVNS0.38900.41530.35830.27840.29220.2685SA0.37490.40790.34440.21770.22310.2112As presented in Figures8 and 9, it is observed that Chain 21 is also vulnerable to target disruptions and exhibits much stronger tolerance to random disruptions. It is also noticed that Chain 21 is more robust than Chain 14 facing both random and target disruptions. For example, when the proportion of random disrupted nodes is 20%, the normalized SLACC of Chain 14 is less than 0.5, while the normalized SLACC of Chain 21 is almost 0.7. With respect to target disruptions, when the proportion of disrupted nodes in target disruptions is less than 15%, Chain 14 loses all functional components, while the functional components of Chain 21 still remain until the proportion of target disrupted nodes reaches 35%. The main reason of such difference can be deduced that Chain 21 is denser than Chain14. By comparing the performance of different reconfiguration methods, it is also observed that networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table3, the average values, the best values, and the worst values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for Rt, the proposed AVNS-based method also achieves the best performance in all of the instances with respect to all of the three indicators. The results presented in Table 3 are also consistent with Figures 8 and 9.


#### 5.2.3. Experimental Results Based on Chain 25

Figures10 and 11 also present the robustness of Chain 25 and the reconfigured ones facing random disruptions and target disruptions, respectively. In all the figures of Figures 10 and 11, the horizontal axes also denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Table 4 also summarizes the average values, best values, and worst values of Rr and Rt of the 20 independent experiments based on Chain 25.Figure 10
Response of chain 25 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 11
Response of chain 25 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 4
Robustness comparison of chain 25 and reconfigured ones.
Fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.36220.42520.27400.07170.07340.06955LD0.37430.43400.29540.09420.09770.0913LB0.37610.43180.29520.09300.09530.0912AVNS0.37880.43440.30140.14060.14440.1371SA0.37410.43430.29310.09630.09800.094610LD0.39300.43020.32510.11210.11470.1096LB0.39540.43010.32900.11550.11790.1130AVNS0.39770.43050.35630.18260.18670.1788SA0.39230.41980.33140.12030.12280.118615LD0.40570.44940.32510.15210.15630.1476LB0.40560.44880.33240.14780.15090.1443AVNS0.41370.45310.36460.20790.21580.2024SA0.40320.44900.34580.13280.13450.1308As presented in Figures10 and 11, Chain 25 is also vulnerable to target disruptions and exhibits much stronger tolerance to random disruptions. It is also noticed that Chain 25 is more robust than Chain 14 facing both random and target disruptions. The main reason of such difference can be deduced that Chain 25 is much denser than Chain14. It can also be observed from Table 4 that Chain 25 is slightly robust than Chain 21 facing random disruptions. When facing target disruptions, Chain 25 is more vulnerable than Chain 21. Chain 25 is denser than Chain 21, which may enhance the robustness of it facing random disruptions. However, the stronger degree heterogeneity of it also weakens the robustness of it facing target disruptions. It is also observed from Figures 10 and 11 that networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table4, the average values, the best values, and the worst values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for Rt, the proposed AVNS-based method also achieves the best performance in all of the instances with respect to all of the three indicators. The results presented in Table 4 are also consistent with Figures 10 and 11.


#### 5.2.4. Verification for Adaptive Search-Based Solution Improvement

To validate the effectiveness of proposed adaptive search-based solution improvement, a comparative experiment is also performed to compare the proposed AVNS with three alternative algorithms, GNS, LNS, and GNS + LNS. As for GNS and LNS, the adaptive search-based solution improvement is replaced by global search and community closeness-based local neighborhood search, respectively. In GNS + LNS, the adaptive neighborhood determination scheme in the solution improvement procedure is replaced by a randomized neighborhood selection, which is commonly used in VNS. Experiments were performed on 3 representative instances, namely, add 5% edges for Chain 14, Chain 21, and Chain 25, respectively. We ran each algorithm 10 times on each instance within a time limitTmax = 1800 seconds.The experimental results are presented in Figure12 and Table 5. The average fitness curves of AVNS, GNS, LNS, and GNS + LNS under fa = 5% for Chain 14, Chain 21, and Chain 25 are presented in Figures 12(a)–12(c), respectively. It can be observed that AVNS can find better solutions in a shorter time in all of the instances. In addition, the experimental results are summarized in Table 5. For each instance, we report the average fitness value (faver), the best fitness value (fbest), and the worst fitness value (fworst) of the 10 trials achieved by each algorithm. The results show that the proposed AVNS performs significantly better than other algorithms in terms of all comparison indicators. Thus, the proposed adaptive search-based solution improvement can effectively increase the performance of algorithm, suggesting that AVNS-based reconfiguration is a suitable method for supply network robustness enhancement.Figure 12
Fitness curve comparison between AVNS, GNS, LNS, and GNS + LNS: reconfiguring (a) chain 14, (b) chain 21, and (c) chain 25 by addingfa = 5% edges.
(a)(b)(c)Table 5
Performance comparison of four neighborhood searching method.
Chain 14Chain 21Chain 25FaverFbestFworstFaverFbestFworstFaverFbestFworstAVNS0.35830.38600.33170.60720.62830.57810.52440.53920.5001GNS0.35240.37920.32770.59170.61940.55860.52030.53310.4983LNS0.34780.37690.32770.60040.62640.56050.50480.51620.4826GNS + LNS0.35110.38530.32640.59730.61730.56470.51600.52930.4937


### 5.3. Experimental Result Discussion

Structural analysis of real-life supply networks is made. It is found that the degree distribution of real supply networks obeys the truncated power-law distribution. Such a finding indicates a very few number of entities occupy the central position in a supply network. These entities play critical roles in maintaining the basic operation of a supply network. Thus, a supply network is usually robust against random disruptions but is fragile when these important entities with high degrees are damaged.Experiments based on three real-life supply networks validate that the proposed AVNS-based reconfiguration method can enhance the robustness of supply networks effectively. In addition, it is also found that supply networks are vulnerable to target disruptions. They also exhibit comparatively stronger tolerance to random disruptions. Such experimental results consist with the structural characters of supply networks. Besides, comparing the robustness of Chain 14, Chain 21, and Chain 25, it is observed that density can affect the robustness of a supply network. A denser supply network can be more robust than a sparse supply network facing both random and target disruptions. In addition, the degree heterogeneity of a supply network can also impact the robustness of it facing target disruptions. The more heterogeneous a network is, the more fragile it is facing target disruptions. Edge addition-based supply network reconfiguration methods can enhance the robustness effectively. Along with the number of added edges increasing, the reconfigured network can exhibit a stronger robustness.


## 5.1. Three Real-Life Supply Networks

Three real-life supply networks used in this study, Chain 14, Chain 21, and Chain 25 are from an existing set of real-life cases [54]. Chain 14 describes a logistic supply network. Chain 21 presents a supply network of toilet preparations. Chain 25 is a supply network of farm machinery and equipment. The general characters of the three supply networks are presented in Table 1. All of them are composed of multiple types of entities, and the number of each type is varied. For example, in the Chain 14, the number of distributors is only 5, while the number of retailers is 66. Since the degree distribution of a supply network has been considered as a main factor affecting its robustness, the degree distributions of these networks are analyzed. It is found that all degree distributions can be fitted by truncated power-law [55]. The observed distributions and fitting curves are presented in Figure 5. Such character indicates that in these real-life supply networks, only a few nodes are intensively connected, while many others only have a few number of connections. According to the previous studies [8, 36], such a heterogeneous supply network can be robust against random disruptions but is vulnerable when entities with high degrees are damaged. In addition, the average degree [48] and H metric [56] of each network are also analyzed. The average degree can reflect the density of networks; the expression of it is presented by equation (13). The H metric is used to define the structural heterogeneity in a network; the definition of it is presented by equation (14). As presented in Table 1, Chain 25 is the most dense and heterogeneous network. Comparing with Chain 21 and Chain 25, Chain 14 is sparser and less heterogeneous:(13)k=1N∑iVki,where |V| is denotes the total number of nodes in network and ki is the degree value of node vi:(14)H=k2k2.where 〈k〉 denotes the average degree of a network, H reflects the level of the structural heterogeneity in a network, and the larger H, the more heterogeneous the network exhibits. From the definition, it is obvious that, in a homogeneous network, H is equal to one.Table 1
Basic characters of the three real-life supply networks.
Network nameNumber of each type of nodesTotal number of nodesTotal number of edges〈k〉HDistributorManufacturerSupplierRetailerTransporterChain 1459—66361161192.0521.983Chain 2117597634—1863593.8602.158Chain 253114294142—4098534.1714.653Figure 5
Degree distributions of real-life supply networks. (a) Chain 14. (b) Chain 21. (c) Chain 25.
(a)(b)(c)


## 5.2. Evaluation of AVNS-Based Supply Network Reconfiguration Method

To verify the effectiveness of AVNS-based supply network reconfiguration method, comparison with other edge addition-based network reconfiguration methods is made, specifically low degree-based reconfiguration method (LD) [53], low betweenness-based reconfiguration method (LB) [57], and simulated anneal-based reconfiguration method (SA) [58].The performances of AVNS-based and SA-based method can be influenced by several important parameters. In this study, the parameters of AVNS are set as follows: termination condition is 250 generations,Ninitial = 50, PL = 0.7, PG = 0.3, p1 = 0.1, p2 = 0.01, and Threshold = 0.1. The parameters of SA are set as follows: initial temperature T = 100, iteration time n = 5, cooling factor θ = 0.95, and low temperature T0 = 0.01. These parameters are set based on the trial-and-error method, which has been widely used to select the parameter values for heuristic algorithms in many previous works [59].Considering the number of added edges may affect the performance of reconfiguration methods, experiments based on the different fraction of added edges were performed. Fraction of added edge (fa) is defined as the fraction of the number of edges of original network before edge addition. The expression of fa is presented using equation (15). To achieve statistically significant results, each experiment was repeated 20 times. The final experimental results are calculated based on the 20 independent experiments. All experiments were performed using MATLAB R2014a and run on a PC equipped with an Intel Core i7 and 16 GB of memory, running Windows 7.(15)fa=SE,where E denote the edges in the original network, S represents the added edges, and |E| and |S| represent the number of edges in set E and S, respectively.


### 5.2.1. Experimental Results Based on Chain 14

Figures6 and 7 illustrate the robustness of Chain 14 and the reconfigured ones facing random disruptions and target disruptions, respectively. Figures 6(a)–6(c) show the responses of five supply networks facing random disruptions, including original Chain 14 and four reconfigured ones, under fa = 5%, fa = 10%, and fa = 15%, respectively. In Figures 6(a)–6(c), the horizontal axes denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Similar to Figure 6, Figures 7(a)–7(c) show the responses of five supply networks facing target disruptions, including original Chain 14 and four reconfigured ones, under fa = 5%, fa = 10%, and fa = 15%, respectively. For presenting a quantitative comparison, Table 2 summarizes the average values, the best values, and the worst values of Rr and Rt of the 20 independent experiments based on Chain 14.Figure 6
Responses of chain 14 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 7
Responses of chain 14 and reconfigured ones facing target disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 2
Robustness comparison of chain 14 and reconfigured ones.
fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.26230.34650.15030.01350.01680.01145LD0.27140.35660.15350.01850.02130.0158LB0.27720.35020.16530.02990.03570.0245AVNS0.28520.35870.17350.04790.05440.0385SA0.27940.35840.16150.03320.03510.031110LD0.28540.37450.17680.03700.04120.0256LB0.28890.38770.16440.03920.04050.0335AVNS0.30490.37490.17930.06030.06120.0514SA0.29860.37590.18170.04770.04870.039215LD0.29810.37320.21110.04440.04870.0337LB0.29630.37980.20550.04250.04450.0372AVNS0.31690.37690.24530.06350.06450.0534SA0.30700.37040.24100.05790.06080.0518Firstly, in both Figures6 and 7, the performances of all networks decrease when nodes are removed sequentially from the networks. It is also observed that a higher fraction of the added edge leads to a better performance for all reconfiguration methods. Besides, by comparing Figures 6 with 7, it is found that all networks are more vulnerable to target disruptions. For example, In Figure 6(a), when 15% nodes are disrupted under random disruptions, the function of original Chain 14 is also well preserved as the majority of remaining nodes are still connected to form a functional component. As presented in Figure 7(a), the value of normalized SLACC becomes 0, when less than 15% nodes are disrupted under target disruptions. By comparing the performances of different reconfiguration methods, it is observed that the networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table2, the average values and the best values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for the worst values of Rr, only when fa = 10%, the performance of the proposed AVNS-based method is slightly worse than SA-based method. Except for the instance under fa = 10%, the AVNS-based method also achieves the best performance. As for Rt, the proposed AVNS-based method achieves the best performance with respect to all of the three indicators. Such results are consistent with Figures 6 and 7.


### 5.2.2. Experimental Results Based on Chain 21

Figures8 and 9 present the robustness of Chain 21 and the reconfigured ones facing random disruptions and target disruptions, respectively. Similar to Figures 6 and 7, in all the figures of Figures 8 and 9, the horizontal axes denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Table 3 also summarizes the average values, the best values, and the worst values of both Rr and Rt of the 20 independent experiments based on Chain 21.Figure 8
Response of chain 21 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 9
Response of chain 21 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 3
Robustness comparison of chain 21 and reconfigured ones.
Fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.34760.39490.31650.09800.10240.09195LD0.34910.38030.30600.16520.17410.1558LB0.35700.40350.30710.16830.17660.1518AVNS0.36110.39930.32270.21790.22550.2119SA0.35590.39290.30210.16940.17520.161910LD0.36520.40590.30150.18810.19340.1799LB0.36740.39970.30940.18330.18620.1779AVNS0.37380.41840.32200.25180.25900.2423SA0.35370.40930.30100.18790.19390.181115LD0.38190.41460.34900.20340.20760.1980LB0.37920.41350.32520.19720.20350.1903AVNS0.38900.41530.35830.27840.29220.2685SA0.37490.40790.34440.21770.22310.2112As presented in Figures8 and 9, it is observed that Chain 21 is also vulnerable to target disruptions and exhibits much stronger tolerance to random disruptions. It is also noticed that Chain 21 is more robust than Chain 14 facing both random and target disruptions. For example, when the proportion of random disrupted nodes is 20%, the normalized SLACC of Chain 14 is less than 0.5, while the normalized SLACC of Chain 21 is almost 0.7. With respect to target disruptions, when the proportion of disrupted nodes in target disruptions is less than 15%, Chain 14 loses all functional components, while the functional components of Chain 21 still remain until the proportion of target disrupted nodes reaches 35%. The main reason of such difference can be deduced that Chain 21 is denser than Chain14. By comparing the performance of different reconfiguration methods, it is also observed that networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table3, the average values, the best values, and the worst values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for Rt, the proposed AVNS-based method also achieves the best performance in all of the instances with respect to all of the three indicators. The results presented in Table 3 are also consistent with Figures 8 and 9.


### 5.2.3. Experimental Results Based on Chain 25

Figures10 and 11 also present the robustness of Chain 25 and the reconfigured ones facing random disruptions and target disruptions, respectively. In all the figures of Figures 10 and 11, the horizontal axes also denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Table 4 also summarizes the average values, best values, and worst values of Rr and Rt of the 20 independent experiments based on Chain 25.Figure 10
Response of chain 25 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 11
Response of chain 25 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 4
Robustness comparison of chain 25 and reconfigured ones.
Fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.36220.42520.27400.07170.07340.06955LD0.37430.43400.29540.09420.09770.0913LB0.37610.43180.29520.09300.09530.0912AVNS0.37880.43440.30140.14060.14440.1371SA0.37410.43430.29310.09630.09800.094610LD0.39300.43020.32510.11210.11470.1096LB0.39540.43010.32900.11550.11790.1130AVNS0.39770.43050.35630.18260.18670.1788SA0.39230.41980.33140.12030.12280.118615LD0.40570.44940.32510.15210.15630.1476LB0.40560.44880.33240.14780.15090.1443AVNS0.41370.45310.36460.20790.21580.2024SA0.40320.44900.34580.13280.13450.1308As presented in Figures10 and 11, Chain 25 is also vulnerable to target disruptions and exhibits much stronger tolerance to random disruptions. It is also noticed that Chain 25 is more robust than Chain 14 facing both random and target disruptions. The main reason of such difference can be deduced that Chain 25 is much denser than Chain14. It can also be observed from Table 4 that Chain 25 is slightly robust than Chain 21 facing random disruptions. When facing target disruptions, Chain 25 is more vulnerable than Chain 21. Chain 25 is denser than Chain 21, which may enhance the robustness of it facing random disruptions. However, the stronger degree heterogeneity of it also weakens the robustness of it facing target disruptions. It is also observed from Figures 10 and 11 that networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table4, the average values, the best values, and the worst values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for Rt, the proposed AVNS-based method also achieves the best performance in all of the instances with respect to all of the three indicators. The results presented in Table 4 are also consistent with Figures 10 and 11.


### 5.2.4. Verification for Adaptive Search-Based Solution Improvement

To validate the effectiveness of proposed adaptive search-based solution improvement, a comparative experiment is also performed to compare the proposed AVNS with three alternative algorithms, GNS, LNS, and GNS + LNS. As for GNS and LNS, the adaptive search-based solution improvement is replaced by global search and community closeness-based local neighborhood search, respectively. In GNS + LNS, the adaptive neighborhood determination scheme in the solution improvement procedure is replaced by a randomized neighborhood selection, which is commonly used in VNS. Experiments were performed on 3 representative instances, namely, add 5% edges for Chain 14, Chain 21, and Chain 25, respectively. We ran each algorithm 10 times on each instance within a time limitTmax = 1800 seconds.The experimental results are presented in Figure12 and Table 5. The average fitness curves of AVNS, GNS, LNS, and GNS + LNS under fa = 5% for Chain 14, Chain 21, and Chain 25 are presented in Figures 12(a)–12(c), respectively. It can be observed that AVNS can find better solutions in a shorter time in all of the instances. In addition, the experimental results are summarized in Table 5. For each instance, we report the average fitness value (faver), the best fitness value (fbest), and the worst fitness value (fworst) of the 10 trials achieved by each algorithm. The results show that the proposed AVNS performs significantly better than other algorithms in terms of all comparison indicators. Thus, the proposed adaptive search-based solution improvement can effectively increase the performance of algorithm, suggesting that AVNS-based reconfiguration is a suitable method for supply network robustness enhancement.Figure 12
Fitness curve comparison between AVNS, GNS, LNS, and GNS + LNS: reconfiguring (a) chain 14, (b) chain 21, and (c) chain 25 by addingfa = 5% edges.
(a)(b)(c)Table 5
Performance comparison of four neighborhood searching method.
Chain 14Chain 21Chain 25FaverFbestFworstFaverFbestFworstFaverFbestFworstAVNS0.35830.38600.33170.60720.62830.57810.52440.53920.5001GNS0.35240.37920.32770.59170.61940.55860.52030.53310.4983LNS0.34780.37690.32770.60040.62640.56050.50480.51620.4826GNS + LNS0.35110.38530.32640.59730.61730.56470.51600.52930.4937


## 5.2.1. Experimental Results Based on Chain 14

Figures6 and 7 illustrate the robustness of Chain 14 and the reconfigured ones facing random disruptions and target disruptions, respectively. Figures 6(a)–6(c) show the responses of five supply networks facing random disruptions, including original Chain 14 and four reconfigured ones, under fa = 5%, fa = 10%, and fa = 15%, respectively. In Figures 6(a)–6(c), the horizontal axes denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Similar to Figure 6, Figures 7(a)–7(c) show the responses of five supply networks facing target disruptions, including original Chain 14 and four reconfigured ones, under fa = 5%, fa = 10%, and fa = 15%, respectively. For presenting a quantitative comparison, Table 2 summarizes the average values, the best values, and the worst values of Rr and Rt of the 20 independent experiments based on Chain 14.Figure 6
Responses of chain 14 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 7
Responses of chain 14 and reconfigured ones facing target disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 2
Robustness comparison of chain 14 and reconfigured ones.
fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.26230.34650.15030.01350.01680.01145LD0.27140.35660.15350.01850.02130.0158LB0.27720.35020.16530.02990.03570.0245AVNS0.28520.35870.17350.04790.05440.0385SA0.27940.35840.16150.03320.03510.031110LD0.28540.37450.17680.03700.04120.0256LB0.28890.38770.16440.03920.04050.0335AVNS0.30490.37490.17930.06030.06120.0514SA0.29860.37590.18170.04770.04870.039215LD0.29810.37320.21110.04440.04870.0337LB0.29630.37980.20550.04250.04450.0372AVNS0.31690.37690.24530.06350.06450.0534SA0.30700.37040.24100.05790.06080.0518Firstly, in both Figures6 and 7, the performances of all networks decrease when nodes are removed sequentially from the networks. It is also observed that a higher fraction of the added edge leads to a better performance for all reconfiguration methods. Besides, by comparing Figures 6 with 7, it is found that all networks are more vulnerable to target disruptions. For example, In Figure 6(a), when 15% nodes are disrupted under random disruptions, the function of original Chain 14 is also well preserved as the majority of remaining nodes are still connected to form a functional component. As presented in Figure 7(a), the value of normalized SLACC becomes 0, when less than 15% nodes are disrupted under target disruptions. By comparing the performances of different reconfiguration methods, it is observed that the networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table2, the average values and the best values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for the worst values of Rr, only when fa = 10%, the performance of the proposed AVNS-based method is slightly worse than SA-based method. Except for the instance under fa = 10%, the AVNS-based method also achieves the best performance. As for Rt, the proposed AVNS-based method achieves the best performance with respect to all of the three indicators. Such results are consistent with Figures 6 and 7.


## 5.2.2. Experimental Results Based on Chain 21

Figures8 and 9 present the robustness of Chain 21 and the reconfigured ones facing random disruptions and target disruptions, respectively. Similar to Figures 6 and 7, in all the figures of Figures 8 and 9, the horizontal axes denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Table 3 also summarizes the average values, the best values, and the worst values of both Rr and Rt of the 20 independent experiments based on Chain 21.Figure 8
Response of chain 21 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 9
Response of chain 21 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 3
Robustness comparison of chain 21 and reconfigured ones.
Fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.34760.39490.31650.09800.10240.09195LD0.34910.38030.30600.16520.17410.1558LB0.35700.40350.30710.16830.17660.1518AVNS0.36110.39930.32270.21790.22550.2119SA0.35590.39290.30210.16940.17520.161910LD0.36520.40590.30150.18810.19340.1799LB0.36740.39970.30940.18330.18620.1779AVNS0.37380.41840.32200.25180.25900.2423SA0.35370.40930.30100.18790.19390.181115LD0.38190.41460.34900.20340.20760.1980LB0.37920.41350.32520.19720.20350.1903AVNS0.38900.41530.35830.27840.29220.2685SA0.37490.40790.34440.21770.22310.2112As presented in Figures8 and 9, it is observed that Chain 21 is also vulnerable to target disruptions and exhibits much stronger tolerance to random disruptions. It is also noticed that Chain 21 is more robust than Chain 14 facing both random and target disruptions. For example, when the proportion of random disrupted nodes is 20%, the normalized SLACC of Chain 14 is less than 0.5, while the normalized SLACC of Chain 21 is almost 0.7. With respect to target disruptions, when the proportion of disrupted nodes in target disruptions is less than 15%, Chain 14 loses all functional components, while the functional components of Chain 21 still remain until the proportion of target disrupted nodes reaches 35%. The main reason of such difference can be deduced that Chain 21 is denser than Chain14. By comparing the performance of different reconfiguration methods, it is also observed that networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table3, the average values, the best values, and the worst values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for Rt, the proposed AVNS-based method also achieves the best performance in all of the instances with respect to all of the three indicators. The results presented in Table 3 are also consistent with Figures 8 and 9.


## 5.2.3. Experimental Results Based on Chain 25

Figures10 and 11 also present the robustness of Chain 25 and the reconfigured ones facing random disruptions and target disruptions, respectively. In all the figures of Figures 10 and 11, the horizontal axes also denote the percentage of disrupted nodes, while the vertical axes are values of normalized SLACC. Table 4 also summarizes the average values, best values, and worst values of Rr and Rt of the 20 independent experiments based on Chain 25.Figure 10
Response of chain 25 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Figure 11
Response of chain 25 and reconfigured ones facing random disruptions. (a)fa = 5%. (b) fa = 10%. (c) fa = 15%.
(a)(b)(c)Table 4
Robustness comparison of chain 25 and reconfigured ones.
Fa (%)MethodRrRtAverageBestWorstAverageBestWorst—Original0.36220.42520.27400.07170.07340.06955LD0.37430.43400.29540.09420.09770.0913LB0.37610.43180.29520.09300.09530.0912AVNS0.37880.43440.30140.14060.14440.1371SA0.37410.43430.29310.09630.09800.094610LD0.39300.43020.32510.11210.11470.1096LB0.39540.43010.32900.11550.11790.1130AVNS0.39770.43050.35630.18260.18670.1788SA0.39230.41980.33140.12030.12280.118615LD0.40570.44940.32510.15210.15630.1476LB0.40560.44880.33240.14780.15090.1443AVNS0.41370.45310.36460.20790.21580.2024SA0.40320.44900.34580.13280.13450.1308As presented in Figures10 and 11, Chain 25 is also vulnerable to target disruptions and exhibits much stronger tolerance to random disruptions. It is also noticed that Chain 25 is more robust than Chain 14 facing both random and target disruptions. The main reason of such difference can be deduced that Chain 25 is much denser than Chain14. It can also be observed from Table 4 that Chain 25 is slightly robust than Chain 21 facing random disruptions. When facing target disruptions, Chain 25 is more vulnerable than Chain 21. Chain 25 is denser than Chain 21, which may enhance the robustness of it facing random disruptions. However, the stronger degree heterogeneity of it also weakens the robustness of it facing target disruptions. It is also observed from Figures 10 and 11 that networks reconfigured by AVNS-based method are more robust than others facing both random and target disruptions, especially for target disruptions.As presented in Table4, the average values, the best values, and the worst values of Rr achieved by the proposed AVNS-based method are better than the three other methods in all of the instances. As for Rt, the proposed AVNS-based method also achieves the best performance in all of the instances with respect to all of the three indicators. The results presented in Table 4 are also consistent with Figures 10 and 11.


## 5.2.4. Verification for Adaptive Search-Based Solution Improvement

To validate the effectiveness of proposed adaptive search-based solution improvement, a comparative experiment is also performed to compare the proposed AVNS with three alternative algorithms, GNS, LNS, and GNS + LNS. As for GNS and LNS, the adaptive search-based solution improvement is replaced by global search and community closeness-based local neighborhood search, respectively. In GNS + LNS, the adaptive neighborhood determination scheme in the solution improvement procedure is replaced by a randomized neighborhood selection, which is commonly used in VNS. Experiments were performed on 3 representative instances, namely, add 5% edges for Chain 14, Chain 21, and Chain 25, respectively. We ran each algorithm 10 times on each instance within a time limitTmax = 1800 seconds.The experimental results are presented in Figure12 and Table 5. The average fitness curves of AVNS, GNS, LNS, and GNS + LNS under fa = 5% for Chain 14, Chain 21, and Chain 25 are presented in Figures 12(a)–12(c), respectively. It can be observed that AVNS can find better solutions in a shorter time in all of the instances. In addition, the experimental results are summarized in Table 5. For each instance, we report the average fitness value (faver), the best fitness value (fbest), and the worst fitness value (fworst) of the 10 trials achieved by each algorithm. The results show that the proposed AVNS performs significantly better than other algorithms in terms of all comparison indicators. Thus, the proposed adaptive search-based solution improvement can effectively increase the performance of algorithm, suggesting that AVNS-based reconfiguration is a suitable method for supply network robustness enhancement.Figure 12
Fitness curve comparison between AVNS, GNS, LNS, and GNS + LNS: reconfiguring (a) chain 14, (b) chain 21, and (c) chain 25 by addingfa = 5% edges.
(a)(b)(c)Table 5
Performance comparison of four neighborhood searching method.
Chain 14Chain 21Chain 25FaverFbestFworstFaverFbestFworstFaverFbestFworstAVNS0.35830.38600.33170.60720.62830.57810.52440.53920.5001GNS0.35240.37920.32770.59170.61940.55860.52030.53310.4983LNS0.34780.37690.32770.60040.62640.56050.50480.51620.4826GNS + LNS0.35110.38530.32640.59730.61730.56470.51600.52930.4937


## 5.3. Experimental Result Discussion

Structural analysis of real-life supply networks is made. It is found that the degree distribution of real supply networks obeys the truncated power-law distribution. Such a finding indicates a very few number of entities occupy the central position in a supply network. These entities play critical roles in maintaining the basic operation of a supply network. Thus, a supply network is usually robust against random disruptions but is fragile when these important entities with high degrees are damaged.Experiments based on three real-life supply networks validate that the proposed AVNS-based reconfiguration method can enhance the robustness of supply networks effectively. In addition, it is also found that supply networks are vulnerable to target disruptions. They also exhibit comparatively stronger tolerance to random disruptions. Such experimental results consist with the structural characters of supply networks. Besides, comparing the robustness of Chain 14, Chain 21, and Chain 25, it is observed that density can affect the robustness of a supply network. A denser supply network can be more robust than a sparse supply network facing both random and target disruptions. In addition, the degree heterogeneity of a supply network can also impact the robustness of it facing target disruptions. The more heterogeneous a network is, the more fragile it is facing target disruptions. Edge addition-based supply network reconfiguration methods can enhance the robustness effectively. Along with the number of added edges increasing, the reconfigured network can exhibit a stronger robustness.


## 6. Conclusions

The structure of a supply network is critically important to its robustness. In spite of the proposed optimal structural designs, a real-life supply network can be quite different from these optimal structures. Meanwhile, real cases reveal the vulnerability of real-life supply networks. Thus, this study proposes a robustness enhancing method for supply networks by reconfiguring the existing network structure. The following can be concluded:(1)
A supply network model considering the different roles of entities in supply networks is introduced. Based on the model, two robustness metrics describing supply networks’ tolerance of random and target disruptions are proposed.(2)
An AVNS-based reconfiguration method is presented for supply network robustness enhancement. In order to search for the optimal reconfiguration solution effectively and efficiently, a new variant of VNS, namely, AVNS is proposed. In the proposed AVNS, adaptive search-based solution improvement is designed, which is validated to be effectively improve algorithm performance.(3)
This study also has implications for empirical analysis of supply networks. The structural characters of three empirical supply networks are analyzed. It is found that the degree distribution of real-life supply networks obeys the truncated power-law distribution. Such finding indicates supply networks are heterogeneous. In a supply network, a very few number of entities occupy the central positions and play critically important roles to maintain the function of the supply network. While many others occupy peripheral positions and have less impact on the function of the supply network. Thus, a supply network is robust against random disruptions but is vulnerable when these important entities with high degrees are damaged.(4)
Experiments based on the three real-life supply networks were conducted. The effectiveness of the proposed AVNS-based supply network reconfiguration method is validated using comparative experiments. In addition, experimental results verify that supply networks are extremely vulnerable to target disruptions and exhibit stronger tolerance of random disruptions. And, the robustness of a supply network can be enhanced by adding a small number of edges especially for target disruptions.However, in this study, the adaptive behavior of entities facing disruptions in a supply network is neglected. Thus, we will take the adaptive behavior of entities into consideration and analyze the effect of it on the supply network robustness in the future.



---

*Source: 1292938-2020-12-08.xml*