## 2 System Background and Related Work  
In this section, we summarize research work related to trajectory planning of mobile nodes. Using mobile sinks to collect data has been a hot topic in Wireless Sensor Networks (WSNs). Ref. [15] tries to determine the constant velocity of the mobile sink with a fixed-mobility pattern so that data collection throughput can be maximized. Ref. [16] addresses the problem of finding an optimal path for the mobile sink to collect packets from each sensor such that the total energy use is minimized and is subject to the length constraint. Ref. [17] studies the problem of controlling sink mobility in event-driven applications to achieve a maximum network lifetime by a convex optimization model inspired by the support vector regression technique. Ref. [18] considers a delivery latency minimization problem (DLMP) in a randomly deployed WSN and solves it using the traversed anchor points on the border of the communication range of sensor nodes to shorten the travel path, along with the movement of the mobile sink. All of these works focus on the shortest path under different conditions. In [19], a framework is built for investigating the joint sink mobility and routing problems by constraining the sink to a finite number of locations. They formally prove the NP-hardness of the problem. They also investigate the induced subproblems. In particular, they develop an efficient primal-dual algorithm to solve the subproblem involving a single sink and then generalize the algorithm to approximate the original problem involving multiple sinks. Some work [20] considers the constrained path of the mobile sink while our work considers the constrained timing allowance. [PERSON] [21] considers the obstacle constraints in the mobile sink path scheduling. However, it is still a case of location constraints. To harvest the full potential of nodeats mobility, [PERSON] [22] presents an algorithm to allow sensor nodes to select the mobile sink that offers the best service for the longest period. In the approach, the data still needs go through a few relays to reach the mobile sink. Some research has been done about the TSP problem with a time window that looks very similar to our work. In [12], the authors propose the time-constrained TSP problem where each city must be visited during a time window. They use a parallel 2-exchange local search algorithm and extend it to multiple time windows. The algorithm can run on a multi-processor computer and achieve the time complexity of \(O(\log^{2}n)\). As well as the time window, [PERSON] et al. [13] also consider the precedence constraints which require ports being visited sequentially in a real ship scheduling scenario. They proposed a forward dynamic programming algorithm and proved that it works efficiently. In [14],a multi-traveling salesman problem with a time window and precedence constraints are further considered. The author claims that the problem is NP-hard and proposes the Linear Programming relaxation of the set partitioning formulation by column generation. Then, a special branch-and-bound scheme is employed to solve the integer set partition formulation. The algorithm is capable of optimally solving 30 customer problems. [PERSON] et al. [23] consider the decaying of the data value in an underwater sensor network. They try to find the trajectory and floating spots that can maximize the value of the data collection. However, the problem proposed in our paper is quite different from these related works. First, we do not require the trajectory of the mobile sink to be a loop. Second, the graph keeps changing along the time scale. Third, the object is not to find the shortest path but to visit as many UGVs as possible in a period. To find the minimal number of vehicles needed to serve the set of locations in a _multiple traveling salesman problem with time windows_ (m-TSPTW) [24], two precedence graphs are introduced as well as algorithms to find a lower and an upper bound.