# Optimization of Truck-Drone Parcel Delivery Using Metaheuristics
## 2 Proposed Greedy Randomized Adaptive Search Procedure for TSP-D
### Algorithm Details
#### 2.2.1 Building the Randomized Initial TSP-D Tour  
The main function of the initial TSP-D procedure (Algorithm 2) is to perform the initial partitioning of the available truck route into a truck route and a drone route, using the restricted candidate list (RCL). First, the time saving obtained for all nodes (except the depot) when a node \(j\) is transformed from a truck node to a drone node is computed. The procedure identifies the  
Figure 2: Representative solution: (**a**) represents the solution corresponding to the graph presented in (**b**). minimum amount of saved time for all nodes \(c_{min}\), the maximum amount of saved time among all nodes \(c_{max}\), and an array \(savingTime\) which contains the time saved by each node. The saved time is computed using Equation (1) and illustrated in Figure 3, where \(i\) is the node ID of the launch node, \(j\) is the node ID of the drone node, and \(k\) is the node ID of the rendezvous node. Calculating the time savings obtained for all nodes takes \(\mathcal{O}(n)\) time. \[saving=C_{T}[i][j]+C_{T}[j][k]-max(C_{D}[i][j]+C_{D}[j][k],C_{T}[i][k]) \tag{1}\]  
The threshold value, \(tau\), is computed using Equation (2) [41], where \(\delta\) is a randomly generated value, \(\delta\in(0,1)\). The RCL is accordingly built by adding the customers that may be serviced by the drone; that is, all nodes \(i\) with \(savingTime[i]\geq tau\). The \(buildRCL\) procedure requires \(\mathcal{O}(n)\) time. Next, nodes are iteratively and randomly selected and removed from the RCL to be transformed into drone nodes, using the \(BuildTspd\) algorithm explained in Algorithm 3. \[tau=c_{max}-\delta\times(c_{min}+c_{max}) \tag{2}\]  
\(buildTspd\) was inspired by the greedy partitioning heuristic presented by [PERSON] et al. [10]. In that method, one of the three moves (\(MakeFly\), which converts a truck node to a drone node, \(PushLeft\), and \(PushRight\)) is randomly selected in each iteration. The selected move is applied to an unprocessed node. However, in this implementation, as presented in Algorithm 3, a candidate node, \(candidateElement\), is chosen randomly and removed from the RCL, in order to be converted into a drone node. \(candidateElement\) can be a drone node if it has a predecessor and a successor, meaning that it is not a boundary node. In addition, it must not lie in a sortie. Once this move is successful, the feasibility of the \(PushLeft\) and \(PushRight\) moves for the sortie under consideration is examined. If both moves can be feasibly implemented while improving the cost, then one of them is greedily selected, such that the cost saving is maximized. Otherwise, the feasible move is applied if it improves the cost. \(PushLeft\) inserts the truck node to the left of the launch node into the sortie, as shown in Figure 4. The move is only feasible if the node preceding the launch node is a truck node other than the depot and is not part of a sortie. The time taken by the sortie before applying \(PushLeft\), \(beforeLeft\), is calculated using Equation (3). Equation (4) computes the time taken by the sortie after applying \(PushLeft\), \(afterLeft\). The time saved is computed by taking the difference between \(beforeLeft\) and \(afterLeft\). If the procedure results in time savings greater than zero, the move is accepted. The \(PushRight\) operator is symmetric with respect to \(PushLeft\). Converting the \(candidateElement\) into a drone node in lines 4-10 of Algorithm 3 requires \(\mathcal{O}(1)\) time. The complexity of both moves, including the work  
Figure 3: Transforming node \(j\) into a drone node. required to compute the savings obtained by the moves, is \(\mathcal{O}(1)\) time. However, the time required by the \(CompCost\) step at line 1 of the algorithm is \(\mathcal{O}(n)\) (Section 2.3), resulting in a time of \(\mathcal{O}(n)\) for \(buildTspd\). The \(buildTspd\) algorithm is called a number of times equal to the length of the RCL as in line 6 from Algorithm 2.