## 6 Conclusions  
In the context of satellite-ground integration, we investigate the inter-satellite routing problem for low-orbit mega-constellations to design an exact solution to solve it. Thus, we propose a multi-task large-scale inter-satellite routing problem with time windows and capacity constraints (ISRPTWC) and design a Lagrange relaxation solution framework combined with the dynamic programming approach in a time-space state network to solve the ISRPTWC. Frankly, multi-task ISRPTWC is actually a minimum-cost route planning problem considering task time window constraints and inter-satellite network capacity constraints. In this study, we first build an integer linear programming model of the problem to solve it. However, the problem is almost impossible to solve directly using the solver. Therefore, we reformulate this problem in the constructed time-space state network and propose a time-discrete multi-commodity flow model which can well explain the time, space, and state properties of a task. Additionally, we find that multi-task ISRPTWC is a set of single-task ISRPTWC if capacity constraints are not considered because the single-task ISRPTWC can use a dynamic programming approach to solve it. Therefore, we further propose a Lagrangian relaxation framework to relax the capacity constraint into the objective function by Lagrangian multipliers and design subproblem-solving methods and feasible solution construction methods. Notably, to obtain a high-quality feasible solution, we propose a new idea to consider a feasible solution construction process as a new combinatorial optimization problem and design an integer linear programming model and heuristic rules to combine to solve it. Finally, we validate the proposed algorithm using illustrative cases, randomly generated cases, and real-world, large-scale network cases. The computational results show that our algorithm can solve the optimal solution of the multi-task ISRPTWC. In conclusion, this algorithm provides a new idea for solving multi-mission ISRPTWC, which is simple and reliable and can be applied to more complex inter-satellite routing problems. Our future research will focus on the following three areas: (1) considering more complex inter-satellite routing problems in satellite networks, such as multi-layer satellite networks and heterogeneous satellite networks; (2) considering more complex task requirement constraints, such as certain tasks can only be transmitted between specific satellites; (3) applying the idea of feasible solution construction to solve other types of transportation problems in combination with related exact solutions. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Scenario** & \(\mathbf{LB}^{*}\) & \(\mathbf{UB}^{*}\) & **Gap\%** & \begin{tabular}{c} **Number of** \\ **Iterations** \\ \end{tabular} & \begin{tabular}{c} **CPU Running** \\ **Time (s)** \\ \end{tabular} & \
\begin{tabular}{c} **Violated Node** \\ **Constraints** \\ \end{tabular} &
\begin{tabular}{c} **Violated Link** \\ **Constraints** \\ \end{tabular} \\ \hline MediumScale\_I & 5492.61 & 5493.40 & 0\% & 31 & 1658.687 & [4832] & Null \\ MediumScale\_II & 8420.76 & 8422.13 & 0\% & 30 & 2069.711 & [5357] & Null \\ LargeScale\_I & 9030.03 & 9040.10 & 0.11\% & 32 & 3886.633 & [6214,7537,4726] & Null \\ LargeScale\_II & 13,066.90 & 13,074.37 & 0\% & 25 & 4372.879 & [7943,9731] & [8444,9483], [8994,9894]] \\ \hline \hline \end{tabular}
\end{table} 
Table 13: Real-world case experiment results. **Author Contributions:** Conceptualization, J.L. and L.X. ; methodology, J.L. ; software, W.Q. ; validation, J.L. and G.Z. ; resources, Y.C. ; data curation, G.Z. ; writing--original draft preparation, J.L. ; writing--review and editing, L.X. and W.Q. ; visualization, J.L. ; supervision, Y.C. ; funding acquisition, L.X. All authors have read and agreed to the published version of the manuscript.