# Optimization of Truck-Drone Parcel Delivery Using Metaheuristics
## 2 Proposed Greedy Randomized Adaptive Search Procedure for TSP-D
### Algorithm Details
#### 2.2.2 Optimizing the Obtained Solution with Local Search  
The LS procedure helps to improve the initial TSP-D solution by applying two different moves: \(Swap\) and \(TwoOpt\)[10]. The LS procedure is explained, followed by a description of the two moves. A general structure for the LS procedure is shown in Algorithm 4. After the initialization step, an iterative process starts. In each iteration, either the \(Swap\) or \(TwoOpt\) move is selected in a self-adaptive manner, based on the move probability, \(p_{m}\), as follows (lines 7-12). A random number, \(rand\in[0,1]\), is generated. If the value of \(rand\) is less than \(p_{m}\), the \(Swap\) move is selected; otherwise, the \(TwoOpt\) move is selected. The selected move is applied to the current solution, \(tspd\). If the resulting neighbor has a lower cost, the move is accepted. Otherwise, the acceptance criterion is tested. The success ratio of the chosen  
Figure 4: \(PushLeft\) move: (**a**) displays the current solution before applying \(PushLeft\); and (**b**) displays the solution after applying \(PushLeft\). move is updated. The procedure is repeated until the termination condition or _convergence_ is reached. ```
1\(j=0\);
2 initialize loop control parameters;
3 while(termination condition not satisfied and \(j<\) convergence)do
4 if(windowSize iterations have elapsed)then
5 update \(p_{m}\) based on Equation (5);
6
7 end if
8\(rand\)=generate a random number \(\in[0,1]\);
9 if(\(rand<p_{m}\))then
10 apply swap move to \(tspd\) and update its success ratio;
11 else
12 apply twoOpt move to \(tspd\) and update its success ratio;
13
14 end if
15 examine move acceptance criteria and accept move accordingly;
16 if(the move was not successful)then
17 increment \(j\);
18 else
19 reset \(j\);
20
21 end if
22 update iteration control parameters;
23 end if
```  
**Algorithm 4**_localSearch_ Algorithm  
The move selection probability, \(p_{m}\), is updated consistently after a certain number of iterations, \(windowSize\), based on the success ratio of the \(Swap\) and \(TwoOpt\) moves: \(swapSR\) and \(twoOptSR\), respectively (lines 4-6 in Algorithm 4). The success ratio is computed as the number of times that the move is successfully applied, divided by the total number of times that the move was applied during the past \(windowSize\). If \(swapSR\) is better than \(twoOptSR\), \(p_{m}\) is updated such that \(Swap\) has a higher probability of being chosen and vice versa, as shown in Equation (5), where \(\beta\in(0,1)\) is a learning rate parameter. \[p_{m}= \begin{cases}p_{m}+\beta\times p_{m},&\text{if }swapSR\geq twoOptSR. \\ p_{m}-\beta\times p_{m},&\text{otherwise.}\end{cases}  \tag{5}\]  
Moreover, in order to control the computational time, the convergence is examined and the LS procedure is stopped if it fails to improve the solution after a specific number of iterations (_convergence_), as shown in lines 1 and 14-18. Two variants of GRASP were considered, according to the LS procedure used: hill-climbing local search (HCLS) [42] and LS with simulated annealing (SA) [26]. These variants differ in terms of the initialization step and the acceptance criteria (lines 2 and 13 in Algorithm 4, respectively). In the HCLS variant, the loop control parameter is a simple loop counter \(i\), which is initialized to zero. The termination condition is satisfied when \(i\) reaches the maximum number of allowed iterations, \(maxIter\). In this variant, a move is accepted only if the resulting neighbor has a lower cost than that of the current solution. In the second variant, SA, the loop is controlled by a temperature parameter, \(T_{i}\). \(T_{i}\) is initialized to an initial temperature, \(T_{0}\), and updated using a geometric cooling schedule, as shown in Equation (6), where \(\gamma\in(0,1)\)[26]. The acceptance criterion in SA differs from that in the HCLS variant for inferior moves.