# Drone-Based Parcel Delivery Using the Rooftops of City Buildings: Model and Solution
## 5 Experiments
### Experimental Results  
Table 2 shows the experimental results for the comparison of the objective values between GUROBI and the proposed heuristic. The average computational times are also summarized. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{\#} & \multirow{2}{*}{Size} & \multirow{2}{*}{ \begin{tabular}{c} \# of \\ Drones \\ \end{tabular}  } & \multirow{2}{*}{\ \begin{tabular}{c} \# of \\ Destinations \\ \end{tabular}  } & \multirow{2}{*}{ \begin{tabular}{c} \# of \\ Destinations \\ \end{tabular}  } & \multicolumn{2}{c}{**GUROBI**} & \multicolumn{2}{c}{**Heuristic**} \\ \cline{5-8}  & & & & **Objective** & **Computational** & **Objective** & **Computational** \\  & & & **Value** & **Time (sec)** & **Value** & **Time (sec)** \\ \hline
1 & & & 33 & 0.11 & 33 & 0.08 \\ \hline
2 & & & 26  
As expected, the computational time of GUROBI drastically increases as the number of drones and delivery destinations increases due to the curse of dimensionality. The computational times of GUROBI for the small- and medium-sized problems are 0.14 s and 7.21 s on average, respectively. For the large problems, GUROBI cannot find optimal solutions for 18 out of 20 problem instances within 12 h. We set 12 h as the computation time limit of GUROBI because the drone schedules should be prepared immediately before opening the operation center the next day. A better computing environment might be able to shorten the computational time of the commercial optimization software. However, if the problem size grows, the same dilemma will arise. In contrast, the proposed heuristic requires only 0.3 s (for small), 1.12 s (for medium), and 7.51 s (for large) on average to derive the optimal solutions for each problem size. For the problem instances that can be solved using GUROBI, the proposed heuristic  
\begin{table}
\begin{tabular}{p{34.1 pt} p{34.1 pt} p{34.1 pt} p{34.1 pt} p{34.1 pt} p{34.1 pt}} \hline \hline \multirow{2}{*}{**\#**} & \multirow{2}{*}{**Size**} & \multirow{2}{*}{**\# of**} & \multirow{2}{*}{**\# of**} & \multicolumn{2}{c}{**GUROBI**} & \multicolumn{2}{c}{**Heuristic**} \\ \cline{5-8}  & & & & **Objective** & **Computational** & **Objective** & **Computational** \\  & & & **Value** & **Time (sec)** & **Value** & **Time (sec)** \\ \hline
34 & & & 58 & 0.85 & 58 & 0.33 \\ \hline
35 & & & 59 & 1.54 & 59 & 0.28 \\ \hline
36 & & & 58 & 6.27 & 58 & 2.08 \\ \hline
37 & & & 60 & 0.99 & 60 & 0.12 \\ \hline
38 & & & 59 & 2.73 & 59 & 1.08 \\ \hline
39 & & & 58 & 3.35 & 58 & 1.07 \\ \hline
40 & & & 55 & 8.41 & 55 & 1.22 \\ \hline \multicolumn{2}{c}{**Average:**} & \multicolumn{2}{c}{**7.21**} & \multicolumn{2}{c}{**1.12**} \\ \hline
41 & & & - & - & 141 & 6.55 \\ \hline
42 & & & - & - & 136 & 3.36 \\ \hline
43 & & & - & - & 146 & 10.01 \\ \hline
44 & & & - & - & 143 & 4.99 \\ \hline
45 & & & - & - & 141 & 8.03 \\ \hline
46 & &gives 0% optimality losses with respect to the GUROBI solutions for all small (20 problem instances), medium (20 problem instances), and large-sized problems (2 problem instances) as shown in Table 2. The optimality gap is calculated using Equation (16). \[Gap(\%)=\frac{Objective\ Value(GUROBI)-Objective\ Value(Hueristic)}{Objective\ Value(GUROBI)}\times 100 \tag{16}\]  
As shown in Table 2, the computational time of the MILP increases rapidly as the number of variables (i.e., number of drones, number of destinations) increases. According to the IBM Knowledge Center [35], the out-of-memory or too many calculations issue almost always occurs when the branch & cut tree of commercial optimization software such as CPLEX and GUROBI becomes so large that insufficient memory remains to solve any subproblem. In such a situation, it terminates the process with an error message. Of course, a better computing environment might be able to handle this issue. However, if the problem size grows, say 20 drones and 100 destinations, the same dilemma will arise [11]. Whereas the proposed heuristic could find solutions for all the 20 large problem instances under 8 s on average.