## 3 Lagrangian Relaxation-Based Solution Approach
### Feasible Solution Generation Methods  
Since the optimal route for a single task is computed by a dynamic planning algorithm without considering capacity constraints, this solution is essentially infeasible in multi-task ISRPTWC. Therefore, we design some rules to adjust the infeasible solutions into feasible ones. Current studies [42; 43; 44] involve the construction of feasible solutions using methods that are basically heuristic rule constructions. However, it is difficult to construct a tight upper bound by heuristic rules. To address this problem, we newly combine heuristic rules with an integer linear programming model to find feasible solutions to ensure computational efficiency. Specifically, we view the feasible solution construction process as a new combinatorial optimization problem. (1) Enhanced lower bound solution for integer linear model  
As shown in Figure 5, the transmission routes of the tasks may exist with partial overlap due to the capacity constraints of nodes and links, which leads to violating the capacity constraints. Therefore, we first compute the set of nodes P and the set of links B that violate the constraints in all task route schemes. Then, we define the \(D_{d}\) as a set of the current routes of the task \(d\), \(D_{d}^{\prime}\) as the set of routes obtained by removing some nodes and links in the set of capacity constraints violated by task \(d\), and the route computed in \(D_{d}\) is called the optimal route scheme of task \(d\), and the route computed in \(D_{d}^{\prime}\) is called the suboptimal route scheme of task \(d\). The route cost \(N_{40}\) of the optimal route solution for task \(d\) is known, and we define the cost \(N_{4l}\) of the suboptimal route solution for task \(d\) to consist of two parts, including its cost \(N_{4l}^{*}\) incurred in \(D_{d}^{\prime}\) and the degree of global impact \(N_{4l}^{\prime}\) of the new route, in which the degree of the global impact is mainly the impact of the new route scheme of task d on other task route schemes. This effect causes other nodes and links that do not violate the constrained routes to violate the capacity constraint due to modified task routes. Thus, the feasible solution construction problem is how to find routes for each task that reduce the number of nodes and links that violate the constraint while increasing the total route cost as little as possible. The specific sets, parameters, and decision variables are shown in Table 5.  
This integer linear programming model (denoted as M4) is formulated as follows. \[Min\sum_{d\in D}\sum_{I\in[0,2]^{|p_{d}|+|b_{d}|}}y_{dl}N_{dl} \tag{36}\]  
\[\sum_{d\in\Gamma_{(i,\omega,\omega)}}x_{d,(i,s,w)}=Cap_{(i,s,w)},\forall(i,s,w)\in P \tag{37}\]  
\[\sum_{d\in Y_{(i,j,s,\omega,w^{\prime})}}x_{d,(i,j,s,\omega,w^{\prime})}=Cap_{( i,j,s,\omega,w^{\prime})},\forall(i,j,s,e,w,w^{\prime})\in B \tag{38}\]  
\[\sum_{k\in[0,|p_{d}|+|b_{d}|-1]}2^{k}x_{dk}=\sum_{l\in[0,2^{|p_{d}|+|b_{d}|}-1]} y_{dl}l,\ \ \ d\in D \tag{39}\]  
\[\sum_{l\in[0,2^{|p_{d}|+|b_{d}|}-1]}y_{dl}=1,\ \ d\in D \tag{40}\]  
\[x_{dk},y_{dl}\in\{0,1\},d\in D,k\in[0,|p_{d}|+|b_{d}|-1],\ l\in\left[0,2^{|p_{ d}|+|b_{d}|}-1\right] \tag{41}\]  
The objective function (36) expresses the lowest total route cost for all tasks. Constraints (37) and (38) are to eliminate the nodes and links that currently violate the capacity constraint, respectively. Constraint (39) represents the relationship between the decision variables \(y_{dl}\) and \(x_{dk}\) taking values. For example, task \(d\) has five links and nodes that violate the constraints. When \([x_{d0},x_{d1},x_{d2},x_{d3},x_{4d}]\) of task \(d\) is [0,0,0,0,0,1], then the current  
Figure 5: Explanation of tasks transmission route.