# Two-Stage Robust Optimization for the Orienteering Problem with Stochastic Weights

Authors: Ke Shang; Felix T. S. Chan; Stephen Karungaru; Kenji Terada; Zuren Feng; Liangjun Ke
Journal: Complexity
 (2020)

---

## Abstract

In this paper, the two-stage orienteering problem with stochastic weights is studied, where the first-stage problem is to plan a path under the uncertain environment and the second-stage problem is a recourse action to make sure that the length constraint is satisfied after the uncertainty is realized. First, we explain the recourse model proposed by Evers et al. (2014) and point out that this model is very complex. Then, we introduce a new recourse model which is much simpler with less variables and less constraints. Based on these two recourse models, we introduce two different two-stage robust models for the orienteering problem with stochastic weights. We theoretically prove that the two-stage robust models are equivalent to their corresponding static robust models under the box uncertainty set, which indicates that the two-stage robust models can be solved by using common mathematical programming solvers (e.g., IBM CPLEX optimizer). Furthermore, we prove that the two two-stage robust models are equivalent to each other even though they are based on different recourse models, which indicates that we can use a much simpler model instead of a complex model for practical use. A case study is presented by comparing the two-stage robust models with a one-stage robust model for the orienteering problem with stochastic weights. The numerical results of the comparative studies show the effectiveness and superiority of the proposed two-stage robust models for dealing with the two-stage orienteering problem with stochastic weights.


---

## Body

## 1. Introduction

The orienteering problem (OP) is a routing problem which has been widely studied in the past few decades. It was first introduced in [1, 2] and had been developed in terms of the problem variants, solution algorithms, and applications. The original OP aims at planning a path which starts and ends at the depot location and visits a subset of nodes in order to maximize the total collected score, while the length of the path cannot exceed a predefined budget, and each node can only be visited at most one time. The OP has a wide practical application background. A few examples are unmanned aerial vehicle (UAV) mission planning (a deterministic one [3] and an uncertain one [4]), tourist trip design problem [5] (and a survey in [6]), and mobile crowdsourcing problem [7] (and a survey in [8]). A detailed survey on the OP is given in [9], and a more recent one is given in [10].The stochastic orienteering problem (SOP) is a variant of the OP, which assumes that some parameters in the OP are stochastic and uncertain such as the score associated with each node and the weight (or distance) associated with each arc. SOP is more appropriate than the OP in practical situations. For example, in a practical environment, traffic congestion affects the travel time between nodes. Ilhan et al. [11] first considered uncertainties in the score of nodes, and the resulting SOP is called OP with stochastic profits (OPSP). Campbell et al. [12] and Evers et al. [1] considered uncertainties in the travel and service times, respectively, and the resulting SOP is called OP with stochastic travel and service times (OPSTS) or OP with stochastic weights (OPSW). Other variants include the dynamic stochastic OP (DSOP) with stochastic time-dependent travel times [13] and the stochastic OPTW (SOPTW) with stochastic waiting time [14].In this paper, we focus on the OPSW where the uncertainties lie in the weights of the arcs. Some works on OPSW have been done in recent years. Campbell et al. [12] considered the OPSTS in which a penalty is incurred if a commitment to a node is made but not completed. A variant of VNS for the OPSTS is proposed, and its performance is evaluated by comparing with a dynamic programming (DP) approach. Evers et al. [1] introduced a two-stage stochastic programming model for the OPSW. The first-stage problem is to plan a path. The second-stage problem is a recourse action after the uncertain weights are realized, which aborts the execution of the first-stage path and enforces a direct return to the depot. The objective is to maximize the first-stage path score plus the expected loss of the score due to the recourse action. They presented a sample average approximation (SAA) approach and an OPSW heuristic to solve the problem. The performance of the two approaches was evaluated. Evers et al. [4] applied the robust optimization (RO) methodology to build robust models for UAV mission planning with uncertain fuel usage between targets, which is essentially an OPSW problem. The performance of the robust models is studied in terms of different uncertainty sets and the feasibility of the robust solutions.Inspired by the recourse model proposed in [1], we consider the two-stage OPSW in this paper, i.e., OPSW with recourse action. The first-stage problem is to plan a path with the stochastic weights unrevealed. The second-stage problem is a recourse action to avoid the violation of the length budget after the uncertainty is realized. The recourse action is to abort the execution of the first-stage path and enforce a direct return to the depot. This kind of recourse action is necessary, especially in the UAV mission planning. The UAV has to return to the depot safely in the uncertain environment. Evers et al. [1] used the two-stage stochastic programming technique [15] to deal with the two-stage OPSW. There are two main drawbacks in their method. (1) The recourse model itself has many decision variables and constraints, which make the two-stage model very complicated. (2) By using the SAA approach, the resulting SAA-problem is a large mixed-integer program (MIP), which makes it unacceptable to use for large instances.To address these issues, we use the two-stage robust optimization (RO) for the two-stage OPSW. Two-stage RO, which is also known as adjustable RO and can be extended to the multistage situation, was initially introduced in [16]. Compared with the traditional one-stage RO, two-stage RO divides the decision variables into “here and now” decisions and “wait and see” decisions, which are more flexible and are suitable for modeling two-stage problems. It has been successfully applied to different applications such as unit commitment (a single-objective one [17] and a multiobjective one [18]), network flow [19], and portfolio optimization [20]. To the best of our knowledge, this is the first time to use the two-stage RO paradigm for the two-stage OPSW. The two-stage RO model introduced in this paper has binary recourse decisions. This kind of problem has largely resisted solution so far [21]. Computing an optimal adjustable robust solution is often intractable since it requires computing a solution for all possible realizations of the uncertainties [22]. Instead of solving the two-stage RO model directly, Bertsimas et al. [23] studied the performance of the static solutions for two-stage adjustable robust linear optimization problems and presented a tight characterization of the conditions under which a static robust solution is optimal for the two-stage robust problem. From this point of view, we introduce the static robust model for the OPSW which corresponds to the two-stage robust model and study its performance and the relationships with the two-stage robust models. We prove that, with the box uncertainty set defined, the two-stage robust models are equivalent to their corresponding static robust models, and the two two-stage robust models are also equivalent to each other even though they are based on different recourse models. These conclusions we obtained indicate that the two-stage robust models for OPSW can be solved to optimality by solving their corresponding static robust models.It is worth mentioning that there are some other application fields which employ similar methodological tool to our method. Some of the representative applications are capacity expansion planning [24], humanitarian relief logistics [25], distribution expansion planning [26], plug-in electric vehicle (PEV) charging station design [27], and parking-lot- (PL-) based charging infrastructure allocation [28]. We can expect that our method has the potential to be applied in these fields as well.The main contributions of this paper are summarized as follows:(1)
For the two-stage OPSW, we propose a new recourse model which has less variables and less constraints compared with the recourse model proposed in [1]. The difference and relation of these two recourse models are discussed in detail in this paper.(2)
Based on the two recourse models, we present two different two-stage robust optimization models for OPSW. To the best of our knowledge, this is the first time to adopt the two-stage robust optimization method to solve the two-stage OPSW.(3)
We theoretically prove that the two-stage robust models are equivalent to their corresponding static robust models under the box uncertainty set, which means that we can use common mathematical programming solvers to solve the two-stage robust models. We also prove that the two two-stage robust models are equivalent to each other even though they are based on different recourse models. This indicates that we can use a much simpler model instead of the complex model in [1] for the two-stage OPSW.(4)
The two-stage robust models for OPSW are evaluated numerically by comparing them with a one-stage robust model for OPSW. The experimental results suggest the usefulness of the two-stage robust models for dealing with the two-stage OPSW.The remainder of the paper is organized as follows. First, the deterministic OP is described in Section2. Section 3 describes the two-stage OPSW and two recourse models. Section 4 introduces two two-stage robust models for OPSW and draws some theoretical conclusions of the equivalence between the two-stage robust models and their corresponding static robust models. A case study is presented in Section 5. We conclude the whole paper in Section 6.


## 2. The Deterministic Orienteering Problem

In this section, the formal definition and the mathematical model of the deterministic orienteering problem (OP) are introduced.In a deterministic OP, a set of verticesN is given with |N| as its cardinality. Each vertex i ∈ N has a score si associated with it. Denote 0 as the depot location, where 0 ∉ N and N+=N∪0. The goal is to plan a path with length limit L that starts and ends at the depot and visits some vertices in order to maximize the sum of the collected scores. Each vertex is visited at most one time.Suppose all nodesN+ are on a complete graph G = (N+, A), where A is the set of arcs connecting the vertices in N+. The weight of each arc (i, j) ∈ A is dij, representing the Euclidean distance from i to j. Let xij be a binary decision variable, where xij = 1 if and only if arc (i, j) is visited by the path; otherwise, xij = 0. An auxiliary variable ui is used to denote the position of node i in the path. The formulation of the deterministic OP is as follows:DOP:(1a)maximize∑i∈N∑j∈N+\ixij,(1b)subject to∑i,j∈Adijxij≤L,(1c)∑i∈Nx0i=∑i∈Nxi0=1,(1d)∑i∈N+\jxij=∑i∈N+jxji≤1,∀j∈N,(1e)ui−uj+1≤1−xijN,∀i,j∈N(1f)1≤ui≤N,∀i∈N,(1g)xij∈0,1,∀i,j∈A.Constraint (1b) is the path length constraint. Constraint (1c) guarantees that the path starts and ends at the depot. Constraint (1d) is the flow conservation constraint ensuring that a vertex is visited at most once. Constraint (1e) ensures the connectivity of the path. Constraints (1f) and (1g) are the boundary and integrality constraints on the auxiliary variables and decision variables, respectively.


## 3. The Two-Stage Orienteering Problem with Stochastic Weights

In this section, the two-stage orienteering problem with stochastic weights (OPSW) is introduced.Suppose the weight of each arc (i, j) is stochastic and uncertain; denote the stochastic weight of arc (i, j) as d˜ij. In this paper, we consider d˜ij as a symmetrically distributed random variable on the interval d¯ij−d^ij,d¯ij+d^ij, where d¯ij is the expected value of d˜ij and d^ij is the maximum deviation of dij from its expected value. For simplicity and convenience, we use dij to denote the realizations of d˜ij. In this paper, we use the interval value to describe the stochastic weights. This is because we will use the robust optimization technique to deal with the two-stage OPSW. In robust optimization, only interval value is needed, and we do not need more knowledge about the uncertain information, e.g., the probability distribution.We consider the two-stage OPSW, i.e., OPSW with recourse action. In the two-stage OPSW, the first-stage problem is to plan a path with the stochastic weights unrevealed. Due to the randomicity and uncertainty of the stochastic weights, the first-stage path may violate constraint (1b) after the uncertainty is realized. So, the second-stage problem is a recourse action to avoid constraint violation after the uncertainty is realized. The recourse action is to abort the execution of the first-stage path and enforce a direct return to the depot.


### 3.1. Recourse Model in [1]

The recourse model introduced in [1] is explained as follows. In this model, after the uncertain weights of the first-stage path are realized, the recourse action is performed to abort the execution of the first-stage path and enforce a direct return to the depot from the current location when the remaining budget cannot support any further visit of the remaining path. Figure 1 gives an illustration of this recourse action. Figure 1(a) shows the planned path in the first stage when all the weights are uncertain. Figure 1(b) shows the recourse action in the second stage after all the uncertain weights of the planned path are realized. The recourse action aborts the execution of the planned path at node 7 and forces a direct return to the depot from node 7. This is because any further execution of the planned path from node 7 will violate constraint (1b) (i.e., the visit of node 6 will violate the path length constraint in Figure 1).Figure 1
An illustration of the two-stage OPSW. (a) First-stage planned path. (b) Recourse action.
(a)(b)Denote the first-stage path as vectorx which contains all xij and the weight realizations as vector d which contains all dij. Let xijk be a binary variable, xijk = 1 if arc (i, j) is the kth arc in the first-stage path; otherwise, xijk = 0; let yi be a binary variable, and yi = 1 if node i is in the first-stage path but cannot be reached as a result of the recourse action; otherwise, yi = 0; and let zk be a binary variable; zk = 1 if the kth node in the first-stage path cannot be reached as a result of the recourse action; otherwise, zk = 0. With the first-stage path x and the weight realizations d, the recourse model of the two-stage OPSW proposed in [1] is formulated as follows.Recourse1:(2a)R1x,d=max−∑siyi,(2b)subject tox0j1≥x0j,∀j∈N,(2c)xijk≥xij+∑l∈N+xlik−1−1,∀i,j∈N,k=1,…,N,(2d)∑k=1k∑i,j∈Adijxijk+∑i,j∈Ad¯j0xijk≤L+Mzk,∀k=1,…,N,(2e)zk≥zk−1,∀k=2,…,N,(2f)yj≥∑i∈N+xijk+zk−1,∀j∈N,k=1,…,N,(2g)xijk∈0,1,∀i,j∈N+,k=1,…,N,(2h)yj∈0,1,∀i∈N,(2i)zk∈0,1,∀k=1,…,N,where objective function (2a) is to minimize the loss in the collected score as a result of the recourse action. Constraint (2b) identifies the first arc in the path. Constraint (2c) identifies the order of the other arcs in the path. Constraint (2d) determines the nodes of the first-stage path x that can and cannot be reached based on d, where M is a sufficiently large number. Constraint (2e) makes sure that all nodes in the path after the first unreachable node cannot be reached either. Constraint (2f) identifies the nodes in the first-stage path that cannot be reached, based on their indexes. For a detailed explanation of this model, refer to [1].From the above recourse model, we can see that there are |N|3 + 2|N|2 + 3|N| = O(|N|3) variables (i.e., xijk, yi, and zk) and |N|3 + |N|2 + 3|N| − 1 = O(|N|3) constraints in total, which is a very complex model.


### 3.2. A New Recourse Model

We now introduce a new recourse model which has less variables and constraints. We introduce a new binary variableyij; yij = 1 if arc (i, j) is in the first-stage path but is cancelled by the recourse action, and yij = 0 if arc (i, j) is in the first-stage path and is not cancelled by the recourse action, or arc (i, j) is not in the first-stage path. Then, the recourse model of the two-stage OPSW can be formulated as follows.Recourse2:(3a)=R2x,d=max−∑j∈Nsi∑i∈N+jyij,(3b)subject toyij≤xij,∀i,j∈A,(3c)∑i∈N+jyij≤∑k∈N+jyjk,∀j∈N,(3d)∑i,j∈Adijxij−∑i,j∈Adijyij+∑j∈N∑k∈N+jyjk−∑i∈N+jyijd¯j0≤L,(3e)yij∈0,1,∀i,j∈A,where objective function (3a) is to minimize the loss in the collected score as a result of the recourse action. Constraint (3b) ensures that the cancelled arcs are from the first-stage path. Constraint (3c) ensures that the cancelled arcs compose a subpath of the first-stage path starting at a vertex of the first-stage path and ending at the depot. Constraint (3d) ensures that the modified path after the recourse action is within the length limit.From the above example, we can see that there areN2+N=ON2 variables (i.e., yij) and N2+2N+1=ON2 constraints in total. Compared with the Recourse1 model, the Recourse2 model has much less variables and constraints.


### 3.3. The Difference between Recourse1 and Recourse2 Models

The idea behind the Recourse1 and Recourse2 models is different, and they may lead to different solutions. In the Recourse1 model, it is assumed that the uncertain weights of the planned path are realized in a sequential manner (i.e., the uncertain weight of each arc is realized one by one). However, in the Recourse2 model, it is assumed that the uncertain weights of the planned path are realized in a concurrent manner (i.e., the uncertain weights of all arcs are realized at the same time). Thus, the main difference between these two models is whether the prior knowledge of the realized weights is known beforehand.Let us take Figure1 as an example to illustrate this difference. For the Recourse1 model, the weights of the planned path are realized one by one during the execution of the planned path. If the current location is 7 as shown in Figure 1(b), the weight of the next arc 7⟶6 is realized, and the weights of the arcs 6⟶9 and 9⟶depot are still unknown. Now, we need to make a decision according to the Recourse1 model. We need to calculate the cost of visiting node 6 and returning to the depot from node 6. If the remaining budget cannot support this decision, the Recourse1 model will cancel visiting node 6 and directly return to the depot from node 7. However, for the Recourse2 model, the weights of the planned path are realized at the same time. Thus, the realized weights of arcs 7⟶6, 6⟶9, and 9⟶depot are known beforehand. If visiting node 6 violates the constraint, then the Recourse2 model will lead to the same solution as the Recourse1 model. However, if visiting node 6 does not violate the constraint, then the Recourse2 model will continue to visit node 6, and thus, the solution will be better than the Recourse1 model.In summary, the Recourse1 model and Recourse2 model are based on different ideas (i.e., how the uncertain weights of the planned path are realized). Also, the two recourse models may lead to different solutions since the Recourse2 model has more prior knowledge of the uncertain weights. With respect to the complexity of the models, the Recourse2 model is less complex and is more attractive to use in practice. However, the Recourse1 model is more realistic since we usually cannot get all the uncertain information beforehand.In the next section, we will establish two-stage robust optimization models based on these two recourse models. We will show that, under certain conditions, these two models are equivalent, i.e., we can use the Recourse2 model instead of the Recourse1 model. This is the main contribution of this paper.


## 3.1. Recourse Model in [1]

The recourse model introduced in [1] is explained as follows. In this model, after the uncertain weights of the first-stage path are realized, the recourse action is performed to abort the execution of the first-stage path and enforce a direct return to the depot from the current location when the remaining budget cannot support any further visit of the remaining path. Figure 1 gives an illustration of this recourse action. Figure 1(a) shows the planned path in the first stage when all the weights are uncertain. Figure 1(b) shows the recourse action in the second stage after all the uncertain weights of the planned path are realized. The recourse action aborts the execution of the planned path at node 7 and forces a direct return to the depot from node 7. This is because any further execution of the planned path from node 7 will violate constraint (1b) (i.e., the visit of node 6 will violate the path length constraint in Figure 1).Figure 1
An illustration of the two-stage OPSW. (a) First-stage planned path. (b) Recourse action.
(a)(b)Denote the first-stage path as vectorx which contains all xij and the weight realizations as vector d which contains all dij. Let xijk be a binary variable, xijk = 1 if arc (i, j) is the kth arc in the first-stage path; otherwise, xijk = 0; let yi be a binary variable, and yi = 1 if node i is in the first-stage path but cannot be reached as a result of the recourse action; otherwise, yi = 0; and let zk be a binary variable; zk = 1 if the kth node in the first-stage path cannot be reached as a result of the recourse action; otherwise, zk = 0. With the first-stage path x and the weight realizations d, the recourse model of the two-stage OPSW proposed in [1] is formulated as follows.Recourse1:(2a)R1x,d=max−∑siyi,(2b)subject tox0j1≥x0j,∀j∈N,(2c)xijk≥xij+∑l∈N+xlik−1−1,∀i,j∈N,k=1,…,N,(2d)∑k=1k∑i,j∈Adijxijk+∑i,j∈Ad¯j0xijk≤L+Mzk,∀k=1,…,N,(2e)zk≥zk−1,∀k=2,…,N,(2f)yj≥∑i∈N+xijk+zk−1,∀j∈N,k=1,…,N,(2g)xijk∈0,1,∀i,j∈N+,k=1,…,N,(2h)yj∈0,1,∀i∈N,(2i)zk∈0,1,∀k=1,…,N,where objective function (2a) is to minimize the loss in the collected score as a result of the recourse action. Constraint (2b) identifies the first arc in the path. Constraint (2c) identifies the order of the other arcs in the path. Constraint (2d) determines the nodes of the first-stage path x that can and cannot be reached based on d, where M is a sufficiently large number. Constraint (2e) makes sure that all nodes in the path after the first unreachable node cannot be reached either. Constraint (2f) identifies the nodes in the first-stage path that cannot be reached, based on their indexes. For a detailed explanation of this model, refer to [1].From the above recourse model, we can see that there are |N|3 + 2|N|2 + 3|N| = O(|N|3) variables (i.e., xijk, yi, and zk) and |N|3 + |N|2 + 3|N| − 1 = O(|N|3) constraints in total, which is a very complex model.


## 3.2. A New Recourse Model

We now introduce a new recourse model which has less variables and constraints. We introduce a new binary variableyij; yij = 1 if arc (i, j) is in the first-stage path but is cancelled by the recourse action, and yij = 0 if arc (i, j) is in the first-stage path and is not cancelled by the recourse action, or arc (i, j) is not in the first-stage path. Then, the recourse model of the two-stage OPSW can be formulated as follows.Recourse2:(3a)=R2x,d=max−∑j∈Nsi∑i∈N+jyij,(3b)subject toyij≤xij,∀i,j∈A,(3c)∑i∈N+jyij≤∑k∈N+jyjk,∀j∈N,(3d)∑i,j∈Adijxij−∑i,j∈Adijyij+∑j∈N∑k∈N+jyjk−∑i∈N+jyijd¯j0≤L,(3e)yij∈0,1,∀i,j∈A,where objective function (3a) is to minimize the loss in the collected score as a result of the recourse action. Constraint (3b) ensures that the cancelled arcs are from the first-stage path. Constraint (3c) ensures that the cancelled arcs compose a subpath of the first-stage path starting at a vertex of the first-stage path and ending at the depot. Constraint (3d) ensures that the modified path after the recourse action is within the length limit.From the above example, we can see that there areN2+N=ON2 variables (i.e., yij) and N2+2N+1=ON2 constraints in total. Compared with the Recourse1 model, the Recourse2 model has much less variables and constraints.


## 3.3. The Difference between Recourse1 and Recourse2 Models

The idea behind the Recourse1 and Recourse2 models is different, and they may lead to different solutions. In the Recourse1 model, it is assumed that the uncertain weights of the planned path are realized in a sequential manner (i.e., the uncertain weight of each arc is realized one by one). However, in the Recourse2 model, it is assumed that the uncertain weights of the planned path are realized in a concurrent manner (i.e., the uncertain weights of all arcs are realized at the same time). Thus, the main difference between these two models is whether the prior knowledge of the realized weights is known beforehand.Let us take Figure1 as an example to illustrate this difference. For the Recourse1 model, the weights of the planned path are realized one by one during the execution of the planned path. If the current location is 7 as shown in Figure 1(b), the weight of the next arc 7⟶6 is realized, and the weights of the arcs 6⟶9 and 9⟶depot are still unknown. Now, we need to make a decision according to the Recourse1 model. We need to calculate the cost of visiting node 6 and returning to the depot from node 6. If the remaining budget cannot support this decision, the Recourse1 model will cancel visiting node 6 and directly return to the depot from node 7. However, for the Recourse2 model, the weights of the planned path are realized at the same time. Thus, the realized weights of arcs 7⟶6, 6⟶9, and 9⟶depot are known beforehand. If visiting node 6 violates the constraint, then the Recourse2 model will lead to the same solution as the Recourse1 model. However, if visiting node 6 does not violate the constraint, then the Recourse2 model will continue to visit node 6, and thus, the solution will be better than the Recourse1 model.In summary, the Recourse1 model and Recourse2 model are based on different ideas (i.e., how the uncertain weights of the planned path are realized). Also, the two recourse models may lead to different solutions since the Recourse2 model has more prior knowledge of the uncertain weights. With respect to the complexity of the models, the Recourse2 model is less complex and is more attractive to use in practice. However, the Recourse1 model is more realistic since we usually cannot get all the uncertain information beforehand.In the next section, we will establish two-stage robust optimization models based on these two recourse models. We will show that, under certain conditions, these two models are equivalent, i.e., we can use the Recourse2 model instead of the Recourse1 model. This is the main contribution of this paper.


## 4. Two-Stage Robust Optimization for OPSW

In this section, we apply the two-stage RO methodology to model the two-stage OPSW. In the two-stage OPSW, the first-stage “here and now” decisions are the binary decision variablesxij described in Section 2. The second-stage “wait and see” decisions are the binary decision variables yi,zk in the Recourse1 model or the binary decision variables yij in the Recourse2 model.In the two-stage RO for OPSW, an uncertainty set needs to be defined for the stochastic weights. We consider the box uncertainty set which is defined by the∞-norm of the uncertain vector. The reasons that we choose the box uncertainty set for the two-stage RO for OPSW are as follows:(1)
It is simple compared with the polyhedral uncertainty set and the ellipsoidal uncertainty set which are defined by 1-norm [29] and 2-norm [30], respectively, and the derived robust counterpart has the same computational complexity as the original model.(2)
With the box uncertainty set, we can draw some interesting conclusions in the following sections which describe the equivalence between the two-stage robust models and their corresponding static robust models.Without loss of generality, the box uncertainty setU for the stochastic weights is defined as follows:(4)U=d∈ℝM:dij=d¯ij+ζijd^ij,∀i,j∈N+,ζ∈Z,where d is an M-dimensional vector with M=N+×N+, ζ∈ℝM is the vector of primitive uncertainties, and Z is a convex set which is defined as follows:(5)Z=ζ∈ℝM:ζ∞≤Θ,where Θ∈0,1 is the parameter controlling the size of Z.Next, we introduce two two-stage RO models for OPSW based on the Recourse1 model and the Recourse2 model, respectively.


### 4.1. Two-Stage Robust Model for OPSW with the Recourse1 Model

Based on the Recourse1 model and the two-stage RO paradigm, we introduce the following two-stage RO model for OPSW.Two-stage-R1:(6a)maximize∑i∈Nsi∑j∈N+\ixij+mind∈UR1x,d,(6b)subject to∑i,j∈Ad¯ij−d^ijxij≤L,(6c)1c−1g,where R1x,d is the Recourse1 model and U is the box uncertainty set. Constraint (6b) is the length limit on the first-stage path. Without constraint (6b), the first-stage path can be arbitrarily long providing there exist unvisited nodes, and these nodes can be included in the first-stage path even when some nodes in any particular case cannot be reached. By adding constraint (6b), we limit the length of the first-stage path in the most optimistic situation, i.e., all arc weights are equal to their minimum values. With this constraint, the size of the solution space can be reduced, while the problem optimality is maintained.The two-stage robust model for OPSW introduced above is an 0-1 integer programming problem with 0-1 integer recourse. Next, we present its corresponding static robust model in which the second-stage “wait and see” decisions become “here and now.” The corresponding static robust model of the Two-stage-R1 model is formulated as follows.Static-R1:(7a)maximize∑i∈Nsi∑j∈N+ixij−∑i∈Nsiyi,(7b)subject to1c−1g,6b,(7c)2b−2c,2e−2i,(7d)∑k=1K∑i,j∈Adijxijk+∑i,j∈Ad¯j0xijK≤L+MzK,∀K=1,…,N,d∈U.In the above static robust model, the second-stage decision variablesyi and zk are “here and now” and do not depend on the realizations of uncertain d. Both first-stage decisions xij and second-stage decisions yi and zk are selected before uncertain d is known. An optimal static robust solution to Static-R1 can be computed efficiently with the box uncertainty set U. What interests us is the relationship between the two-stage robust model Two-stage-R1 and its corresponding static robust model Static-R1.In the following, we establish a theorem which describes the equivalence of the Two-stage-R1 model and the Static-R1 model.Theorem 1.
The two-stage robust model Two-stage-R1 and its corresponding static robust model Static-R1 are equivalent.Proof.
It is clear that the optimal solution of the static robust model Static-R1 is a feasible solution of the two-stage robust model Two-stage-R1. All we need to show is that the optimal solution of the two-stage robust model Two-stage-R1 is a feasible solution of the static robust model Static-R1.
We prove by apagoge. Denotexij∗,xijk∗,yi∗,zk∗ as the optimal solution of the two-stage robust model Two-stage-R1. Suppose the optimal solution is infeasible for the static robust model Static-R1, which means(8)∃d′∈UandK′,∑k=1K′∑i,j∈Adij′xijk∗+∑i,j∈Ad¯j0xijK′∗>L+MzK′∗.
BecauseM is a sufficiently large number, the above condition is only satisfied by zK′∗=0. This means that the K′th node in the first-stage path of the two-stage robust model Two-stage-R1 is reachable, but this node is unreachable under the context of the static robust model Static-R1.
Now, we consider the second-stage problemR1x∗,d′, where x∗ is the first-stage optimal solution, and denote the optimal solution as yi′,zk′. Then, for K′,(9)∑k=1K′∑i,j∈Adij′xijk∗+∑i,j∈Ad¯j0xijK′∗≤L+MzK′′.
Comparing constraints (8) and (9), it is clear that zK′′ must be 1. This means the K′th node in the first-stage path is unreachable with d′. Denote the K′th node in the first-stage path as node j; then, the second-stage optimal value RSx∗,d′≤−∑i∈Nsiyi∗−sj. Because we are optimizing mind∈URSx∗,d, yi∗,zk∗ is not the optimal second-stage solution, so this is a contradiction. Thus, the hypothesis cannot be established, which means xij∗,xijk∗,yi∗,zk∗ is feasible for the static robust model Static-R1.
We conclude that the optimal solution of the two-stage robust model Two-stage-R1 is a feasible solution of the static robust model Static-R1. Because the two models have the same objective function value with the same solutions, the optimal solution of the two-stage robust model Two-stage-R1 is also the optimal solution of the static robust model Static-R1; this implies the two models are equivalent.Remark 1.
The proof of Theorem1 does not need the support of the box uncertainty set. We can still draw this conclusion even if the uncertainty set U is an arbitrary uncertainty set.Based on Theorem1, the two-stage robust model Two-stage-R1 can be solved to optimality by solving its corresponding static robust model Static-R1. Comparing the static robust model Static-R1 with the original deterministic OP model DOP, many new integer variables are added which makes the static robust model Static-R1 computationally expensive. Evers et al. [1] proved that the relaxation model with 0≤xijk≤1 and 0≤yi≤1 of the second-stage problem R1x,d is equivalent to the original R1x,d, and the resulting relaxation model provides a substantial decrease in the computation time. This conclusion can be easily applied to the static robust model Static-R1 which leads to the following proposition.Proposition 1.
The relaxation model with0≤xijk≤1 and 0≤yi≤1 of the static robust model Static-R1 is equivalent to the original static robust model Static-R1.Proof.
This conclusion can be drawn by following the proof way of Theorem1 in [1].
However, even the relaxed Static-R1 model has a large number of decision variables and constraints, which make this model not practical to use.


### 4.2. Two-Stage Robust Model for OPSW with the Recourse2 Model

Based on the Recourse2 model and the two-stage RO paradigm, we introduce the following two-stage RO model for OPSW.Two-stage-R2:(10a)maximize∑i∈Nsi∑j∈N+\ixij+mind∈UR2x,d,(10b)subject to1c−1g,6b,where R2x,d is the Recourse2 model and U is the box uncertainty set.We also consider the corresponding static robust model of Two-stage-R2 instead of solving the two-stage robust model directly; the corresponding static robust model of Two-stage-R2 is formulated as follows.Static-R2:(11a)maximize∑i∈Nsi∑j∈N+\ixij−∑j∈Nsj∑i∈N+jyij,(11b)subject to1c−1g,6b,(11c)3b−3c,3e,(11d)∑i,j∈Adijxij−∑i,j∈Adijyij+∑j∈N∑k∈N+\jyjk−∑i∈N+\jyijd¯j0≤L,∀d∈U.We can readily see that the optimal solution of the static robust model Static-R2 is feasible to the two-stage robust model Two-stage-R2. With the help of the box uncertainty set, the following theorem can be established which shows that Two-stage-R2 and Static-R2 are equivalent.Theorem 2.
The two-stage robust model Two-stage-R2 and its corresponding static robust model Static-R2 are equivalent.Proof.
It is clear that the optimal solution of the static robust model Static-R2 is a feasible solution of the two-stage robust model Two-stage-R2. All we need to show is that the optimal solution of the two-stage robust model Two-stage-R2 is a feasible solution of the static robust model Static-R2.
We prove by apagoge. Denotexij∗,yij∗ as the optimal solution of the two-stage robust model Two-stage-R2. Suppose the optimal solution is infeasible for the static robust model Static-R2, which means(12)∃d′∈U,∑i,j∈Adij′xij∗−∑i,j∈Adij′yij∗+∑j∈N∑k∈N+\jyjk∗−∑i∈N+\jyij∗d¯j0>L.
Denotedu=d+Θd^; according to the definition of the box uncertainty set U, we know that du∈U and du≽d′, where ≽ is the element-wise inequality. Based on inequality (12), it is clear that(13)∑i,j∈Adijuxij∗−∑i,j∈Adijuyij∗+∑j∈N∑k∈N+\jyjk∗−∑i∈N+\jyij∗d¯j0>L.
Denoted∗∈U as the optimal value of d that achieves optimal solution xij∗,yij∗ in the two-stage robust model Two-stage-R2; then,(14)∑i,j∈Adij∗xij∗−∑i,j∈Adij∗yij∗+∑j∈N∑k∈N+\jyjk∗−∑i∈N+\jyij∗d¯j0≤L,∑i,j∈Adij∗xij∗−∑i,j∈Adij∗yij′+∑j∈N∑k∈N+\jyjk′−∑i∈N+\jyij′d¯j0>L,∀y′∈Yandy′≠y∗,where Y=yij′≤yij∗,∀i,j,y′:∑i∈N+jyij′≤∑k∈N+\jyjk′,∀j,yij′∈0,1,∀i,j is the set which contains all recourse actions with less cancelled arcs compared with y∗.
Based on the fact thatdu≽d∗ and using inequality (14), we have(15)∑i,j∈Adijuxij∗−∑i,j∈Adijuyij′+∑j∈N∑k∈N+\jyjk′−∑i∈N+\jyij′d¯j0>L,∀y′∈Yandy′≠y∗.
Combining inequalities (13) and (15), we can observe that, for the second-stage problem R2x∗,du, the recourse action needs to cancel more arcs than y∗ to satisfy the length constraint, which means R2x∗,du<−∑j∈Nsj∑i∈N+\jyij∗. Because we are optimizing mind∈UR2x∗,d, y∗ is not the optimal second-stage solution, so this is a contradiction. Hence, the hypothesis cannot be established, which means xij∗,yij∗ is feasible for the static robust model Static-R2.
We conclude that the optimal solution of the two-stage robust model Two-stage-R2 is a feasible solution of the static robust model Static-R2. Because the two models have the same objective function value with the same solutions, the optimal solution of the two-stage robust model Two-stage-R2 is also the optimal solution of the static robust model Static-R2; this implies the two models are equivalent.Based on Theorem2, the two-stage robust model Two-stage-R2 can be solved to optimality by solving its corresponding static robust model Static-R2. Meanwhile, the Static-R2 model has much less decision variables and constraints compared with the Static-R1 model, which make it more practical to use.


### 4.3. The Relationship between Two-Stage-R1 and Two-Stage-R2 Models

Until now, we have introduced two two-stage robust models Two-stage-R1 and Two-stage-R2 and also proved that these two models are equivalent to their corresponding static robust models, respectively. In this section, we further investigate the relationships between Two-stage-R1 and Two-stage-R2.First, we investigate the static models Static-R1 and Static-R2. Comparing static model Static-R2 with static model Static-R1, model Static-R2 has less decision variables and less constraints and is computationally more attractive. The two static models are based on different recourse models. Next, we show that model Static-R1 and model Static-R2 are equivalent with the support of the box uncertainty set.Theorem 3.
The static robust models Static-R1 and Static-R2 are equivalent.Proof.
First, supposexij∗,xijk∗,yi∗,zk∗ is the optimal solution of the static robust model Static-R1, and we introduce decision variable yij which is defined in the Recourse2 model to model Static-R1; then, the optimal solution xij∗,xijk∗,yi∗,zk∗ can be mapped to an optimal solution xij∗,yij∗ of model Static-R1, and it is clear that xij∗,yij∗ is feasible to the static robust model Static-R2.
Then, supposexij∗,yij∗ is the optimal solution of the static robust model Static-R2, and we introduce variables xijk,yi,zk which are defined in the Recourse1 model to model Static-R2; then, the optimal solution xij∗,yij∗ can be mapped to an optimal solution xij∗,xijk∗,yi∗,zk∗ of model Static-R2, and we now show that xij∗,xijk∗,yi∗,zk∗ is feasible to the static robust model Static-R1.
SupposezK′∗=0 and zK′+1∗=1; then, this means the nodes in the first-stage path become unreachable from the K′+1th node. Then, length constraint (11d) in the static robust model Static-R2 is equivalent to(16)∑k=1K′∑i,j∈Adijxijk∗+∑i,j∈Ad¯j0xijK′∗≤L,∀d∈U.
Based on the definition of the box uncertainty setU, inequality (16) is equivalent to(17)∑k=1K′∑i,j∈Adij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′∗≤L.
We transform the left-hand side of the above inequality as follows:(18)∑k=1K′∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′∗=∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯ij+Θd^ijxijK′∗+∑i,j∈Ad¯j0xijK′∗≥∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯ij+d¯j0xijK′∗>1∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′−1∗,where relation 1 is due to the triangle inequality.
Based on (17) and (18), we have(19)∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′−1∗≤L,which implies(20)∑k=1K′−1∑i,j∈Adijxijk∗+∑i,j∈Ad¯j0xijK′−1∗≤L,∀d∈U.
Following the above transformation recursively, finally, we can get(21)∑k=1K∑i,j∈Adijxijk∗+∑i,j∈Ad¯j0xijK∗≤L,∀K=1,...,K′,d∈U.
So, the optimal solutionxij∗,xijk∗,yi∗,zk∗ is feasible to the static robust model Static-R1.
We conclude that the optimal solution of the static robust model Static-R1 is a feasible solution of the static robust model Static-R2, and the optimal solution of the static robust model Static-R2 is a feasible solution of the static robust model Static-R1. Then, the two models have the same optimal solution; this implies the two models are equivalent.
The following corollary shows the equivalence between two two-stage robust models.Corollary 1.
The two-stage robust models Two-stage-R1 and Two-stage-R2 are equivalent.Proof.
Based on Theorems1, 2, and 3, we can draw this conclusion.
Based on Theorems1–3 and Corollary 1, we know that the four models Two-stage-R1, Static-R1, Two-stage-R2, and Static-R2 are equivalent to each other. It is an interesting conclusion that Two-stage-R1 and Two-stage-R2 are equivalent under the box uncertainty set even though they are based on different recourse models.In this section, we have established the two-stage robust optimization models for OPSW. First, we proved that the two-stage robust optimization models are equivalent to their corresponding static robust models. This is a very important conclusion since this indicates that the two-stage robust models can be solved by solving their corresponding static models. We can directly use some mathematical programming solvers (e.g., CPLEX) to solve the two-stage robust optimization models. Second, we proved that, with the box uncertainty set, Two-stage-R1 and Two-stage-R2 are equivalent. This is another important conclusion since this indicates that we can use a much simpler model (i.e., Recourse2 model) to get the same solution as the Recourse1 model. As we have discussed in the previous section, the Recourse1 model is more realistic, and this recourse model has been well studied in [1]. However, this model is very complex and is not preferable to use in practice. We introduced the Recourse2 model, and now, our theories support us to use the Recourse2 model instead of the Recourse1 model in our two-stage robust optimization models.


## 4.1. Two-Stage Robust Model for OPSW with the Recourse1 Model

Based on the Recourse1 model and the two-stage RO paradigm, we introduce the following two-stage RO model for OPSW.Two-stage-R1:(6a)maximize∑i∈Nsi∑j∈N+\ixij+mind∈UR1x,d,(6b)subject to∑i,j∈Ad¯ij−d^ijxij≤L,(6c)1c−1g,where R1x,d is the Recourse1 model and U is the box uncertainty set. Constraint (6b) is the length limit on the first-stage path. Without constraint (6b), the first-stage path can be arbitrarily long providing there exist unvisited nodes, and these nodes can be included in the first-stage path even when some nodes in any particular case cannot be reached. By adding constraint (6b), we limit the length of the first-stage path in the most optimistic situation, i.e., all arc weights are equal to their minimum values. With this constraint, the size of the solution space can be reduced, while the problem optimality is maintained.The two-stage robust model for OPSW introduced above is an 0-1 integer programming problem with 0-1 integer recourse. Next, we present its corresponding static robust model in which the second-stage “wait and see” decisions become “here and now.” The corresponding static robust model of the Two-stage-R1 model is formulated as follows.Static-R1:(7a)maximize∑i∈Nsi∑j∈N+ixij−∑i∈Nsiyi,(7b)subject to1c−1g,6b,(7c)2b−2c,2e−2i,(7d)∑k=1K∑i,j∈Adijxijk+∑i,j∈Ad¯j0xijK≤L+MzK,∀K=1,…,N,d∈U.In the above static robust model, the second-stage decision variablesyi and zk are “here and now” and do not depend on the realizations of uncertain d. Both first-stage decisions xij and second-stage decisions yi and zk are selected before uncertain d is known. An optimal static robust solution to Static-R1 can be computed efficiently with the box uncertainty set U. What interests us is the relationship between the two-stage robust model Two-stage-R1 and its corresponding static robust model Static-R1.In the following, we establish a theorem which describes the equivalence of the Two-stage-R1 model and the Static-R1 model.Theorem 1.
The two-stage robust model Two-stage-R1 and its corresponding static robust model Static-R1 are equivalent.Proof.
It is clear that the optimal solution of the static robust model Static-R1 is a feasible solution of the two-stage robust model Two-stage-R1. All we need to show is that the optimal solution of the two-stage robust model Two-stage-R1 is a feasible solution of the static robust model Static-R1.
We prove by apagoge. Denotexij∗,xijk∗,yi∗,zk∗ as the optimal solution of the two-stage robust model Two-stage-R1. Suppose the optimal solution is infeasible for the static robust model Static-R1, which means(8)∃d′∈UandK′,∑k=1K′∑i,j∈Adij′xijk∗+∑i,j∈Ad¯j0xijK′∗>L+MzK′∗.
BecauseM is a sufficiently large number, the above condition is only satisfied by zK′∗=0. This means that the K′th node in the first-stage path of the two-stage robust model Two-stage-R1 is reachable, but this node is unreachable under the context of the static robust model Static-R1.
Now, we consider the second-stage problemR1x∗,d′, where x∗ is the first-stage optimal solution, and denote the optimal solution as yi′,zk′. Then, for K′,(9)∑k=1K′∑i,j∈Adij′xijk∗+∑i,j∈Ad¯j0xijK′∗≤L+MzK′′.
Comparing constraints (8) and (9), it is clear that zK′′ must be 1. This means the K′th node in the first-stage path is unreachable with d′. Denote the K′th node in the first-stage path as node j; then, the second-stage optimal value RSx∗,d′≤−∑i∈Nsiyi∗−sj. Because we are optimizing mind∈URSx∗,d, yi∗,zk∗ is not the optimal second-stage solution, so this is a contradiction. Thus, the hypothesis cannot be established, which means xij∗,xijk∗,yi∗,zk∗ is feasible for the static robust model Static-R1.
We conclude that the optimal solution of the two-stage robust model Two-stage-R1 is a feasible solution of the static robust model Static-R1. Because the two models have the same objective function value with the same solutions, the optimal solution of the two-stage robust model Two-stage-R1 is also the optimal solution of the static robust model Static-R1; this implies the two models are equivalent.Remark 1.
The proof of Theorem1 does not need the support of the box uncertainty set. We can still draw this conclusion even if the uncertainty set U is an arbitrary uncertainty set.Based on Theorem1, the two-stage robust model Two-stage-R1 can be solved to optimality by solving its corresponding static robust model Static-R1. Comparing the static robust model Static-R1 with the original deterministic OP model DOP, many new integer variables are added which makes the static robust model Static-R1 computationally expensive. Evers et al. [1] proved that the relaxation model with 0≤xijk≤1 and 0≤yi≤1 of the second-stage problem R1x,d is equivalent to the original R1x,d, and the resulting relaxation model provides a substantial decrease in the computation time. This conclusion can be easily applied to the static robust model Static-R1 which leads to the following proposition.Proposition 1.
The relaxation model with0≤xijk≤1 and 0≤yi≤1 of the static robust model Static-R1 is equivalent to the original static robust model Static-R1.Proof.
This conclusion can be drawn by following the proof way of Theorem1 in [1].
However, even the relaxed Static-R1 model has a large number of decision variables and constraints, which make this model not practical to use.


## 4.2. Two-Stage Robust Model for OPSW with the Recourse2 Model

Based on the Recourse2 model and the two-stage RO paradigm, we introduce the following two-stage RO model for OPSW.Two-stage-R2:(10a)maximize∑i∈Nsi∑j∈N+\ixij+mind∈UR2x,d,(10b)subject to1c−1g,6b,where R2x,d is the Recourse2 model and U is the box uncertainty set.We also consider the corresponding static robust model of Two-stage-R2 instead of solving the two-stage robust model directly; the corresponding static robust model of Two-stage-R2 is formulated as follows.Static-R2:(11a)maximize∑i∈Nsi∑j∈N+\ixij−∑j∈Nsj∑i∈N+jyij,(11b)subject to1c−1g,6b,(11c)3b−3c,3e,(11d)∑i,j∈Adijxij−∑i,j∈Adijyij+∑j∈N∑k∈N+\jyjk−∑i∈N+\jyijd¯j0≤L,∀d∈U.We can readily see that the optimal solution of the static robust model Static-R2 is feasible to the two-stage robust model Two-stage-R2. With the help of the box uncertainty set, the following theorem can be established which shows that Two-stage-R2 and Static-R2 are equivalent.Theorem 2.
The two-stage robust model Two-stage-R2 and its corresponding static robust model Static-R2 are equivalent.Proof.
It is clear that the optimal solution of the static robust model Static-R2 is a feasible solution of the two-stage robust model Two-stage-R2. All we need to show is that the optimal solution of the two-stage robust model Two-stage-R2 is a feasible solution of the static robust model Static-R2.
We prove by apagoge. Denotexij∗,yij∗ as the optimal solution of the two-stage robust model Two-stage-R2. Suppose the optimal solution is infeasible for the static robust model Static-R2, which means(12)∃d′∈U,∑i,j∈Adij′xij∗−∑i,j∈Adij′yij∗+∑j∈N∑k∈N+\jyjk∗−∑i∈N+\jyij∗d¯j0>L.
Denotedu=d+Θd^; according to the definition of the box uncertainty set U, we know that du∈U and du≽d′, where ≽ is the element-wise inequality. Based on inequality (12), it is clear that(13)∑i,j∈Adijuxij∗−∑i,j∈Adijuyij∗+∑j∈N∑k∈N+\jyjk∗−∑i∈N+\jyij∗d¯j0>L.
Denoted∗∈U as the optimal value of d that achieves optimal solution xij∗,yij∗ in the two-stage robust model Two-stage-R2; then,(14)∑i,j∈Adij∗xij∗−∑i,j∈Adij∗yij∗+∑j∈N∑k∈N+\jyjk∗−∑i∈N+\jyij∗d¯j0≤L,∑i,j∈Adij∗xij∗−∑i,j∈Adij∗yij′+∑j∈N∑k∈N+\jyjk′−∑i∈N+\jyij′d¯j0>L,∀y′∈Yandy′≠y∗,where Y=yij′≤yij∗,∀i,j,y′:∑i∈N+jyij′≤∑k∈N+\jyjk′,∀j,yij′∈0,1,∀i,j is the set which contains all recourse actions with less cancelled arcs compared with y∗.
Based on the fact thatdu≽d∗ and using inequality (14), we have(15)∑i,j∈Adijuxij∗−∑i,j∈Adijuyij′+∑j∈N∑k∈N+\jyjk′−∑i∈N+\jyij′d¯j0>L,∀y′∈Yandy′≠y∗.
Combining inequalities (13) and (15), we can observe that, for the second-stage problem R2x∗,du, the recourse action needs to cancel more arcs than y∗ to satisfy the length constraint, which means R2x∗,du<−∑j∈Nsj∑i∈N+\jyij∗. Because we are optimizing mind∈UR2x∗,d, y∗ is not the optimal second-stage solution, so this is a contradiction. Hence, the hypothesis cannot be established, which means xij∗,yij∗ is feasible for the static robust model Static-R2.
We conclude that the optimal solution of the two-stage robust model Two-stage-R2 is a feasible solution of the static robust model Static-R2. Because the two models have the same objective function value with the same solutions, the optimal solution of the two-stage robust model Two-stage-R2 is also the optimal solution of the static robust model Static-R2; this implies the two models are equivalent.Based on Theorem2, the two-stage robust model Two-stage-R2 can be solved to optimality by solving its corresponding static robust model Static-R2. Meanwhile, the Static-R2 model has much less decision variables and constraints compared with the Static-R1 model, which make it more practical to use.


## 4.3. The Relationship between Two-Stage-R1 and Two-Stage-R2 Models

Until now, we have introduced two two-stage robust models Two-stage-R1 and Two-stage-R2 and also proved that these two models are equivalent to their corresponding static robust models, respectively. In this section, we further investigate the relationships between Two-stage-R1 and Two-stage-R2.First, we investigate the static models Static-R1 and Static-R2. Comparing static model Static-R2 with static model Static-R1, model Static-R2 has less decision variables and less constraints and is computationally more attractive. The two static models are based on different recourse models. Next, we show that model Static-R1 and model Static-R2 are equivalent with the support of the box uncertainty set.Theorem 3.
The static robust models Static-R1 and Static-R2 are equivalent.Proof.
First, supposexij∗,xijk∗,yi∗,zk∗ is the optimal solution of the static robust model Static-R1, and we introduce decision variable yij which is defined in the Recourse2 model to model Static-R1; then, the optimal solution xij∗,xijk∗,yi∗,zk∗ can be mapped to an optimal solution xij∗,yij∗ of model Static-R1, and it is clear that xij∗,yij∗ is feasible to the static robust model Static-R2.
Then, supposexij∗,yij∗ is the optimal solution of the static robust model Static-R2, and we introduce variables xijk,yi,zk which are defined in the Recourse1 model to model Static-R2; then, the optimal solution xij∗,yij∗ can be mapped to an optimal solution xij∗,xijk∗,yi∗,zk∗ of model Static-R2, and we now show that xij∗,xijk∗,yi∗,zk∗ is feasible to the static robust model Static-R1.
SupposezK′∗=0 and zK′+1∗=1; then, this means the nodes in the first-stage path become unreachable from the K′+1th node. Then, length constraint (11d) in the static robust model Static-R2 is equivalent to(16)∑k=1K′∑i,j∈Adijxijk∗+∑i,j∈Ad¯j0xijK′∗≤L,∀d∈U.
Based on the definition of the box uncertainty setU, inequality (16) is equivalent to(17)∑k=1K′∑i,j∈Adij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′∗≤L.
We transform the left-hand side of the above inequality as follows:(18)∑k=1K′∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′∗=∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯ij+Θd^ijxijK′∗+∑i,j∈Ad¯j0xijK′∗≥∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯ij+d¯j0xijK′∗>1∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′−1∗,where relation 1 is due to the triangle inequality.
Based on (17) and (18), we have(19)∑k=1K′−1∑i,j∈Ad¯ij+Θd^ijxijk∗+∑i,j∈Ad¯j0xijK′−1∗≤L,which implies(20)∑k=1K′−1∑i,j∈Adijxijk∗+∑i,j∈Ad¯j0xijK′−1∗≤L,∀d∈U.
Following the above transformation recursively, finally, we can get(21)∑k=1K∑i,j∈Adijxijk∗+∑i,j∈Ad¯j0xijK∗≤L,∀K=1,...,K′,d∈U.
So, the optimal solutionxij∗,xijk∗,yi∗,zk∗ is feasible to the static robust model Static-R1.
We conclude that the optimal solution of the static robust model Static-R1 is a feasible solution of the static robust model Static-R2, and the optimal solution of the static robust model Static-R2 is a feasible solution of the static robust model Static-R1. Then, the two models have the same optimal solution; this implies the two models are equivalent.
The following corollary shows the equivalence between two two-stage robust models.Corollary 1.
The two-stage robust models Two-stage-R1 and Two-stage-R2 are equivalent.Proof.
Based on Theorems1, 2, and 3, we can draw this conclusion.
Based on Theorems1–3 and Corollary 1, we know that the four models Two-stage-R1, Static-R1, Two-stage-R2, and Static-R2 are equivalent to each other. It is an interesting conclusion that Two-stage-R1 and Two-stage-R2 are equivalent under the box uncertainty set even though they are based on different recourse models.In this section, we have established the two-stage robust optimization models for OPSW. First, we proved that the two-stage robust optimization models are equivalent to their corresponding static robust models. This is a very important conclusion since this indicates that the two-stage robust models can be solved by solving their corresponding static models. We can directly use some mathematical programming solvers (e.g., CPLEX) to solve the two-stage robust optimization models. Second, we proved that, with the box uncertainty set, Two-stage-R1 and Two-stage-R2 are equivalent. This is another important conclusion since this indicates that we can use a much simpler model (i.e., Recourse2 model) to get the same solution as the Recourse1 model. As we have discussed in the previous section, the Recourse1 model is more realistic, and this recourse model has been well studied in [1]. However, this model is very complex and is not preferable to use in practice. We introduced the Recourse2 model, and now, our theories support us to use the Recourse2 model instead of the Recourse1 model in our two-stage robust optimization models.


## 5. Case Study

In this section, a simple case study is presented to illustrate the effectiveness of the proposed two-stage robust models for OPSW.


### 5.1. Test Instance

The test instance used in our experiments is based on problem set 3 from [31] which was originally used for the deterministic OP. Problem set 3 contains 20 instances with the same 33 nodes and 20 varying length limits. We only consider 3 length limits: 80, 90, and 100. In the instance, the end point is ignored, and the start point is kept as the depot location. The problem set can be found at http://www.mech.kuleuven.be/en/cib/op.To generate the uncertain instances for OPSW, we use the Euclidean distances between nodes as the expected weightsd¯ij. Two kinds of uncertain instances are generated with the deviation values d^ij chosen as 0.2d¯ij and 0.5d¯ij, respectively. Then, based on different length limits and different deviation values, we can get a total of 6 uncertain instances for OPSW.


### 5.2. Experiments

In order to evaluate the effectiveness of the proposed two-stage robust models, we use the one-stage robust model for OPSW for comparison. In the one-stage robust model, all the decision variables are “here and now,” and there are no recourse decision variables considered in the model. The one-stage robust model follows the traditional RO paradigm and is formulated as follows.One-stage-RO:(22a)maximize∑i∈Nsi∑j∈N+\ixij,(22b)subject to1c−1g,(22c)∑i,j∈Adijxij≤L,∀d∈U.As proven inSection 4, the Static-R2 model is equivalent to the two-stage robust models Two-stage-R1 and Two-stage-R2 and is computationally more efficient than the Static-R1 model. So, we use the Static-R2 model to solve the two-stage OPSW with sequential or concurrent realized weights.We generate 1000 scenarios for thed^ij=0.2d¯ij and d^ij=0.5d¯ij cases, respectively, for simulation purposes. Suppose the uncertain weights d˜ij are uniformly distributed on interval d¯ij−d^ij,d¯ij+d^ij. Then, the realizations dij are sampled uniformly on the interval d¯ij−d^ij,d¯ij+d^ij.For each uncertain instance, the Static-R2 model and the One-stage-RO model are solved by CPLEX 12.6 withΘ=0,0.1,...,1, respectively. The java source code of using CPLEX to solve the models is provided in the supplementary material. The robust solutions obtained by the Static-R2 model and the One-stage-RO model are then simulated with the 1000 scenarios for the two-stage OPSW with Recourse1 and Recourse2 actions. The mean objective values and the standard deviations of the robust solutions are statistically summarized.


### 5.3. Numerical Results

We use the Static-R2 model instead of the Static-R1 model in our experiments. Here, we show a simple runtime comparison between Static-R1 and Static-R2 to illustrate that Static-R2 (i.e., with the new recourse model proposed in this paper) is much more efficient than Static-R1. We choose the instance withL=80 and d^ij=0.5d¯ij and set Θ=0.1. Then, the two models are solved by CPLEX. Their runtime is shown in Figure 2. We can clearly see that Static-R2 can be solved in 0.11 seconds, whereas Static-R1 needs 102.75 seconds to be solved. Our proposed model is 900+ times faster, which shows the great improvement in the computational time. The results in Figure 2 clearly suggest us to use Static-R2 in our experiments.Figure 2
Runtime comparison between Static-R1 and Static-R2. The instance is withL=80, d^ij=0.5d¯ij, and Θ=0.1.Tables1–6 show the numerical results of the 6 instances with different length limits and different deviation values. Obj. in the tables represents the objective value obtained by the One-stage-RO model or the Static-R2 model. First, we can observe that the objective values of the robust solutions are decreasing as parameter Θ increases for both one-stage and two-stage RO models. As Θ increases, the size of the uncertainty set U is increasing which means the protection level is increasing, and the resulting robust solution is more conservative.Table 1
Numerical results of the instance withL= 80 and d⌢ij= 0.2d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00710.00680.1941.66681.6341.43710.00693.7627.37695.2924.890.10690.00676.5228.56677.9327.62700.00691.5519.85692.4318.590.20690.00688.487.08688.826.36690.00685.6418.87685.7018.790.30680.00679.586.02679.586.02680.00679.931.38679.941.340.40670.00670.000.00670.000.00670.00679.771.50679.781.470.50660.00660.000.00660.000.00660.00660.000.00660.000.000.60650.00650.000.00650.000.00650.00650.000.00650.000.000.70640.00640.000.00640.000.00640.00640.685.17640.685.170.80630.00630.000.00630.000.00640.00640.000.00640.000.000.90630.00630.000.00630.000.00630.00630.000.00630.000.001.00620.00620.000.00620.000.00630.00630.000.00630.000.00Table 2
Numerical results of the instance withL= 80 and d⌢ij= 0.5d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00710.00652.4777.39657.9073.04710.00652.4777.39657.9073.040.10680.00662.9740.82664.2939.68680.00680.4125.69681.2624.960.20660.00658.718.26658.857.74660.00655.9117.83656.0517.580.30640.00639.832.07639.862.00640.00639.486.43639.546.150.40620.00620.000.00620.000.00630.00629.990.32629.990.320.50610.00610.000.00610.000.00610.00631.7119.40633.1119.230.60590.00590.000.00590.000.00600.00600.000.00600.000.000.70570.00570.000.00570.000.00580.00580.000.00580.000.000.80570.00570.000.00570.000.00570.00600.000.00600.000.000.90550.00550.000.00550.000.00560.00593.9324.90596.2528.571.00540.00540.000.00540.000.00550.00570.000.00570.000.00Table 3
Numerical results of the instance withL= 90 and d⌢ij= 0.2d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00770.00744.9635.74748.4433.24770728.1644.97729.6845.170.10760.00750.7425.94751.3325.31760754.0917.22754.4716.440.20750.00746.0917.02746.5116.21750752.6910.43752.939.900.30740.00739.802.36739.852.25740747.125.07747.264.810.40730.00730.000.00730.000.00730730.000.00730.000.000.50720.00720.000.00720.000.00720720.000.00720.000.000.60710.00710.000.00710.000.00710710.000.00710.000.000.70700.00700.000.00700.000.00710736.434.83736.714.740.80690.00690.000.00690.000.00690690.000.00690.000.000.90680.00680.000.00680.000.00690700.000.00700.000.001.00670.00670.000.00670.000.00680680.000.00680.000.00Table 4
Numerical results of the instance withL= 90 and d⌢ij= 0.5d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00770.00722.3458.05727.4657.50770719.9759.25725.5658.420.10740.00718.9948.56721.5643.38740730.8638.69733.3036.300.20720.00718.3710.40718.4310.37720716.0616.54716.7415.180.30690.00689.980.45689.980.45700699.832.88699.882.570.40670.00670.000.00670.000.00680683.8312.27684.1313.680.50650.00650.000.00650.000.00660679.901.18679.921.090.60640.00640.000.00640.000.00640701.2726.59702.8626.300.70620.00620.000.00620.000.00630630.000.00630.000.000.80610.00610.000.00610.000.00610650.0013.75650.2114.850.90600.00600.000.00600.000.00600649.8326.63652.7431.741.00580.00580.000.00580.000.00590604.8813.09608.5216.38Table 5
Numerical results of the instance withL= 100 and d⌢ij= 0.2d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00800795.397.86795.687.84800776.8845.66778.9941.130.10800798.065.57798.145.53800797.027.11797.207.050.20790789.831.86789.831.86790789.771.86789.781.830.30790789.980.45789.990.32790789.891.70789.891.700.40780780.000.00780.000.00790790.000.00790.000.000.50780780.000.00780.000.00780780.000.00780.000.000.60760760.000.00760.000.00770770.000.00770.000.000.70760760.000.00760.000.00760760.000.00760.000.000.80740740.000.00740.000.00750769.392.39769.482.220.90740740.000.00740.000.00740740.000.00740.000.001.00730730.000.00730.000.00730730.000.00730.000.00Table 6
Numerical results of the instance withL= 100 and d⌢ij= 0.5d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00800778.7943.57779.3443.51800787.0719.79787.6318.570.10790774.7240.31776.1338.69790776.0434.31778.0532.250.20780777.5014.56778.1012.25780778.718.64778.818.180.30750749.714.56749.774.15760759.723.15759.792.840.40730730.000.00730.000.00730749.273.57749.333.440.50710710.000.00710.000.00710710.000.00710.000.000.60690690.000.00690.000.00690719.752.29719.812.020.70670670.000.00670.000.00670718.0538.05720.0838.580.80650650.000.00650.000.00660720.000.00720.000.000.90630630.000.00630.000.00640650.000.00650.000.001.00620620.000.00620.000.00630640.000.00640.000.00For both one-stage and two-stage robust models, the mean objective values with concurrent recourse are greater than or equal to the corresponding mean objective values with sequential recourse. The reason is that the concurrent recourse has more information on the uncertainty realizations than the sequential recourse, so the concurrent recourse can make a better recourse decision and achieve a lower loss of the collected score. However, the gaps between the mean objective values with the sequential recourse and concurrent recourse are very small which means that the difference between the two recourse actions is small.Comparing the mean objective values of the one-stage RO and two-stage RO with the sequential recourse or concurrent recourse, the two-stage RO achieves better values than the one-stage RO in most cases. This is because that the two-stage RO considers the recourse decisions into the model, but the one-stage RO only considers the first-stage decisions. We also notice that the one-stage RO can achieve better mean objective values than the two-stage RO in some cases. Figures3–5 show visual comparisons between the one-stage RO and two-stage RO with the sequential recourse. The comparisons between the one-stage RO and two-stage RO with the concurrent recourse are visually similar. The figures clearly show that the two-stage RO dominates the one-stage RO in most cases, which shows the effectiveness and superiority of the proposed two-stage robust models for dealing with the two-stage OPSW.Figure 3
Comparison between the one-stage RO and two-stage RO with the sequential recourse,L=80: d^ij=0.2d¯ij (a); d^ij=0.5d¯ij (b).
(a)(b)Figure 4
Comparison between the one-stage RO and two-stage RO with the sequential recourse,L=90: d^ij=0.2d¯ij (a); d^ij=0.5d¯ij (b).
(a)(b)Figure 5
Comparison between the one-stage RO and two-stage RO with the sequential recourse,L=100: d^ij=0.2d¯ij (a); d^ij=0.5d¯ij (b).
(a)(b)In Tables1–6, we also report the standard deviations of the simulated robust solutions for both the one-stage RO and the two-stage RO. The standard deviations can reflect the stabilities of the obtained robust solutions. From the tables, we can see that, as parameter Θ increases, the standard deviations tend to decrease, which means the robust solutions are more stable with a larger uncertainty set. We can also observe that the two-stage RO can mostly achieve better mean objective values and lower or small standard deviation values at the same time compared with the one-stage RO. This further indicates that the proposed two-stage robust models can efficiently tackle the two-stage OPSW.


## 5.1. Test Instance

The test instance used in our experiments is based on problem set 3 from [31] which was originally used for the deterministic OP. Problem set 3 contains 20 instances with the same 33 nodes and 20 varying length limits. We only consider 3 length limits: 80, 90, and 100. In the instance, the end point is ignored, and the start point is kept as the depot location. The problem set can be found at http://www.mech.kuleuven.be/en/cib/op.To generate the uncertain instances for OPSW, we use the Euclidean distances between nodes as the expected weightsd¯ij. Two kinds of uncertain instances are generated with the deviation values d^ij chosen as 0.2d¯ij and 0.5d¯ij, respectively. Then, based on different length limits and different deviation values, we can get a total of 6 uncertain instances for OPSW.


## 5.2. Experiments

In order to evaluate the effectiveness of the proposed two-stage robust models, we use the one-stage robust model for OPSW for comparison. In the one-stage robust model, all the decision variables are “here and now,” and there are no recourse decision variables considered in the model. The one-stage robust model follows the traditional RO paradigm and is formulated as follows.One-stage-RO:(22a)maximize∑i∈Nsi∑j∈N+\ixij,(22b)subject to1c−1g,(22c)∑i,j∈Adijxij≤L,∀d∈U.As proven inSection 4, the Static-R2 model is equivalent to the two-stage robust models Two-stage-R1 and Two-stage-R2 and is computationally more efficient than the Static-R1 model. So, we use the Static-R2 model to solve the two-stage OPSW with sequential or concurrent realized weights.We generate 1000 scenarios for thed^ij=0.2d¯ij and d^ij=0.5d¯ij cases, respectively, for simulation purposes. Suppose the uncertain weights d˜ij are uniformly distributed on interval d¯ij−d^ij,d¯ij+d^ij. Then, the realizations dij are sampled uniformly on the interval d¯ij−d^ij,d¯ij+d^ij.For each uncertain instance, the Static-R2 model and the One-stage-RO model are solved by CPLEX 12.6 withΘ=0,0.1,...,1, respectively. The java source code of using CPLEX to solve the models is provided in the supplementary material. The robust solutions obtained by the Static-R2 model and the One-stage-RO model are then simulated with the 1000 scenarios for the two-stage OPSW with Recourse1 and Recourse2 actions. The mean objective values and the standard deviations of the robust solutions are statistically summarized.


## 5.3. Numerical Results

We use the Static-R2 model instead of the Static-R1 model in our experiments. Here, we show a simple runtime comparison between Static-R1 and Static-R2 to illustrate that Static-R2 (i.e., with the new recourse model proposed in this paper) is much more efficient than Static-R1. We choose the instance withL=80 and d^ij=0.5d¯ij and set Θ=0.1. Then, the two models are solved by CPLEX. Their runtime is shown in Figure 2. We can clearly see that Static-R2 can be solved in 0.11 seconds, whereas Static-R1 needs 102.75 seconds to be solved. Our proposed model is 900+ times faster, which shows the great improvement in the computational time. The results in Figure 2 clearly suggest us to use Static-R2 in our experiments.Figure 2
Runtime comparison between Static-R1 and Static-R2. The instance is withL=80, d^ij=0.5d¯ij, and Θ=0.1.Tables1–6 show the numerical results of the 6 instances with different length limits and different deviation values. Obj. in the tables represents the objective value obtained by the One-stage-RO model or the Static-R2 model. First, we can observe that the objective values of the robust solutions are decreasing as parameter Θ increases for both one-stage and two-stage RO models. As Θ increases, the size of the uncertainty set U is increasing which means the protection level is increasing, and the resulting robust solution is more conservative.Table 1
Numerical results of the instance withL= 80 and d⌢ij= 0.2d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00710.00680.1941.66681.6341.43710.00693.7627.37695.2924.890.10690.00676.5228.56677.9327.62700.00691.5519.85692.4318.590.20690.00688.487.08688.826.36690.00685.6418.87685.7018.790.30680.00679.586.02679.586.02680.00679.931.38679.941.340.40670.00670.000.00670.000.00670.00679.771.50679.781.470.50660.00660.000.00660.000.00660.00660.000.00660.000.000.60650.00650.000.00650.000.00650.00650.000.00650.000.000.70640.00640.000.00640.000.00640.00640.685.17640.685.170.80630.00630.000.00630.000.00640.00640.000.00640.000.000.90630.00630.000.00630.000.00630.00630.000.00630.000.001.00620.00620.000.00620.000.00630.00630.000.00630.000.00Table 2
Numerical results of the instance withL= 80 and d⌢ij= 0.5d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00710.00652.4777.39657.9073.04710.00652.4777.39657.9073.040.10680.00662.9740.82664.2939.68680.00680.4125.69681.2624.960.20660.00658.718.26658.857.74660.00655.9117.83656.0517.580.30640.00639.832.07639.862.00640.00639.486.43639.546.150.40620.00620.000.00620.000.00630.00629.990.32629.990.320.50610.00610.000.00610.000.00610.00631.7119.40633.1119.230.60590.00590.000.00590.000.00600.00600.000.00600.000.000.70570.00570.000.00570.000.00580.00580.000.00580.000.000.80570.00570.000.00570.000.00570.00600.000.00600.000.000.90550.00550.000.00550.000.00560.00593.9324.90596.2528.571.00540.00540.000.00540.000.00550.00570.000.00570.000.00Table 3
Numerical results of the instance withL= 90 and d⌢ij= 0.2d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00770.00744.9635.74748.4433.24770728.1644.97729.6845.170.10760.00750.7425.94751.3325.31760754.0917.22754.4716.440.20750.00746.0917.02746.5116.21750752.6910.43752.939.900.30740.00739.802.36739.852.25740747.125.07747.264.810.40730.00730.000.00730.000.00730730.000.00730.000.000.50720.00720.000.00720.000.00720720.000.00720.000.000.60710.00710.000.00710.000.00710710.000.00710.000.000.70700.00700.000.00700.000.00710736.434.83736.714.740.80690.00690.000.00690.000.00690690.000.00690.000.000.90680.00680.000.00680.000.00690700.000.00700.000.001.00670.00670.000.00670.000.00680680.000.00680.000.00Table 4
Numerical results of the instance withL= 90 and d⌢ij= 0.5d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00770.00722.3458.05727.4657.50770719.9759.25725.5658.420.10740.00718.9948.56721.5643.38740730.8638.69733.3036.300.20720.00718.3710.40718.4310.37720716.0616.54716.7415.180.30690.00689.980.45689.980.45700699.832.88699.882.570.40670.00670.000.00670.000.00680683.8312.27684.1313.680.50650.00650.000.00650.000.00660679.901.18679.921.090.60640.00640.000.00640.000.00640701.2726.59702.8626.300.70620.00620.000.00620.000.00630630.000.00630.000.000.80610.00610.000.00610.000.00610650.0013.75650.2114.850.90600.00600.000.00600.000.00600649.8326.63652.7431.741.00580.00580.000.00580.000.00590604.8813.09608.5216.38Table 5
Numerical results of the instance withL= 100 and d⌢ij= 0.2d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00800795.397.86795.687.84800776.8845.66778.9941.130.10800798.065.57798.145.53800797.027.11797.207.050.20790789.831.86789.831.86790789.771.86789.781.830.30790789.980.45789.990.32790789.891.70789.891.700.40780780.000.00780.000.00790790.000.00790.000.000.50780780.000.00780.000.00780780.000.00780.000.000.60760760.000.00760.000.00770770.000.00770.000.000.70760760.000.00760.000.00760760.000.00760.000.000.80740740.000.00740.000.00750769.392.39769.482.220.90740740.000.00740.000.00740740.000.00740.000.001.00730730.000.00730.000.00730730.000.00730.000.00Table 6
Numerical results of the instance withL= 100 and d⌢ij= 0.5d¯ij.
ΘOne-stage ROTwo-stage ROObj.SequentialConcurrentObj.SequentialConcurrentMeanStd.MeanStd.MeanStd.MeanStd.0.00800778.7943.57779.3443.51800787.0719.79787.6318.570.10790774.7240.31776.1338.69790776.0434.31778.0532.250.20780777.5014.56778.1012.25780778.718.64778.818.180.30750749.714.56749.774.15760759.723.15759.792.840.40730730.000.00730.000.00730749.273.57749.333.440.50710710.000.00710.000.00710710.000.00710.000.000.60690690.000.00690.000.00690719.752.29719.812.020.70670670.000.00670.000.00670718.0538.05720.0838.580.80650650.000.00650.000.00660720.000.00720.000.000.90630630.000.00630.000.00640650.000.00650.000.001.00620620.000.00620.000.00630640.000.00640.000.00For both one-stage and two-stage robust models, the mean objective values with concurrent recourse are greater than or equal to the corresponding mean objective values with sequential recourse. The reason is that the concurrent recourse has more information on the uncertainty realizations than the sequential recourse, so the concurrent recourse can make a better recourse decision and achieve a lower loss of the collected score. However, the gaps between the mean objective values with the sequential recourse and concurrent recourse are very small which means that the difference between the two recourse actions is small.Comparing the mean objective values of the one-stage RO and two-stage RO with the sequential recourse or concurrent recourse, the two-stage RO achieves better values than the one-stage RO in most cases. This is because that the two-stage RO considers the recourse decisions into the model, but the one-stage RO only considers the first-stage decisions. We also notice that the one-stage RO can achieve better mean objective values than the two-stage RO in some cases. Figures3–5 show visual comparisons between the one-stage RO and two-stage RO with the sequential recourse. The comparisons between the one-stage RO and two-stage RO with the concurrent recourse are visually similar. The figures clearly show that the two-stage RO dominates the one-stage RO in most cases, which shows the effectiveness and superiority of the proposed two-stage robust models for dealing with the two-stage OPSW.Figure 3
Comparison between the one-stage RO and two-stage RO with the sequential recourse,L=80: d^ij=0.2d¯ij (a); d^ij=0.5d¯ij (b).
(a)(b)Figure 4
Comparison between the one-stage RO and two-stage RO with the sequential recourse,L=90: d^ij=0.2d¯ij (a); d^ij=0.5d¯ij (b).
(a)(b)Figure 5
Comparison between the one-stage RO and two-stage RO with the sequential recourse,L=100: d^ij=0.2d¯ij (a); d^ij=0.5d¯ij (b).
(a)(b)In Tables1–6, we also report the standard deviations of the simulated robust solutions for both the one-stage RO and the two-stage RO. The standard deviations can reflect the stabilities of the obtained robust solutions. From the tables, we can see that, as parameter Θ increases, the standard deviations tend to decrease, which means the robust solutions are more stable with a larger uncertainty set. We can also observe that the two-stage RO can mostly achieve better mean objective values and lower or small standard deviation values at the same time compared with the one-stage RO. This further indicates that the proposed two-stage robust models can efficiently tackle the two-stage OPSW.


## 6. Conclusions

In this paper, we considered the orienteering problem with stochastic weights with recourse actions. Based on different uncertainty realization ways, we presented two recourse models: one is the Recourse1 model and the other is the Recourse2 model. The Recourse2 model has less decision variables and less constraints and is computationally more attractive. We applied the two-stage robust optimization paradigm to the orienteering problem with stochastic weights and introduced two two-stage robust optimization models based on two recourse models. We theoretically proved that, with the box uncertainty set defined, the two-stage robust models are equivalent to their corresponding static robust models, and the two two-stage robust models are also equivalent to each other. Subsequently, the two-stage robust models for the orienteering problem with stochastic weights can be solved to optimality by solving their corresponding static models. Comparative studies between the two-stage robust models and the one-stage robust model for the orienteering problem with stochastic weights showed the effectiveness and superiority of the proposed two-stage robust models for tackling the two-stage orienteering problem with stochastic weights.We provide the following research directions as our future works:(1)
The two-stage robust models for the orienteering problem with stochastic weights proposed in this paper are based on the box uncertainty set; therefore, we can draw theoretical conclusions on the equivalence between the two-stage robust models and their corresponding static robust models. Other uncertainty sets (e.g., the polyhedral uncertainty set) could be defined in the two-stage robust models, and the performance of the corresponding static robust models can be studied.(2)
The orienteering problem with stochastic weights considered in this paper is with a two-stage setting where the decision variables are classified into two categories. As the planned path is executed dynamically and the nodes are visited sequentially, the orienteering problem with stochastic weights can be viewed as a multistage decision-making problem. So, we can apply the multistage robust optimization methodology and build a multistage robust model for the orienteering problem with stochastic weights with a multistage setting.(3)
Currently, all the conclusions proved in this paper are problem-dependent, i.e., these conclusions are only applicable to the two-stage orienteering problem with stochastic weights. In the future, we will study if the conclusions can be applied to other problems, such as the traveling salesman problem and vehicle routing problem.



---

*Source: 5649821-2020-11-16.xml*