# A Sim-Learnheuristic for the Team Orienteering Problem: Applications to Unmanned Aerial Vehicles
## 4 Our Sim-Learnheuristic Approach
```
1:\(sol\leftarrow\)genDummySolution\((inputs)\)
2:\(savingsList\leftarrow\)genSortedSavingsList\((inputs,\alpha)\)
3:while\(savingsList\
eq\emptyset\)do
4:\(ijEdge\leftarrow\)selectNext\((savingsList)\)
5:\(iRout\leftarrow\)getOriginRoute\((ijEdge)\)
6:\(jRoute\leftarrow\)getEndRoute\((ijEdge)\)
7:\(newRoute\leftarrow\)mergeRoutes\((iRoute,jRoute)\)
8:\(isMergePossible\leftarrow\)checkMergeConditions\((newRoute)\)
9:if\(isMergePossible=\)truethen
10: deleteRoute\((sol,iRoute)\)
11: deleteRoute\((sol,jRoute)\)
12: addRoute\((sol,newRoute)\)
13:endif
14: deleteEdge\((savingsList,ijEdge)\)
15:endwhile
16: sortRoutesByProfit\((sol)\)
17: deleteRoutesByProfit\((sol,v_{max})\)
18:return\(sol\)
```  
**Algorithm 2** Savings-based heuristic  
The simulation process is depicted in Algorithm 3. The simulation procedure takes two input parameters: a solution (\(sol\)) and the number of simulation replications (\(n_{runs}\)) to estimate the performance of the solution under stochastic and dynamic conditions. In the procedure, a variable keeps track of the accumulated expected reward (\(sumReward\)), which is initialized to zero at the start of the simulation process (line 1). The simulation is run \(it_{max}\) times, and at each run, the expected reward of the solution (\(solReward\)) is added to the accumulated expected reward (lines 2-28). For each route in the solution, the route's expected reward (\(routeReward\)) is computed along with the route's expected cost (\(routeCost\)) (lines 4-26). If the expected route cost exceeds the maximum travel time, a penalty is applied to the route, resulting in a loss of all the collected rewards from the visited nodes (lines 22-24). To compute the route's expected reward, we iterate through the route's composing edges, and for each edge, we obtain its expected cost (lines 7-21). The expected cost of an edge is computed based on its deterministic, stochastic, or dynamic characteristics. The expected cost of a deterministic edge is predefined and specific to each particular instance (line 12). Moreover, the expected cost of a stochastic edge is sampled using a non-negative probability distribution, such as the Weibull or Log-Normal distributions, to simulate the uncertainty in the route plan (line 14). Finally, the expected cost of a dynamic edge is predicted using a multiple regression model considering the current dynamic conditions at this time (lines 16-17). Once the simulation replications are complete, the expected reward is computed as the average accumulated expected reward across all the simulation replications and is assigned as the expected reward of the solution (lines 29-30). ```
1:\(sumReward\gets 0\)
2:for\(i\in\{1,\dots,n_{runs}\}\)do
3:\(solReward\gets 0\)
4:for\(route\in\) getRoutes(\(sol\))do
5:\(routeReward\gets 0\)
6:\(routeCost\gets 0\)
7:for\(edge\in\) getEdges(\(route\))do
8:\(edgeCost\gets 0\)
9:\(node\leftarrow\)getEndNode(\(edge\))
10:\(type\leftarrow\)getType(\(edge\))
11:if\(type=\)DETERMINISTICthen
12:\(edgeCost\leftarrow\)getCost(\(edge\))
13:elseif\(type=\)STOCHASTICthen
14:\(edgeCost\leftarrow\)getStochasticValue(\(edge,varLevel\))
15:elseif\(type=\)DYNAMICthen
16:\(conditions\leftarrow\)getDynamicConditions(\(time\))
17:\(edgeCost\leftarrow\)getDynamicValue(\(edge,conditions\))
18:endif
19:\(routeCost\gets routeCost+edgeCost\)
20:\(routeReward\gets routeReward+\)getReward(\(node\))
21:endfor
22:if\(routeCost>routeMaxCost\)then
23:\(routeReward\gets 0\)
24:endif
25:\(solReward\gets solReward+routeReward\)
26:endfor
27:\(sumReward\gets sumReward+solReward\)
28:endfor
29:\(expReward\gets sumReward/it_{max}\)
30:setExpReward(\(sol,expReward\))
```  
**Algorithm 3** Simulation procedure