## 3 Lagrangian Relaxation-Based Solution Approach
### Dynamic Programming Algorithm  
In this subsection, we use a dynamic programming algorithm (Algorithm 2.) to solve the shortest route problem with time window constraints, which is a subproblem of the multi-task ISRPTWC, where the constructed time-space state network can nicely ensure that the time-dependent constraints are not violated. According to the time-discrete multi-commodity flow model in Section 2.4, we define \(L(\_,\_,)\) is denoted as the vertex \((\_,\_,)\), including \(L(\_,\_^{*},s_{d}^{*},w^{*})\) denoted as the starting node of task \(d\), and \(L\big{(}t_{d^{\prime}}^{*},e_{d^{\prime}}^{*},w^{*}\big{)}\) denoted as the termination node of task \(d\). The specific dynamic programming algorithm flow is as follows. Single-task ISRPTWC can be solved well by the dynamic planning algorithm, but it is difficult to check for task congestion during transmission, i.e., tasks are transmitted continuously on nodes with the same satellite attributes over multiple time slices. Therefore, we add the process of checking a task transmission route at the end of the dynamic planning algorithm. If a task transmission route causes congestion, we go back to the first congestion-generating node and recalculate its optimal route while avoiding using subsequent congested nodes. To ensure the optimality of the backtracking method, we combine it with the relevant theorem of the dynamic programming algorithm to prove it, as shown in Theorem 1. **Theorem 1**. : _If a transmission route of a task \(d\) reaches the upper limit of the congestion \(Blo_{d}\), it is sufficient to go back to the first node \((i,s,w)\) that caused the congestion on its optimal route \(S_{d}^{*}\) and modify the connection structure of node \(S_{d}^{*}(n)\) to recalculate its optimal route._  
Proof. : Suppose the current set of routes of the task \(d\) is \(\mathrm{D}_{d}\), the optimal sequence of task \(d\) is \(S_{d}^{*}\subseteq\mathrm{D}_{d}\), and the set of nodes causing congestion is \(\{(i,s,w),(i,s+1,w),\cdots,(i,s+Blo_{d},w)\}\subseteq S_{d}^{*}\). \(\square\)  
Taking node \((i,t,w),t\in[s,s+Blo_{d}]\) as the breakpoint. That is, the connection link \(l_{(i,t,w)}\) between \(\mathrm{node}(i,t-1,w)\) and node \((i,t,w)\) is destroyed, and the set of destroyed links is viewed to be \(\frac{\mathrm{D}}{l_{(i,t,w)}d}\). According to the no-aftereffect characteristic in dynamic planning, the optimality of the route \(\{(i,t,w),\cdots,destination\}\subseteq S_{d}^{*}\) is not affected in backward planning and thus does not need to be recalculated. However, the optimality of the route \(\{origin,\cdots,(i,t,w)\}\subseteq S_{d}^{*}\) is broken and needs to be recomputed. Moreover, we obviously know that the fewer route structures are destroyed, the smaller the impact on the routes \(\mathrm{D}_{d}\). Therefore, we must find the node that minimizes the damage while meeting the maximum congestion time constraint. That is, we must find the maximally effective routes (35). \[\max\left(\frac{\mathrm{D}_{eff}}{l_{(i,t,w)}d}\right),t\in[s,s+Blo_{d}] \tag{35}\]The effective route set \(\frac{D_{eff}}{l(i,\omega)_{d}}\) is both the set of routes that the task d can transmit from the origin node to the termination node. Therefore, we can obviously conclude that \(\frac{\mathrm{D}_{eff}}{l(i,\omega)_{d}}\subseteq\frac{\mathrm{D}_{eff}}{l(i-1 \omega)_{d}}\), so that the breakpoint \((i,t,w)=(i,s,w)\) can make \(\frac{\mathrm{D}_{eff}}{l(i,\omega)_{d}}\) maximize. In summary, the proof is over. ```
For each task \(d\in D\) do  calculate the set \(D_{d}\subseteq D_{*}\) of possible routes for the task \(d\);  // initialization of relevant parameters.