# A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Unmanned Aerial Vehicles
## 3 Problem Definition  
The TOP is an NP-hard optimization problem [1], with a formal definition on a directed graph \(G=(V,A)\). The graph has \(V=\{0,1,2,\ldots,n+1\}\) nodes, where the origin depot is node 0, the destination depot is node \(n+1\), and \(N=\{1,\ldots,n\}\) are the intermediate nodes. The edges in \(A=\{(i,j)|i,j\in V,i\
eq j\}\) represent the connections between the nodes. We consider a set of homogeneous UAVs denoted as \(D\), and each UAV \(d\in D\) begins its journey from the origin depot, serves a subset of intermediate nodes, and finally reaches the destination depot. The objective is to maximize the total reward collected by all UAVs. Following the mixed-integer linear programming model for the TOP proposed by [12], the hybrid version of the problem, where the travel times are either deterministic, stochastic, or dynamic, can be expressed formally as follows:  
\[\max\sum_{d\in D}\sum_{(i,j)\in A}u_{j}x_{ij}^{d} \tag{1}\]  
where the objective is to maximize the aggregated deterministic reward of visited nodes over the set of edges. For each visited node in the route, it yields a reward \(u_{i}\geq 0\). Note that these rewards are zero for both the origin and destination depots, while they hold strictly positive values for the customers. More specifically, for each edge \((i,j)\in A\) and each UAV \(d\in D\), we consider the binary variable \(x_{ij}^{d}\), which is equal to 1 if UAV \(d\) traverses through edge \((i,j)\), and takes the value 0 otherwise. Below are the provided constraints with their explanations. In the course of the tour, each point is visited at most once to ensure that no point is revisited (2). \[\sum_{d\in D}\sum_{i\in V}x_{ij}^{d}\leq 1\quad\forall j\in N \tag{2}\]  
The variable \(y_{i}^{d}\) is introduced to indicate the position of node \(i\) in the tour made by vehicle \(d\), and constraint (3) makes sure that there are no sub-tours. \[y_{i}^{d}-y_{j}^{d}+1\leq(1-x_{ij}^{d})\mid N\mid\quad\forall i,j\in N,\ \forall d\in D \tag{3}\]  
Constraint (4) states that the total travel time of each vehicle should not be more than its threshold (\(T_{max}\)), since each UAV \(d\in D\) starts its route and can only serve some intermediate nodes due to the limited travel time. The total travel time is the sum of the travel times of deterministic, dynamic, and stochastic edges, which are included in \(A_{det}\), \(A_{dyn}\), and \(A_{stoch}\), respectively. These are disjoint sets that include all the edges of set \(A\). For each edge \((i,j)\in A_{det}\), we assume that the travel time of each edge is deterministic and predefined (\(t_{ij}=t_{ji}>0\)). Similarly, for each edge \((i,j)\in A_{stoch}\), we assume the travel time \(T_{ij}\) is stochastic and can be modeled using a probability distribution function. Lastly, for each edge \((i,j)\in A_{dyn}\), we assume the travel time \(\hat{t}_{ij}\) is dynamic, which depends on various factors such as weather and traffic conditions. Since the stochastic and dynamic travel times bring in a level of uncertainty, this constraint introduces a probabilistic approach to account for such unpredictability in travel times. The parameter \(\gamma\), which ranges between 0 and 1, represents a threshold that defines the acceptable level of probability for keeping the travel time within the specified travel limit. \[P\left(\sum_{(i,j)\in A_{det}}t_{ij}x_{ij}^{d}+\sum_{(i,j)\in A_{dyn}}\hat{t }_{ij}x_{ij}^{d}+\sum_{(i,j)\in A_{stoch}}T_{ij}x_{ij}^{d}\leq T_{max}\right) \geq\gamma\quad\forall d\in D \tag{4}\]  
Constraint (5) ensures that for every arrival at a node, there is a corresponding departure from that node. \[\sum_{i\in V}x_{ij}^{d}=\sum_{h\in V}x_{jn}^{d}\quad\forall d\in D\qquad \forall j\in N \tag{5}\]Constraint (6) indicates that the tour always commences at the starting node 0 and ends at the ending node \(n+1\). \[\sum_{j\in N}x_{0 jd}=\sum_{j\in N}x_{j(n+1)d}=1\qquad\qquad\forall d\in D \tag{6}\]  
Constraints (7) and (8) refer to the nature of \(y_{j}^{d}\) and \(x_{ij}^{d}\) variables.