## 1 Introduction
### Literature Review of Exact Solution Methods on Routing Problems  
To the extent of our knowledge, few studies have focused on the applicability of exact solution methods to the inter-satellite routing problem with time windows and capacity constraints (ISRPTWC). However, the vehicle routing problem with time windows (VRPTW) [24] problem and the vehicle routing problem with pickup and delivery (VRPTD) [25; 26] problem have been studied, and a large number of exact solution algorithms have been proposed. In this work, the ISRPTWC refers to optimizing the transmission routes and schedules of tasks without violating all satellites and links capacity constraints, in which the schedule refers to specifying the upload start time and downlink termination time for each task. Without considering multi-tasks scenarios, ISRPTWC and vehicle routing problems with pickup and delivery with time windows (VRPTDTW), which VRPTDTW consists of optimizing a set of vehicle routes and schedules with known passenger demand without violating vehicle capacity constraints, are essentially sequential combinatorial optimization problems with complex constraints.  
Based on VRPPDTW, some applications have been extended in maritime, air, and road transportation, in which the studies related to maritime routing and scheduling [27; 28], air cargo routing and scheduling [29], and road freight routing and scheduling [30; 31] are well known. School bus routing and scheduling [32] and ridesharing [33; 34] are also of great interest in recent years' research on VRPPDTW. These research methods are useful for solving ISRPTWC. Considering the single-vehicle pickup and drop-off problem with time windows (PDPTW), [PERSON] [35] developed an exact forward dynamic programming solution to minimize the waiting time and service time for all passengers. [PERSON] et al. [36] applied the Benders' decomposition method to handle the main routing problem and the scheduling subproblem for the single-vehicle PDPTW. Later, many researchers changed their focus from single-vehicle PDPTW to multi-vehicles PDPTW. [PERSON] et al. [37] proposed an algorithm combining heuristics in which the primary objective was to minimize the number of demanded vehicles, and the secondary objective function was to minimize the route cost. [PERSON] et al. [38] proposed a double exponential formulation and used a branch-and-cut algorithm to solve the multi-vehicles PDPTW. [PERSON] [39] developed a novel branch-and-cut-and-price algorithm in which the lower bound was computed using a column generation algorithm, and various inequalities were designed to improve the computational efficiency. [PERSON] et al. [40] and [PERSON] et al. [41] considered the route congesting case in the multi-vehicle PDPTW and solved it using a directed graph approach. [PERSON] et al. [42] designed an exact solution framework to solve VRP-PDTW considering traffic congestion cases, in which they first developed a discrete-time multi-commodity flow model and decomposed the problem into the main problem and single-vehicle PDPTW subproblems, then solved the subproblem using dynamic programming methods in a Lagrangian relaxation framework, and finally validated it in Chicago sketch and Phoenix regional network.  
Combining the above methods and considering the complex space environment of the mega constellation, we use the space-time network scheme to construct the time-space state network for ISRPTWC. The constructed time-space state network can easily represent a task upload window and downlink. Also, the introduced time-space state network ensures that we can use the dynamic programming algorithm to solve the single-task ISRPTWC. For the multi-task ISRPTWC, we use the Lagrangian relaxation framework to decompose the original problem into a series of sub-problems with time window constraints by relaxing the satellite and linking capacity-related constraints into the objective function and design subgradient methods to update the Lagrangian multipliers.