## 3 Lagrangian Relaxation-Based Solution Approach
### Feasible Solution Generation Methods
\begin{table}
\begin{tabular}{p{42.7 pt} p{113.8 pt}} \hline \hline \multicolumn{2}{c}{**Symbol**} & \multicolumn{1}{c}{**Definition**} \\ \hline \(D_{d},D_{d}^{\prime}\) & \(D_{d}\) represents the current set of routes of task \(d\)  and \(D_{d}^{\prime}\) represents the set of routes of task \(d\) after removing the nodes and links in the set of violated constraints corresponding to \(x_{dk}=1\). \\ \(N_{dl}\) & \(N_{dl}\) represents the route cost of the optimal route for task \(d\) under \(D_{d}\). \\  & \(N_{dl}^{*}\) represents the route cost required for the optimal route \(l\) of task \(d\) under \(D_{d}^{\prime}\); \(N_{dl}^{\prime}\) represents the degree of influence of the optimal route \(l\) of task \(d\) under \(D_{d}^{\prime}\) on the optimal route of other data; \(N_{dl}=N_{dl}^{*}+N_{dl}^{\prime}\) represents the total cost of task \(d\) after modifying the optimal route. \(l\in\left[1,2^{|p_{d}|+|b_{d}|}-1\right]\) \\ \(N_{d}\) & \(N_{d}\) represents the set of route costs for task \(d\). \\ P, B & P, B represent the set of nodes and the set of links that violate the constraints, respectively. \\ \(\mathrm{p}_{d},b_{d}\) & \(\mathrm{p}_{d},b_{d}\) represent the set of nodes and the set of links for which the optimal route scheme of task d violates the constraints. \(P_{d}\subseteq P,b_{d}\subseteq B\) \\ \(Cap_{(i,s,\omega)}\), \(Cap_{(i,j,s,\omega,w^{\prime})}\) & \(Cap_{(i,j,s,\omega,w^{\prime})}\) represent the node capacity and link capacity, respectively. \\ \(\Gamma_{(i,s,w)}\) & The set of tasks that violate the node \((i,s,w)\) constraint. \\ \(Y_{(i,j,s,\omega,w^{\prime})}\) & The set of tasks that violate the link \((i,j,s,e,w,w^{\prime})\) constraint. \\ \(x_{dk}\) & represents whether the kth node or link in the set of routes of task \(d\) that violates the constraint is removed, \(k\in[0,|p_{d}|+|b_{d}|-1]\). \\ \(y_{dl}\) & \(y_{dl}\) represents the \(l\)th route in the set of routes for task \(d\) that is used. If \(y_{d0}=1\), the optimal route is selected, \(l\in\left[1,2^{|p_{d}|+|b_{d}|}-1\right]\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Sets, parameters, variables. decision variable \(y_{d1}\) is 1. In other words, the selected route scheme is computed in \(D^{\prime}_{d}\) of the node or link corresponding to the deletion constraint \(x_{d4}\). The range of values of the decision variables is defined in constraints (40) and (41). We use the CPLEX solver to solve the M4 model. Although the solutions obtained from the integer linear model are not feasible, it certainly converges toward the direction of constructing feasible solutions. Thus, with a reasonable time, we can repeat the construction of the M4 model and solve it using the solver. 1. Heuristic methods to construct feasible solutions  
Although the M4 model has largely reduced the number of nodes and links that violate the capacity constraint, the obtained route schemes are still not feasible solutions. Therefore, in this section, we design heuristics for feasible solution construction. The purpose of the constructed M4 model is to reduce the constraints as much as possible while controlling the route cost. However, in contrast to the M4 model idea, the main idea of the heuristic methods is to reduce the route cost as much as possible while eliminating the nodes and links that violate the constraints. In the process of constructing the feasible solution, we analyze the relationship between the two types of costs of the suboptimal route and the two types of costs of the optimal route of a task. Then, different processing strategies apply to different situations. The specific steps are as follows. Step1: Obtain the set of task routes, and calculate the optimal route and the number of constraint violations for each task. Step2: Calculate the suboptimal route and the degree of global impact for each task. Step3: Compare the suboptimal route cost and global impact degree of each task, find the optimal task adjustment scheme, and record this adjustment scheme into the tabu table to prevent subloops.