# A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Unmanned Aerial Vehicles
## 4 Our Sim-Learnheuristic Approach
If the new solution has a higher reward value (line 8), a short number of MCS runs are performed on the new solution to calculate its expected reward (line 9). In addition, if the newly generated solution obtains a higher expected reward (line 10), the best-known solution is updated and the new solution is added to the pool of elite solutions (lines 11-12). The computational time employed to generate new solutions is updated before checking if the maximum execution time (\(t_{max}\)) is reached (line 15). Once the stopping criteria are met, the algorithm conducts a refinement procedure using a larger number of MCS runs (\(n_{long}\)) over the pool of elite solutions (lines 17-22). This allows for more accurate estimations of the  
Figure 3: Schema of the sim-learnheuristic methodology. solutions in the elite pool. Finally, the solution with the highest expected reward is selected from the pool of elite solutions and returned by the algorithm (line 23). ```
1:\(initSol\leftarrow\)savingsHeuristic\((inputs)\)
2:simulation\((initSol,n_{short})\)
3:\(bestSol\gets initSol\)
4:add\((\mathit{eliteSols},bestSol)\)
5:\(time\gets 0\)
6:while\(time\leq t_{max}\)do
7:\(newSol\leftarrow\)savingsHeuristicBR\((inputs,\beta)\)
8:if\(reward(newSol)>reward(bestSol)\)then
9:simulation\((newSol,n_{short})\)
10:if\(expReward(newSol)>expReward(bestSol)\)then
11:\(bestSol\gets newSol\)
12:add\((\mathit{eliteSols},bestSol)\)
13:endif
14:endif
15:updateTime\((time)\)
16:endwhile
17:for\(sol\in eliteSols\)do
18:simulation\((sol,n_{long})\)
19:if\(expReward(sol)>expReward(bestSol)\)then
20:\(bestSol\gets sol\)
21:endif
22:endfor
23:return\(bestSol\)
```  
**Algorithm 1** Sim-learnheuristic algorithm  
Algorithm 2 depicts the main components of the savings-based heuristic. The heuristic starts by constructing a dummy solution (\(sol\)) with as many routes as nodes (line 1). Specifically, each route goes from the origin depot to a node before concluding its route at the destination depot. Notice that the constructed routes that exceed the maximum travel time are deleted from the solution. Then, the savings \(s_{i,j}\) associated with each edge connecting two different nodes \(i\) and \(j\) are generated as follows:  
\[s_{i,j}=\alpha\left(t_{0,j}+t_{i,n+1}-t_{i,j}\right)+(1-\alpha)\left(u_{i}+u_{j}\right) \tag{9}\]  
where \(t_{i,j}\) is the travel time between nodes \(i\) and \(j\), \(t_{i,n+1}\) is the travel time between node \(i\) and the destination depot, \(t_{0,j}\) is the travel time between the origin depot and node \(j\), \(u_{i}\) and \(u_{j}\) are the rewards at nodes \(i\) and \(j\), and \(\alpha\) is a parameter used to balance travel time and collected reward. Notably, each pair of nodes has two different savings, one for each direction or edge. The savings associated with each edge are sorted in descending order, from the highest to the lowest saving value (line 2). This sorted list of savings is iterated, and a merging process is started (lines 3-15). At each iteration, a savings edge is extracted from the list of savings, and the two routes associated with the savings edge are obtained (lines 4-6). These two routes are merged, and the resulting route is checked to see if the merge does not exceed the maximum travel time constraint (line 7). If the merge is feasible, the two routes are removed from the solution, and the merged route is inserted instead (lines 8-13). Once the merging process finishes, the routes are sorted based on their collected reward in decreasing order from higher to lower rewards (lines 16). Then, the number of routes equal to the number of vehicles in the fleet (\(v_{max}\)) constitutes the solution proposed by the heuristic (line 17). Finally, the resulting solution with the highest rewarded routes is returned by the procedure (line 18).