# Solving the Parallel Drone Scheduling Traveling Salesman Problem via Constraint Programming
## 4 Computational Experiments
### Main Experimental Results
#### 4.2.3 Instances Proposed in [13]  
A third set of experiments to test the model presented in Section 3 was carried out on the instances originated from TSPLIB [21] in [13]. Since this dataset partially overlaps with that discussed in Section 4.2.2, only the results on the uncovered instances are reported here. We rename the instances according to the logic followed in previous publications for the instances presented in [7]. We refer the reader to [13] for full details about the instances (the mapping of the naming notation should also be straightforward). The results again cover instances with 48 to 229 customers served with six drones. We report figures for the methods previously applied on these instances, namely a _MILP_, a branch-and-price approach (\(B\&P\)) and a matheuristic algorithm (_matheuristic_), all discussed in [13]. The results are summarized in Table 8.  
The results show that CP was able to find three new optimal solutions, with improvements of up to 15% over the previous solution values. For the hardest instances, however, significant computing time was required--more than 32 h of computation. In Figure 4 the optimality gaps are reported for all the methods available for these instances. For each method \(M\), the gap is calculated in terms of the percentage deviation from the optimal solution as \(\frac{cost(M)-cost(CP)}{cost(CP)}\cdot 100\), where \(cost(M)\) is the cost of the best solution retrieved by method \(M\). From the chart, it is possible to see how the methods previously introduced in [13] have difficulty finding high quality solutions for the larger instances, with substantial gaps with respect to CP in some cases. From the results on these instances, the best method among those discussed in [13] appears to be the MILP-based method, although it performed poorly on one of the instances. \begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline
**Instance** & **[PERSON] et al.** & **[PERSON] et al.** & **[PERSON] et al.** & **[PERSON] and [PERSON]** & **[PERSON] et al.** & **[PERSON] et al.** & **CP** & \\  & [7]–UB & [10]–UB & [11]–UB & [12]–UB & [14]–UB & [13]–UB & **Opt Cost** & **Sec Found** & **Sec Opt** \\ \hline aats 0.8,0.1,2.1 & 29,954.0 & 29,954.0 & 29,954.0 & 29,954.0 & - & - & 29,954.0 & 0.7 & 1.3 \\ aats -1.80,1.2,1 & 37,780.0 & 32,780.0 & 33,780.0 & - & - & 32,780.0 & 2.7 & 3.3 \\ aats -0.1,2.1 & 22,180.0 & 62,130.0 & 42,130.0 & 42,130.0 & - & - & 24,236.0 & 0.3 & 0.3 \\ aats -0.0,2.1,2.1 & 38,640.0 & 38,662.0 & 38,662.0 & - & - & 38,642.0 & 0.8 & 0.8 \\ aats -0.0,0.2,1.2 & 31,952.0 & 33,952.0 & 31,952.0 & 33,952.0 & - & - & 31,952.0 & 0.5 & 0.5 \\ aats -0.0,0.1,2.3 & 30,780.8 & 30,780.8 & 30,780.8 & - & - & 30,780.8 & 2.0 & 2.2 \\ aats -0.0,0.1,2.1 & 27,780.0 & 27,924.0 & 27,944.0 & 27,944.0 & - & - & 27,784.0 & 4.1 & 5.2 \\ aats 0.80,1.1,3 & 33,234.0 & 33,234.0 & 33,234.0 & - & - & 33,234.0 & 14 & 2.1 \\ aats 0.80,1.3,1.3 & 29,420.0 & 29,142.0 & 29,142.0 & 29,142.0 & - & - & 29,424.0 & 2.4 & 5.3 \\ aats 0.80,1.4,1.4 & 28,660.0 & 28,660.0 & 28,660.0 & - & - & 28,660.0 & 38 & 7.1 \\ aats 0.80,1.5,1.2 & 28,660.0 & 28,660.0 & 28,660.0 & - & - & 28,631.0 & 2.9 & 7.6 \\ aats 0.80,2.1,2.1 & 28,660.0 & 28,660.0 & 28,660.0 & - & 28,736.0 & 28,660.0 & 1.1 & 13.6 \\ aats 0.80,3.2,1 & 28,660.0 & 28,660.0 & 28,660.0 & - & - & 28,631.0 & 2.0 & 18.0 \\ aats 0.80,4.2,1.3 & 28,610.0 & 28,610.0 & 28,610.0 & 28,610.0 & - & 28,610.0 & 28,610.0 & 5.9 & 22.6 \\ aats 0.80,5.2,1.2 & 28,610.0 & 28,610.0 & 28,610.0 & 28,610.0 & - & - & 28,610.0 & 3.5 & 27.3 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Instances originated from _att8_ in [7]. Optimal solution costs.