# Mobile Data-Mule Optimal Path Planning for Wireless Sensor Networks
## 1 Introduction
Similarly, the authors of [23] formulated an OP with time windows (OPTW) where the timestamp \(x_{ijt}\) is added to all transitions \(x_{ij}\) between nodes \(i\) and \(j\). The advocated problem counts a transition if it occurs within its assigned time window, and thus the optimization problem can be viewed as a time-connectivity formulation rather than in terms of minimum route length. The aforementioned MILP problems for a single MoEl do not account for the service time/visiting duration to a location, nor is there a constraint that imposes the route to start and end at the same depot node and thus cannot easily be extended to repeatable extraction of consecutive paths for one MoEl or a fleet with \(M\) MoEls. Reference [24] formulates the underlying TSP so as to minimize the duration of a route, along with the service time that is spent on the visited locations/nodes. Other path planning formulations, which take into consideration the time windows for the visiting nodes, are examined as Time-Dependent [23; 24], where the MoEl waits for a time interval after it visits a node and before it visits the next node, so as to be synchronized with the time window of the node that follows. This case results in additional delays, along with higher energy consumption for the MoEl. Rather than formulating the problem as a TSP, OP, or variations, the need to revisit nodes necessitates a different approach similar to [25], where a message ferrying algorithm that accounts for sensors' buffer overflow is presented. A similar approach, that of [6], utilizes a MES scheme, where the objective is the elimination of data loss due to the sensors' hardware limitation. In the case of the Multiple TSP (MTSP) using several MoEls, different heuristic approaches have been proposed in the literature due to the problem's issues with increased dimensionality. Reference [26] presents a heuristic approach, where one function minimizes the longest tour length, while a second one minimizes the total length of all tours. A learning-based approach to optimize the MTSP is presented in [27], which indirectly addresses the prohibitive combinatorial increase in the search space. The reduction of the MTSP search space's complexity is divided into two parts: the first assigns locations to agents and the other to small-scale TSP planning, resulting in suboptimal solutions. In [28], in order to avoid the exhaustive search of an exact solution over an MTSP, the number of locations to be visited is initially partitioned into several groups. Then, each group is assigned to a single agent, for which the shortest path between the locations of the assigned group has to be found using TSP solvers. Ref. [29] presents the formulation of a TSP with profits that consider priority prizes as an MILP; this generates itineraries that maximize the total value of the attractions/locations visited and minimizes the total travel cost involved. Only one route is extracted, and the priorities are not introduced as visiting deadline constraints in the problem to ensure that the prioritized locations are visited early in the extracted route. In [30], the revisit period constraint is introduced for a set of task locations that need to be inspected by a group of MoEIs. In this routing problem, the gathering of data from a set of specified locations and their delivery to a control station is considered. Given each task's priority, a different refresh rate is imposed for each task. Then, the objective for each MoEI is to minimize the maximum of the delivery times of all the tasks' data to the single control station (depot), while also satisfying each task's revisit period constraint. This problem differs from the Persistent Intelligence, Surveillance, and Reconnaissance (PISR) problem in the sense that the constraints are not dictated by the MoEI (UAV in the current case) but by the tasks that the MoEI visits. Nevertheless, a critical assumption of this work is that each task is serviced by the same MoEI in the consecutive routes.