# Optimization of Truck-Drone Parcel Delivery Using Metaheuristics
## 4 Results
### Evaluation against Rival Algorithms  
Based on the conclusion presented in Section 4.1, the GRASP HCLS variant outperformed the SA variant. The better performing GRASP variant was compared with the rival algorithms, LS [10] and HGVNS [23], for the TSP-D problem, where the endurance of the drone was set to infinity and the service time for the drone launch and return was set to zero. The parameter settings for both rival algorithms can be found in the study of [PERSON] and [PERSON] [23]. The experiment used 200 instances, as described in Section 3.1. Table 4 reports the average values (in _secs_) for the best-known solutions for the ten instances for each (type, size, \(\alpha\)) combination. The column definitions are the same as those used in Table 2, and are sectioned according to the algorithm addressed. Figure 11 compares the average solution cost results. Similarly to the findings presented by [PERSON] and [PERSON] [23], the algorithms generally performed better for instances with a uniform distribution, compared to instances with a single-center distribution, for all values of \(\alpha\). The proposed GRASP approach performed better in instances where \(\alpha=1\); however, in instances where \(\alpha=2\), that size was found to play a role. Accordingly, the proposed GRASP approach had a better or approximately equal performance in instances with small size (i.e., 10 and 20). Conversely, in instances with large size (i.e., 50 and 75), our approach had a worse or approximately equal performance. Figure 10: Comparison of the average solution cost obtained with the two GRASP variants–GRASP with HCLS vs. GRASP with SA: (**a**) Uniform distribution, \(\alpha=1\). (**b**) Uniform distribution, \(\alpha=2\). (**c**) Single-centered distribution, \(\alpha=1\). (**d**) Single-centered distribution, \(\alpha=2\). The average solution costs over all instances (in _secs_) were as follows: The HGVNS scored 565.52, closely followed by the LS (567.10) and GRASP (594.11). The Friedman test applied under the null hypothesis of equal performance of all algorithms obtained a \(p\)-value of (\(p=0.074\)). Since the \(p\)-value was larger than the significance level (0.05), the null hypothesis is accepted, indicating that no statistically significant differences were detected among all the means of solution costs obtained from the three algorithms on multiple datasets. Considering the efficiency of the three algorithms under consideration, all three algorithms start by constructing the initial TSP tour using the Concorde TSP solver. Both of the rival algorithms, LS and HGVNS, adapt the best-improvement search strategy, which exhaustively explores the neighborhoods and returns the solution having the minimum cost. The proposed GRASP algorithm, on the other hand, employs the first-improvement strategy, accepting the first neighbor having a cost that is lower than that of the current solution. Excluding the time required for obtaining the initial TSP tour, a single iteration of the LS procedure requires \(\mathcal{O}(n^{3}\log n)\)[10]. A single iteration of the HGVNS algorithm runs in \(\Theta(n^{2}|\mathcal{N}^{2}|)\)[23], where \(|\mathcal{N}|\) is the number of neighborhoods considered. On the contrary, and considering the value of \(maxIter\) in HCLS to be equal to \(n\), a single iteration of GRASP requires \(\mathcal{O}(n^{2})\) time. Accordingly, the proposed algorithm has lower computational requirements than the two rival algorithms, LS and HGVNS.