## 3 Lagrangian Relaxation-Based Solution Approach
### Lagrangian Relaxation Solution Procedure  
Although the time-discrete multi-commodity flow model can simplify the time-dependent constraints in multi-task ISRPTWC, the capacity constraints of nodes and links have been unresolved complex constraints. Meanwhile, if all node and link constraints are eliminated, the multi-task ISRPTWC becomes a set of single-task ISRPTWCs, and it can be calculated using the dynamic programming algorithm. Along this line, we reformulate the problem by relaxing this complex constraint (17) and (18) into the objective function and use the Lagrange multipliers, \(\lambda_{1}(n)\) and \(\lambda_{2}(e)\), to build the dual Lagrangian function (25). \[L= \sum\limits_{d\in D}\frac{1}{P\mu_{d}}\sum\limits_{(i,j,s,e,w,w^{ \prime})\in D_{d}}c(d,i,j,s,e,w,w^{\prime})y(d,i,j,s,e,w,w^{\prime}) \tag{25}\] \[+\sum\limits_{n\in N}\lambda_{1}(n)\left[\sum\limits_{d\in D}\sum \limits_{(i,j,s,e,w,w^{\prime})\in\Phi_{(j,e,w^{\prime})}}y(d,i,j,s,e,w,w^{ \prime})-Cap_{(j,e,w^{\prime})}\right]\] \[+\sum\limits_{e\in E}\lambda_{2}(e)\left[\sum\limits_{d\in D}y(d, i,j,s,e,w,w^{\prime})-Cap_{(i,j,s,e,w,w^{\prime})}\right]\]  
Therefore, the Lagrangian relaxation dual model (denoted as M3) can be expressed as follows. \[\text{Min }L \tag{26}\] \[\sum\limits_{(i,j,s,e,w,w^{\prime})\in D_{d}}y\big{(}d,i,j,s,e,w,w^ {\prime}\big{)}=1,\quad(i,s)=st_{i},\,w=w_{s},\forall d\in D\] (27) \[\sum\limits_{(i,j,s,e,w,w^{\prime})\in D_{d}}y\big{(}d,i,j,s,e,w,w ^{\prime}\big{)}=1,\quad(j,e)=ar_{i},\,w=w_{e},\forall d\in D\] (28) \[\sum\limits_{(j,w,^{\prime})}y(d,i,j,s,e,w,w^{\prime})-\sum \limits_{(i^{\prime},j^{\prime},w^{\prime})}y(d,i^{\prime},i,s^{\prime},s,w^ {\prime},w)=0,\,\,(i,s)\
otin\{st_{i},ar_{i}\},\] (29) \[w\
otin\{w_{s},w_{e}\},\forall d\in D\]  
\[y\big{(}d,i,j,s,e,w,w^{\prime}\big{)}\in\{0,1\}\quad\forall(i,j,s,e,w,w^{ \prime}\big{)}\in D_{d},\forall d\in D \tag{30}\]  
So far, we have obtained a set of single-task ISRPTWCs by the Lagrangian relaxation process. Then, we further process the function L to get the connection of Lagrange multipliers with node and link costs. The derivation process of the simplified function L and the simplified results are shown below. The links consist of a virtual link formed by nodes with the same satellite attributes in the front and back consecutive time slices and a physical link constructed by nodes with different satellite attributes in the front and back consecutive time slices, and there is no capacity limit for the virtual link. Thus, it is necessary to divide all links in function L into two categories. \[ \begin{array}{ll}L=&\sum\limits_{d\in D}\sum\limits_{(i,j,s,e,w,w^{\prime} )\in D_{d}}\frac{1}{P\mu_{d}}c(d,i,j,s,e,w,w^{\prime})y(d,i,j,s,e,w,w^{\prime} )+\sum\limits_{d\in D}\sum\limits_{(i,j,s,e,w,w^{\prime})\in\Gamma_{d}} \lambda_{1}(n)y(d,i,j,s,e,w,w^{\prime})\\ &+\sum\limits_{d\in D}\sum\limits_{(i,j,s,e,w,w^{\prime})\in A_{d}}\lambda_{1 }(n)y(d,i,j,s,e,w,w^{\prime})-\sum\limits_{n\in N}\lambda_{1}(n)Cap_{(j,e,w)}+ \sum\limits_{d\in D}\sum\limits_{(i,j,s,e,w,w^{\prime})\in D_{d}}\lambda_{2} (e)y(d,i,j,s,e,w,w^{\prime})\\ &-\sum\limits_{(i,j,s,e,w,w^{\prime})\in D_{d}}\lambda_{2}(e)Cap_{(i,j,s,e,w, w^{\prime})}\end{array}  \tag{31}\]  
Combining links with different attributes in function L.  
\[ \begin{array}{ll}L=\sum\limits_{d\in D}\sum\limits_{(i,j,s,e,w,w^{\prime}) \in\Gamma_{d}}y(d,i,j,s,e,w,w^{\prime})\times\left[\frac{1}{P\mu_{d}}c(d,i,j,s, e,w,w^{\prime})+\lambda_{1}(n)+\lambda_{2}(e)\right]\\ +\sum\limits_{d\in D}\sum\limits_{(i,j,s,e,w,w^{\prime})\in A_{d}}y(d,i,j,s,e, w,w^{\prime})\times\left[\frac{1}{P\mu_{d}}c(d,i,j,s,e,w,w^{\prime})+\lambda_{1}(n)+ \lambda_{2}(e)\right]\\ -\left[\sum\limits_{n\in N}\lambda_{1}(n)Cap_{(j,e,w^{\prime})}-\sum\limits_{( i,j,s,e,w,w^{\prime})\in D_{d}}\lambda_{2}(e)Cap_{(i,j,s,e,w,w^{\prime})}\right]\end{array}  \tag{32}\]  
Let \(\xi(d,i,j,s,e,w,w^{\prime})=\frac{1}{P\mu_{d}}c(d,i,j,s,e,w,w^{\prime})+ \lambda_{1}(n)+\lambda_{2}(e)\) be the new transmission cost.