# A Monarch Butterfly Optimization for the Dynamic Vehicle Routing Problem
## 4 Experimental Results
### Comparison with the Literature for DVRP  
A comparison for the quality of the solution, in terms of minimizing travel distances, was done between our approach and other metaheuristics proposed previously in the literature. In order to obtain significant results, our approach was executed five times for each instance. Tables 1 and 2 show the best computational results by our MBO algorithm and the average results over five runs, respectively. There are six columns in Tables 1 and 2: the instance, our _MBO_ algorithm, the best known solutions (\(BKS\)), the algorithm to find the \(BKS\), the relative error (\(RE\)) (i.e., \(RE=(MBO-BKS)/BKS\)\(\times\) 100%) and the computational time by MBO (note that we cannot compare with other algorithms as there is no such data available in the public domain or in the literature). There are other best and average results in Tables 1 and 2 provided by some heuristic algorithms as follows: GA2007 and TS by [PERSON] and [PERSON] (2017), DAPSO and VNS by (2016), GA2014 by (2017), HLNS by (2017) and AAC-2 OPT by (2017). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **MBO** & **BKS** & **Algorithm** & **RE (\%)** & \(\mathbf{T_{MBO}}\) **(s)** \\ \hline c50 & 570.61 & **551.95** & AAC-2 OPT & 3.38 & 42.44 \\ c75 & **897.16** & 962.79 & GA & \(-\)6.82 & 83.01 \\ c100 & **915.27** & 961.10 & GA2007 & \(-\)4.77 & 80.80 \\ c100b & 819.60 & **800.93** & AAC-2 OPT & 2.33 & 101.77 \\ c120 & 1070.18 & **1049.47** & AAC-2 OPT & 1.97 & 122.56 \\ c150 & **1183.03** & 1318.22 & TS & \(-\)15.19 & 250.99 \\ c199 & **1394.74** & 1640.40 & DAPSO & \(-\)14.98 & 470.15 \\ f1 & **271.43** & 279.52 & DAPSO & \(-\)2.89 & 51.53 \\ f134 & **11759.06** & 13015.56 & AAC-2 OPT & \(-\)9.77 & 205.78 \\ tail57a & **1478.71** & 1755.33 & AAC-2 OPT & \(-\)0.38 & 81.75 \\ tail57b & 1371.90 & **1306.47** & AAC-2 OPT & 5.01 & 90.42 \\ tail75c & 1464.37 & **1406.27** & TS & 4.13 & 77.41 \\ tail57d & 1419.00 & **1334.67** & AAC-2 OPT & 6.32 & 83.13 \\ tail100a & **2185.49** & 2194.93 & AAC-2 OPT & \(-\)0.43 & 113.82 \\ tail100b & **2057.80** & 2126.09 & AAC-2 OPT & \(-\)3.21 & 108.28 \\ tail100c & **1463.42** & 1490.58 & VNS & \(-\)1.82 & 131.28 \\ tail00d & **1704.35** & 1834.60 & GA2007 & \(-\)7.10 & 119.77 \\ tail50a & 3560.28 & **2999.27** & AAC-2 OPT & 18.70 & 336.75 \\ tail50b & 2966.19 & **2846.28** & AAC-2 OPT & 4.21 & 333.55 \\ tail50c & **2528.04** & 2612.68 & GA2007 & \(-\)3.24 & 353.91 \\ tail50d & 2980.44 & **2950.61** & GA2007 & 1.01 & 292.68 \\ \hline Average & **2107.91** & 2163.70 & & \(-\)1.12 & 168.18 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of the best Monarch Butterfly Optimization (MBO) results with the hitherto best-known solutions. As you can see, our approach is very competitive. Table 1 shows that MBO found 12 out of 21 new best solutions, compared to the BKS. The average distance of all instances by the MBO was 2096.55 which is lower than the BKS's average cost of 2163.70. It made an improvement of 1.12% over the BKS. Regarding the computation time of MBO, the longest was no more than 470.15 s (much lower than the time limit of 750 s that we set), and the shortest was 42.44 s, while the average time for each instance was 168.18 s. In particular, the computation time for each time slice was only 6.73 s on average. This indicates that MBO has good computational capability. From Table 2, our average results were superior to GRASP in almost all instances, and better than BKS in 14 instances. All these results allow us to say that our MBO is effective and shows the viability to generate very high quality solutions for the DVRP. In the next experiment, we compared the AAC-2 OPT, DAPSO, and GA2007 with our MBO. The percentage of deviation from the known optimal solution concerning problems can be seen as a chart in Figure 4. It shows that MBO is superior to other methods. The deviation of MBO is less than 5% for all instances except tail75d and tail150a. In this experiment, we analyzed the results in detail.