## 5 Computational Experiments and Discussion
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multicolumn{2}{c}{**Instance**} & \multicolumn{1}{c}{**Depot**} & \multicolumn{1}{c}{**Vehicle**} & \multicolumn{3}{c}{**Route**} & \multicolumn{3}{c}{**Cost**} \\ \cline{3-8} \cline{7-9} \multicolumn{1}{c}{} & & V1 & D2\(\rightarrow\)4\(\rightarrow\)17\(\rightarrow\)37\(\rightarrow\)15\(\rightarrow\)33\(\rightarrow\)45\(\rightarrow\)44\(\rightarrow\)42\(\rightarrow\)19\(\rightarrow\)40\(\rightarrow\)41\(\rightarrow\)13\(\rightarrow\)D2 & & & 119,68 & \\ \cline{3-8} \multicolumn{1}{c}{} & D2 & V2 & D2\(\rightarrow\)6\(\rightarrow\)48\(\rightarrow\)23\(\rightarrow\)7\(\rightarrow\)43\(\rightarrow\)24\(\rightarrow\)14\(\rightarrow\)25\(\rightarrow\)D2 & 40 & 98.12 & 130.14 & \\ \cline{3-8} \multicolumn{1}{c}{} & & V3 & D2\(\rightarrow\)18\(\rightarrow\)46\(\rightarrow\)27\(\rightarrow\)32\(\rightarrow\)11\(\rightarrow\)38\(\rightarrow\)5\(\rightarrow\)12\(\rightarrow\)47\(\rightarrow\)D2 & & & 78.65 & & **817.86** \\ \cline{3-8} \multicolumn{1}{c}{} & D5 & V4 & D5\(\rightarrow\)11\(\rightarrow\)8\(\rightarrow\)26\(\rightarrow\)31\(\rightarrow\)28\(\rightarrow\)3\(\rightarrow\)36\(\rightarrow\)35\(\rightarrow\)20\(\rightarrow\)22\(\rightarrow\)D5 & 40 & 95.21 & & \\ \cline{3-8} \multicolumn{1}{c}{} & D5 & D5\(\rightarrow\)21\(\rightarrow\)16\(\rightarrow\)50\(\rightarrow\)49\(\rightarrow\)10\(\rightarrow\)39\(\rightarrow\)30\(\rightarrow\)34\(\rightarrow\)21\(\rightarrow\)29\(\rightarrow\)D5 & 40 & 95.21 & & \\ \hline \multirow{6}{*}{Christofides 2} & & V1 & D1\(\rightarrow\)17\(\rightarrow\)34\(\rightarrow\)42\(\rightarrow\)49\(\rightarrow\)16\(\rightarrow\)51\(\rightarrow\)66\(\rightarrow\)D1 & & & 85.99 & \\  & & V2 & D1\(\rightarrow\)88\(\rightarrow\)14\(\rightarrow\)11\(\rightarrow\)35\(\rightarrow\)37\(\rightarrow\)17\(\rightarrow\)17 & & & 43.90 & \\  & & V3 & D1\(\rightarrow\)32\(\rightarrow\)50\(\rightarrow\)18\(\rightarrow\)55\(\rightarrow\)25\(\rightarrow\)9\(\rightarrow\)40\(\rightarrow\)D1 & & 98.72 & & \\ \cline{3-8} \multicolumn{1}{c}{} & D1 & D1\(\rightarrow\)19\(\rightarrow\)59\(\rightarrow\)66\(\rightarrow\)53\(\rightarrow\)10\(\rightarrow\)58\(\rightarrow\)D1 & 40 & 97.16 & & \\ \cline{3-8} \multicolumn{1}{c}{} & V5 & D1\(\rightarrow\)44\(\rightarrow\)52\(\rightarrow\)52\(\rightarrow\)46\(\rightarrow\)34\(\rightarrow\)57\(\rightarrow\)D1 & 40 & 34.29 & & \\ \cline{3-8} \multicolumn{1}{c}{} & V6 & D1\(\rightarrow\)30\(\rightarrow\)48\(\rightarrow\)74\(\rightarrow\)28\(\rightarrow\)62\(\rightarrow\)73\(\rightarrow\)63\(\rightarrow\)33\(\rightarrow\)2\(\rightarrow\)68\(\rightarrow\)75\(\rightarrow\)D1 & & 91.12 & & **1146.09** \\ \cline{3-8} \multicolumn{1}{c}{} & V7 & D1\(\rightarrow\)54\(\rightarrow\)54\(\rightarrow\)31\(\rightarrow\)57\(\rightarrow\)51\(\rightarrow\)52\(\rightarrow\)45\(\rightarrow\)D1 & & 75.40 & & \\ \cline{3-8} \multicolumn{1}{c}{} & V8 & D1\(\rightarrow\)26\(\rightarrow\)72\(\rightarrow\)31\(\rightarrow\)39\(\rightarrow\)12\(\rightarrow\)D1 & & & 77.34 & & \\ \cline{3-8} \multicolumn{1}{c}{} & D5 & V9 & D5\(\rightarrow\)69\(\rightarrow\)71\(\rightarrow\)60\(\rightarrow\)70\(\rightarrow\)20\(\rightarrow\)37\(\rightarrow\)36\(\rightarrow\)D5 & 40 & 61.19 & & \\ \cline{3-8} \multicolumn{1}{c}{} & V10 & D5\(\rightarrow\)61\(\rightarrow\)64\(\rightarrow\)42\(\rightarrow\)41\(\rightarrow\)56\(\rightarrow\)23\(\rightarrow\)43\(\rightarrow\)12\(\rightarrow\)2\(\rightarrow\)21\(\rightarrow\)47\(\rightarrow\)D5 & 40 & 140.33 & & \\ \hline \multirow{6}{*}{Christofides 3} & & V1 & D3\(\rightarrow\)69\(\rightarrow\)1\(\rightarrow\)50\(\rightarrow\)33\(\rightarrow\)81\(\rightarrow\)51\(\rightarrow\)35\(\rightarrow\)71\(\rightarrow\)55\(\rightarrow\)66\(\rightarrow\)20\(\rightarrow\)30\(\rightarrow\)70\(\rightarrow\)D3 & & & 110.56 & \\ \cline{3-8} \multicolumn{1}{c}{} & D3 & D3\(\rightarrow\)68\(\rightarrow\)62\(\rightarrow\)19\(\rightarrow\)11\(\rightarrow\)44\(\rightarrow\)36\(\rightarrow\)47\(\rightarrow\)46\(\rightarrow\)88\(\rightarrow\)82\(\rightarrow\)84\(\rightarrow\)7\(\rightarrow\)52\(\rightarrow\)D3 & 40 & 127.18 & 154.43 & \\ \cline{3-8} \multicolumn{1}{c}{} & V3 & D3\(\rightarrow\)31\(\rightarrow\)10\(\rightarrow\)63\(\rightarrow\)39\(\rightarrow\)32\(\rightarrow\)32\(\rightarrow\)30 & 51.83 & & 51.83 & & \\ \cline{3-8} \multicolumn{1}{c}{} & V4 & D5\(\rightarrow\)89\(\rightarrow\)18\(\rightarrow\)60\(\rightarrow\)63\(\rightarrow\)45\(\rightarrow\)17\(\rightarrow\)64\(\rightarrow\)55\(\rightarrow\)59\(\rightarrow\)94\(\rightarrow\)53\(\rightarrow\)28\(\rightarrow\)27\(\rightarrow\)D5 & & & 97.34 & & **1307.24** \\ \cline{3-8} \multicolumn{1}{c}{} & D5 & V5 & D5\(\rightarrow\)95\(\rightarrow\)92\(\rightarrow\)37\(\rightarrow\)491\(\rightarrow\)44\(\rightarrow\)14\(\rightarrow\)38\(\rightarrow\)86\(\rightarrow\)16\(\rightarrow\)61\(\rightarrow\)93\(\rightarrow\)99\(\rightarrow\)96\(\rightarrow\)6\(\rightarrow\)D5 & 40 & 92.79 & & \\ \cline{3-8} \multicolumn{1}{c}{} & V6 & D5\(\rightarrow\)13\(\rightarrow\)87\(\rightarrow\)97\(\rightarrow\)98\(\rightarrow\)85\(\rightarrow\)100\(\rightarrow\)42\(\rightarrow\)43\(\rightarrow\)15\(\rightarrow\)57\(\rightarrow\)2\(\rightarrow\)40\(\rightarrow\)58\(\rightarrow\)D5 & & & 95.14 & \\ \cline{3-8} \multicolumn{1}{c}{} & D8 & V7 & D8\(\rightarrow\)12\(\rightarrow\)80\(\rightarrow\)68\(\rightarrow\)76\(\rightarrow\)77\(\rightarrow\)3\(\rightarrow\)79\(\rightarrow\)78\(\rightarrow\)34\(\rightarrow\)29\(\rightarrow\)24\(\rightarrow\)55\(\rightarrow\)25\(\rightarrow\)54\(\rightarrow\)D8 & 40 & 95.56 & & \\ \cline{3-8} \multicolumn{1}{c}{} & V8 & D8\(\rightarrow\)44\(\rightarrow\)39\(\rightarrow\)67\(\rightarrow\)23\(\rightarrow\)56\(\rightarrow\)75\(\rightarrow\)41\(\rightarrow\)22\(\rightarrow\)47\(\rightarrow\)72\(\rightarrow\)73\(\rightarrow\)21\(\rightarrow\)26\(\rightarrow\)D8 & 40 & 95.13 & & \\ \hline \hline \end{tabular}
\end{table}