%!Tex root=./SEMR_Template_en.tex
\section{Numerical Evaluation}\label{sec:experiments}

In our paper, we focus on the comparison of our algorithm with results of paper \cite{Casazza2021}. The authors of that paper did not provide neither implementation details of their algorithm, nor the benchmarking instances. Thus, we synthesize the random instances following their instructions, and compare our averaged results with theirs. For the sake of convenience, we denote the method of our colleagues as $A_{CC}$, and the proposed algorithm as $A_{E2TRP}$. 

\subsection{Benchmarking instances} 

In all the instances, graph $G$ is specified by a finite point set $V$ that consists of points taken at random from the square $(-100,100)\times(-100,100)$ on the Euclidean plane. Similarly to \cite{Casazza2021}, we restrict ourselves to the case of $|V| = \{20,30\}$, and the graph density $\gamma \in \{0.25,0.5,0.75\}$.

For any arc $e$, its cost $c_e$ is defined  by the Euclidean distance between its endpoints,  and failure probability $q_e$ taken at random from the set $\{5\cdot10^{-3},10^{-3},10^{-4},10^{-5}\}$. For any instance, we guarantee that terminals $s$ and $t$ belong to the same connected component. 

For each tuple $(V,\gamma)$, we synthesize a bunch of 10 random graphs. Then, for each generated graph we consider E2TRP instances $(V,\gamma,\F)$, where $\F\in\{1~\cdot10^{-1}, 5~\cdot10^{-2}, 1~\cdot10^{-2}, 5~\cdot10^{-3}, 1~\cdot10^{-3}, 
5~\cdot10^{-4}, 1~\cdot10^{-4}, 5~\cdot10^{-5}, 1~\cdot10^{-5}, 5~\cdot10^{-6}, 1~\cdot10^{-6}\}$. 

Thus, we obtain 660 instances of the E2TRP.
All benchmarking instances together with source code are available by request. 

\subsection{Experimental setup}

Our experiment consists of three subsequent stages. At the first stage, we evaluate performance of our algorithm in compar-ison the algorithm proposed in \cite{Casazza2021}. Since the authors of \cite{Casazza2021} report on the results obtained only for graphs of $20$ nodes, we restrict ourselves to the instances of the same size. In addition, we set time limit to 1 hour (3600 sec) as well. 

On the second stage, we examine our algorithm on 30 node instances to demonstrate its ability to obtain approximate solutions within the same time limit.

Finally, on the third stage, we increase the time limit to 10 hours and test the computational ability of the proposed algorithm over the whole database of the benchmarking instances and compare it with the results obtained within the hour.

The algorithm was implemented in Python 3.9.7 using NetworkX library, while the LP-relaxations of the aforementioned problems was done on top of the Gurobi MIP-solver \cite{GUROBI}. 

The experiments were carried out on the `Uran' supercomputer center at N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences http://parallel.uran.ru, on Intel(R) Xeon(R) 16 core CPU E5-2697 v4 @2.30 GHz 256GB RAM. 

\subsection{Results and discussion}

Results of the first stage are reported in Table \ref{tbl:1}. For each group of instances the best performers are highlighted in bold. 

As it can be seen from the Table \ref{tbl:1}, the number of optimal solutions obtained by $A_{CC}$ is greater than the one obtained by $A_{E2TRP}$ but our algorithm provides branching trees of less nodes in average and less average  relative errors (gaps) for the instances of tight probability thresholds $\F$. For instance, for the group $(20,0.5,1~\cdot10^{-5})$, average gap and branching nodes obtained by $A_{E2TRP}$ are 23.79 and 6815.1, respectively vs. 52.7 and 16054.4  for $A_{CC}$. 

\begin{table}[th]
\caption{First stage results: comparison of algorithms $A_{CC}$ and $A_{E2TRP}$ on instances with $|V|=20$ nodes:
$\gamma$ is the graph density, $\F$ is the failure probability threshold,\\ OPT is the number of instances solved to optimality,
 ABN is the average number of branching nodes,
  avg gap,\% is the average gap value = $(UB-LB)/LB$, time limit = 1 hour}\label{tbl:1}
  \scriptsize
  % \tiny
  \centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
& & \multicolumn{3}{|c|}{$A_{CC}$} & \multicolumn{3}{|c|}{$A_{E2TRP}$}\\
\hline
$\gamma$ & $\F$ & OPT & ABN & avg gap,\% & OPT & ABN & avg gap,\%\\
\hline
& $1\cdot10^{-1}$ & 10 & 1.0 & 0.0 & 10 & 3607.8 & 0.0\\
& $5\cdot10^{-2}$ & 10 & 1.0 & 1.6 & 10 & 3607.8 & 0.0\\
& $1\cdot10^{-2}$ & 10 & 1.6 & 0.0 & 10 & 2068.6 & 0.0\\
& $5\cdot10^{-3}$ & 10 & 8.5 & 0.0 & 10 & 1552.4 & 0.0\\
& $1\cdot10^{-3}$ & {\bf 10} & 291.5 & {\bf 0.0} & 8 & 6667.9 & 4.44\\
0.25 & $5\cdot10^{-4}$ & {\bf 10} &  227.9 & {\bf 0.0} & 9 & 6821.3 & 4.01\\
& $1\cdot10^{-4}$ & {\bf 8} & 6634.6 & 43.8 & 6 & 11819.2 & {\bf 10.81}\\
& $5\cdot10^{-5}$ & {\bf 9} & 7930.3 & {\bf 11.6} & 6 & 7276.2 & 13.82\\
& $1\cdot10^{-5}$ & {\bf 8} & 9357.0 & 47.9  & 3 & 8025.9 & {\bf 23.42}\\
& $5\cdot10^{-6}$ & {\bf 5} & 12823.5 & 67.9 & 2 & 7682.7 & {\bf 29.52}\\
& $1\cdot10^{-6}$ & {\bf 3} & 17148.1 & 59.6 & 2 & 7511.1 & {\bf 32.95}\\
\hline
& $1\cdot10^{-1}$ & {\bf 10} & 1.0 & {\bf 0.0} & 9 & 9028.0 & 0.09\\
& $5\cdot10^{-2}$ & 10 & 1.0 & 0.0 & 10 & 9182.6 & 0.0\\
& $1\cdot10^{-2}$ & {\bf 10} & 1.0 & {\bf 0.0} & 8 & 4900.4 & 2.43\\
& $5\cdot10^{-3}$ & {\bf 10} & 210.3 & {\bf 0.0} & 8 & 3083.6 & 3.52\\
& $1\cdot10^{-3}$ & {\bf 10} & 159.0 & {\bf 0.0} & 6 & 4761.2 & 12.47\\
0.5 & $5\cdot10^{-4}$ & {\bf 10} & 129.8 & {\bf 0.0} & 6 & 4469.6 & 12.2\\
& $1\cdot10^{-4}$ & {\bf 10} & 205.0 & {\bf 0.0} & 6 & 4233.6 & 14.57\\
& $5\cdot10^{-5}$ & {\bf 10} & 539.2 & {\bf 0.0} & 6 & 3738.1 & 14.81\\
& $1\cdot10^{-5}$ & {\bf 8} & 16054.4 & 52.7 & 3 & 6815.1 & {\bf 23.79}\\
& $5\cdot10^{-6}$ & {\bf 8} & 16364.5 & 52.5 & 2 & 6154.3 & {\bf 30.07}\\
& $1\cdot10^{-6}$ & {\bf 8} & 17542.9 & 53.9 & 1 & 4828.3 & {\bf 39.12}\\
\hline
& $1\cdot10^{-1}$ & {\bf 10} & 1.0 & {\bf 0.0} & 4 & 23877.0 & 15.34\\
& $5\cdot10^{-2}$ & {\bf 10} & 1.0 & {\bf 0.0} & 4 & 24516.4 & 15.1 \\
& $1\cdot10^{-2}$ & {\bf 10} & 1.0 & {\bf 0.0} & 4 & 10493.6 & 19.38\\
& $5\cdot10^{-3}$ & {\bf 10} & 1.6 & {\bf 0.0} & 5 & 5289.8 & 20.35\\
& $1\cdot10^{-3}$ & {\bf 10} & 6.8 & {\bf 0.0} & 3 & 5496.2 & 23.54\\
0.75 & $5\cdot10^{-4}$ & {\bf 10} & 6.2 & {\bf 0.0} & 3 & 5496.8 & 23.79\\
& $1\cdot10^{-4}$ & {\bf 9} & 1104.4 & 50.1 & 4 & 3566.2 & {\bf 33.14}\\
& $5\cdot10^{-5}$ & {\bf 8} & 2728.4 & 46.5 & 2 & 3482.6 & {\bf 43.82}\\
& $1\cdot10^{-5}$ & {\bf 7} & 3280.9 & 50.5 & 2 & 2890.6 & {\bf 46.94}\\
& $5\cdot10^{-6}$ & {\bf 7} & 3114.2 & {\bf 51.2} & 1 & 2976.0 & 52.21\\
& $1\cdot10^{-6}$ & {\bf 6} & 2069.5 & 53.6 & 0 & 3565.3 & {\bf 53.01}\\
\hline
\end{tabular}
\end{table}

\begin{table}[th]
\caption{Second stage results: numerical evaluation of $A_{E2TRP}$ with $|V|=30$ nodes:
$\gamma$ is the graph density, $\F$ is the failure threshold,\\ OPT is the number of instances solved to optimality,
 ABN is the average number of branching nodes,
  avg gap,\% is the average gap value, \%, time limit = 1 hour}\label{tbl:2}
  \centering
  \tiny
  % \scriptsize
  \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
  \hline
  & \multicolumn{9}{|c|}{$A_{E2TRP}$}\\
  \hline
   & \multicolumn{3}{|c|}{$\gamma=0.25$} & \multicolumn{3}{|c|}{$\gamma=0.5$} & \multicolumn{3}{|c|}{$\gamma=0.75$}\\ 
  \hline
  $\F$ & OPT & ABN & avg gap,\% & OPT & ABN & avg gap,\% & OPT & ABN & avg gap,\%\\
  \hline
  $1\cdot10^{-1}$ & 7 & 23147.2 & 8.28 & 4 & 19628.4 & 17.47 & 0 & 14430.6 & 58.66\\
  $5\cdot10^{-2}$ & 7 & 22887.2 & 8.19 & 4 & 16413.2 & 19.47 & 0 & 13735.8 & 59.71\\
  $1\cdot10^{-2}$ & 6 & 8513.6 & 8.93 & 3 & 9389.0 & 24.03 & 0 & 8218.4 & 64.04\\
  $5\cdot10^{-3}$ & 5 & 4306.1 & 10.46 & 3 & 5160.2 & 27.49 & 0 & 5337.2 & 63.3\\
  $1\cdot10^{-3}$ & 3 & 5488.1 & 15.38 & 4 & 4354.0 & 26.1 & 0 & 4594.4 & 68.14\\
  $5\cdot10^{-4}$ & 3 & 5637.1 & 14.65 & 2 & 4829.4 & 31.8 & 0 & 4751.6 & 66.74\\
  $1\cdot10^{-4}$ & 3 & 6545.3 & 29.69 & 1 & 3843.8 & 46.84 & 0 & 4397.2 & 67.22\\
  $5\cdot10^{-5}$ & 2 & 6292.3 & 33.35 & 0 & 3686.0 & 54.62 & 0 & 4249.6 & 67.47\\
  $1\cdot10^{-5}$ & 1 & 5095.4 & 39.04 & 0 & 4640.1 & 53.13 & 0 & 3146.0 & 72.61\\
  $5\cdot10^{-6}$ & 1 & 4717.4 & 43.58 & 0 & 4752.1 & 57.35 & 0 & 1601.6 & 83.04\\
  $1\cdot10^{-6}$ & 1 & 3964.4 & 46.4 & 0 & 2655.1 & 63.19 & 0 & 1281.0 & 86.1\\
  \hline
  \end{tabular}
\end{table}


Summarizing the results of the first stage, we conclude that algorithm $A_{CC}$ performs well on the small instances of $20$ nodes under mild threshold values $\F$. However, when the value $\F$ becomes more tight, our algorithm $A_{E2TRP}$ shows better results. 

Table \ref{tbl:2} reflects the results of the second stage for instances with $|V|=30$. As it follows from the table, our algorithm is able to find feasible solutions for all instances regardless of their $\gamma$ and $\F$ values. However, the number of instances that are solved to optimality are decreased with the $\gamma$ growth and $\F$ tightening. 

\begin{table}[th]
\caption{Third stage results: numerical evaluation of $A_{E2TRP}$ with $|V|=20$ nodes:
$\gamma$ is the graph density, $\F$ is the failure threshold, OPT is the number of instances solved to optimality,
 ABN is the average number of branching nodes,
  avg gap,\% is the average gap value, \%, time limit = 10 hour}\label{tbl:3}
% \scriptsize
\tiny
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
   \multicolumn{2}{|c}{}    & \multicolumn{6}{|c|}{20 nodes}\\
\hline
\multicolumn{2}{|c}{}  & \multicolumn{3}{|c|}{1 hour} & \multicolumn{3}{|c|}{10 hours}\\
\hline
  $\gamma$ &    $\F$      & OPT & ABN & avg gap,\% & OPT & ABN & avg gap,\%        \\
\hline
 & $1\cdot10^{-1}$ & 10 & 3607.8 & 0.0 &   10 &    3607.8 &              0.00      \\
   & $5\cdot10^{-2}$ & 10 & 3607.8 & 0.0 &   10 &    3607.8 &            0.00      \\
   & $1\cdot10^{-2}$ &  10 & 2068.6 & 0.0 & 10 &    2068.6 &             0.00      \\
   & $5\cdot10^{-3}$ &  10 & 1552.4 & 0.0 &  10 &    1552.4 &            0.00      \\
0.25 & $1\cdot10^{-3}$ & 8 & 6667.9 & 4.44 &    8 &   12588.1 &         {\bf 1.26} \\
   & $5\cdot10^{-4}$ & 9 & 6821.3 & 4.01 &   {\bf 10} &   18059.1 &    {\bf 0.00}  \\
   & $1\cdot10^{-4}$ & 6 & 11819.2 & 10.81 &    {\bf 7} &   73885.0 &   {\bf 4.85} \\
   & $5\cdot10^{-5}$ & 6 & 7276.2 & 13.82 &    {\bf 7} &   49897.9 &   {\bf 6.64}  \\
   & $1\cdot10^{-5}$ & 3 & 8025.9 & 23.42 &    {\bf 5} &   56711.5 &   {\bf 11.68} \\
   & $5\cdot10^{-6}$ & 2 & 7682.7 & 29.52 &    {\bf 3} &   67474.4 &  {\bf 14.33}  \\
   & $1\cdot10^{-6}$ & 2 & 7511.1 & 32.95 &    {\bf 3} &   59927.1 &   {\bf 18.75} \\
\hline
 & $1\cdot10^{-1}$ & 9 & 9028.0 & 0.09 &   {\bf 10} &    9182.6 &       {\bf 0.00} \\
   & $5\cdot10^{-2}$ & 10 & 9182.6 & 0.0 &   10 &    9182.6 &             0.00     \\
   & $1\cdot10^{-2}$ & 8 & 4900.4 & 2.43 &   {\bf 10} &    8444.4 &     {\bf 0.00} \\
   & $5\cdot10^{-3}$ & 8 & 3083.6 & 3.52 &   {\bf 10} &    6609.2 &     {\bf 0.00} \\
0.5   & $1\cdot10^{-3}$ & 6 & 4761.2 & 12.47 &   {\bf 7} &   21457.3 &  {\bf 3.98} \\
   & $5\cdot10^{-4}$ & 6 & 4469.6 & 12.2 &    {\bf 8} &   17351.9 &    {\bf 2.55}  \\
   & $1\cdot10^{-4}$ & 6 & 4233.6 & 14.57 &   6 &   26172.1 &           {\bf 5.68} \\
   & $5\cdot10^{-5}$ & 6 & 3738.1 & 14.81 &    {\bf 7} &   22185.0 &    {\bf 5.60} \\
   & $1\cdot10^{-5}$ & 3 & 6815.1 & 23.79 &    {\bf 5} &   29727.4 &   {\bf 12.81} \\
   & $5\cdot10^{-6}$ & 2 & 6154.3 & 30.07 &    {\bf 5} &   30477.4 &   {\bf 16.73} \\
   & $1\cdot10^{-6}$ & 1 & 4828.3 & 39.12 &    {\bf 4} &   28915.9 &   {\bf 22.84} \\
\hline
 & $1\cdot10^{-1}$ & 4 & 23877.0 & 15.34 &    {\bf 6} &   67308.0 &    {\bf 7.16}  \\
   & $5\cdot10^{-2}$ & 4 & 24516.4 & 15.1 &    {\bf 6} &   67308.0 &   {\bf 7.16}  \\
   & $1\cdot10^{-2}$ & 4 & 10493.6 & 19.38 &    {\bf 6} &   38357.6 &  {\bf 9.96}  \\
   & $5\cdot10^{-3}$ & 5 & 5289.8 & 20.35 &    5 &   28099.6 &         {\bf 9.15}  \\
0.75   & $1\cdot10^{-3}$ & 3 & 5496.2 & 23.54 & {\bf 5} &   28796.8 &  {\bf 10.10} \\
   & $5\cdot10^{-4}$ & 3 & 5496.8 & 23.79 &  {\bf 5} &   27734.8 &     {\bf 10.05} \\
   & $1\cdot10^{-4}$ & 4 & 3566.2 & 33.14 &    {\bf 5} &   17916.6 &   {\bf 21.26} \\
   & $5\cdot10^{-5}$ & 2 & 3482.6 & 43.82 &  2 &   24889.3 &           {\bf 27.70} \\
   & $1\cdot10^{-5}$ & 2 & 2890.6 & 46.94 &    2 &   22787.0 &         {\bf 33.44} \\
   & $5\cdot10^{-6}$ & 1 & 2976.0 & 52.21 &    {\bf 2} &   20084.4 &   {\bf 39.91} \\
   & $1\cdot10^{-6}$ & 0 & 3565.3 & 53.01 &    {\bf 2} &   20747.1 &   {\bf 38.87} \\
\hline
\end{tabular}
\end{table}

\begin{table}[th]
\caption{Third stage results: numerical evaluation of $A_{E2TRP}$ with $|V|=30$ nodes:
$\gamma$ is the graph density, $\F$ is the failure threshold, OPT is the number of instances solved to optimality,
 ABN is the average number of branching nodes,
  avg gap,\% is the average gap value, \%, time limit = 10 hour}\label{tbl:4}
% \scriptsize
\tiny
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
   \multicolumn{2}{|c}{}    & \multicolumn{6}{|c|}{30 nodes} \\
\hline
\multicolumn{2}{|c}{}  & \multicolumn{3}{|c|}{1 hour} & \multicolumn{3}{|c|}{10 hours} \\
\hline
  $\gamma$ &    $\F$      & OPT & ABN & avg gap,\% & OPT & ABN & avg gap,\% \\
\hline
 & $1\cdot10^{-1}$ &  7 & 23147.2 & 8.28 &  {\bf 8} &   56920.6 &       {\bf 3.14} \\
   & $5\cdot10^{-2}$ &  7 & 22887.2 & 8.19 &  {\bf 8} &   56920.6 &       {\bf 3.14} \\
   & $1\cdot10^{-2}$ &  6 & 8513.6 & 8.93 &    {\bf 8} &   25404.4 &       {\bf 2.40} \\
   & $5\cdot10^{-3}$ &  5 & 4306.1 & 10.46 &    {\bf 8} &   19153.5 &       {\bf 1.17}\\
0.25 & $1\cdot10^{-3}$ &  3 & 5488.1 & 15.48 &      {\bf 8} &   26404.5 &       {\bf 2.06}\\
   & $5\cdot10^{-4}$ &  3 & 5637.1 & 14.65 &    {\bf 8} &   25947.3 &       {\bf 1.70} \\
   & $1\cdot10^{-4}$ &  3 & 6545.3 & 29.69 &   {\bf 5} &   40336.6 &      {\bf 20.28} \\
   & $5\cdot10^{-5}$ &  2 & 6292.3 & 33.35 &    {\bf 4} &   42185.3 &      {\bf 20.42}  \\
   & $1\cdot10^{-5}$ &  1 & 5095.4 & 39.04   &     {\bf 3} &   36239.0 &      {\bf 24.77}  \\
   & $5\cdot10^{-6}$ &  1 & 4717.4 & 43.58 &    {\bf 2} &   34515.2 &      {\bf 29.05} \\
   & $1\cdot10^{-6}$ &  1 & 3964.4 & 46.4 &         {\bf 2} &   27162.4 &      {\bf 31.41}  \\
\hline
 & $1\cdot10^{-1}$ &  4 & 19628.4 & 17.47 &   {\bf 4} &   52933.4 &       {\bf 8.82}  \\
   & $5\cdot10^{-2}$ &  4 & 16413.2 & 19.47 &  4 &   52933.4 &       {\bf 8.82} \\
   & $1\cdot10^{-2}$ &  3 & 9389.0 & 24.03 &       {\bf 4} &   36123.0 &      {\bf 10.92}  \\
   & $5\cdot10^{-3}$ &  3 & 5160.2 & 27.49 &   {\bf 4} &   27190.2 &      {\bf 13.12}  \\
0.5   & $1\cdot10^{-3}$ &  4 & 4354.0 & 26.1 &  4 &   23955.8 &      {\bf 12.56}  \\
   & $5\cdot10^{-4}$ &  2 & 4829.4 & 31.8 &   {\bf 3} &   28477.6 &      {\bf 15.08} \\
   & $1\cdot10^{-4}$ &  1 & 3843.8 & 46.84 &    {\bf 2} &   25629.1 &      {\bf 32.10} \\
   & $5\cdot10^{-5}$ &  0 & 3686.0 & 54.62 &    {\bf 1} &   25899.9 &      {\bf 38.36} \\
   & $1\cdot10^{-5}$ &  0 & 4640.1 & 53.13 &     {\bf 1} &   32232.9 &      {\bf 39.06} \\
   & $5\cdot10^{-6}$ &  0 & 4752.1 & 57.35 &   0 &   35114.3 &      {\bf 42.68} \\
   & $1\cdot10^{-6}$ &  0 & 2655.1 & 63.19 &    0 &   21523.5 &      {\bf 47.99} \\
\hline
   & $1\cdot10^{-1}$ &  0 & 14430.6 & 58.66 &     {\bf 1} &   57790.2 &      {\bf 44.45}  \\
   & $5\cdot10^{-2}$ &  0 & 13735.8 & 59.71 &  {\bf 1} &   57810.4 &      {\bf 44.44} \\
   & $1\cdot10^{-2}$ &  0 & 8218.4 & 64.04 &     {\bf 1} &   39927.0 &      {\bf 48.41}  \\
   & $5\cdot10^{-3}$ &  0 & 5337.2 & 63.3 &  {\bf 1}  &   30397.0 &      {\bf 48.20}  \\
0.75   & $1\cdot10^{-3}$ &  0 & 4594.4 & 68.14 &      0 &   31808.6 &      {\bf 50.30}  \\
   & $5\cdot10^{-4}$ &   0 & 4751.6 & 66.74 &     0 &   32276.6 &      {\bf 49.75} \\
   & $1\cdot10^{-4}$ &   0 & 4397.2 & 67.22 &      0 &   31572.8 &      {\bf 50.76} \\
   & $5\cdot10^{-5}$ &  0 & 4249.6 & 67.47 &      0 &   31387.6 &      {\bf 50.50} \\
   & $1\cdot10^{-5}$ &  0 & 3146.0 & 72.61 &       0 &   24130.2 &      {\bf 59.37} \\
   & $5\cdot10^{-6}$ &  0 & 1601.6 & 83.04 &   0 &   15438.0 &      {\bf 71.39} \\
   & $1\cdot10^{-6}$ & 0 & 1281.0 & 86.1 &    0 &   12517.4 &      {\bf 75.03} \\
\hline
\end{tabular}
\end{table}

In order examine asymptotic behavior of the proposed algorithm, we proceed with the third stage of our experiment. 
As it follows from Tables \ref{tbl:3} and \ref{tbl:4}, increasing of the time limit leads to the notably better results. Thus, the number of instances solved to optimality has increased in average by $6.36\%$ for the instances of $(20,0.25)$, by $15.45\%$ for $(20,0.5)$, by $12.73\%$ for $(20,0.75)$, by $22.72\%$ for $(30,0.25)$, by $5.45\%$ for $(30,0.5)$, and by $3.63\%$ for $(30,0.75)$.
In particular, allowing more computation time implies the ability to solve to optimality several complex instances within the following groups (see Fig.\ref{fig:1}): $(30,0.5,5\cdot 10^{-5})$, $(30,0.5,1\cdot10^{-5})$, $(30,0.75,1\cdot10^{-1})$, $(30,0.75,5\cdot10^{-2})$, $(30,0.75,1\cdot10^{-2})$, $(30,0.75,5\cdot10^{-3})$. 
 
In turn, the average gap values have decreased by $5.59\%$ for the instances of $(20,0.25)$, by $8.35\%$ for $(20,0.5)$, by $11.98\%$ for $(20,0.75)$, by $10.77\%$ for $(30,0.25)$, by $13.82\%$ for $(30,0.5)$, and by $14.94\%$ for $(30,0.75)$. As it follows from the stage three results, there is significant enhancement even for hard instances such as those ones of $|V|=30$, $\gamma=0.75$, and $\F\leq5\cdot10^{-5}$. In addition, for groups $(20,0.25,5\cdot10^{-3})$, $(20,0.25,1\cdot10^{-3})$, and $(20,0.25,5\cdot10^{-4})$, the average gaps were decreased more than 10 times (see also Fig.\ref{fig:2}). 

\begin{figure}[h]
\centering

\includegraphics[width=0.49\textwidth]{images/hist_20_10hours.png}
\includegraphics[width=0.49\textwidth]{images/hist_30_10hours.png}

\caption{The number of instances solved to optimality  for (a): 20 nodes and (b): 30 nodes in 10 hours}\label{fig:1}
\end{figure}

% However, the results presented in Table \ref{tbl:3} and on Figure \ref{fig:1} demonstrate that the number of optimally solved instances is rapidly decreased with density and graph nodes growth and failure threshold shrinking. Especially it concerns the instances of $|V|=30$ nodes, $\gamma=0.75$ and $\F\in\{10^{-3}, 5\cdot10^{-4}, 10^{-4}, 5~\cdot~10^{-5}, 10^{-5},\\
%  5~\cdot~10^{-6}, 10^{-6}\}$. The number of branching nodes grows significantly as well. 
% The average gap values depending on failure threshold are depicted in Fig.\ref{fig:2}. It can be seen, that for $\F\leq5\cdot 10^{-4}$ and any $|V|\in\{20,30\}$ and $\gamma\in{0.25,0.5,0.75}$ the average gap values increase unsignificantly. However, for $\F\geq1\cdot10^{-4}$, these values grow rapidly. To improve even more the quality of $A_{E2TRP}$ it can be added a group of valid inequalities and cutting planes. We proceed with this challenge in the future work.

% that the average gaps uniformly increases for $|V|=20$ nodes and have essential increasing for $|V|=30$ nodes and failure threshold $\F\leq5\cdot10^{-5}$ (see Fig. \ref{fig:2}). To improve the gap values and reduce the size of the branching tree it can be added a group of valid inequalities. We proceed with this one in the future work.
% Generally, the number of optimally solved instances for $|V|=30$ nodes and $\gamma\in\{0.5,0.75\}$ is less than for the instances of other parameters (see Fig. \ref{fig:1}).
 

% \begin{figure}[H]
% \centering
% \subfloat[]{
% \includegraphics[width=0.6\textwidth]{images/gap_20_1hour.png}
% }
% \subfloat[]{
% \includegraphics[width=0.6\textwidth]{images/gap_30_1hour.png}
% }
% \caption{Accuracy gap for 20 and 30 nodes in 1 hour}
% \end{figure}

\begin{figure}[h!]
\centering

\includegraphics[width=0.49\textwidth]{images/gap_20_10hours.png}
\includegraphics[width=0.49\textwidth]{images/gap_30_10hours.png}

\caption{Average gaps for (a): 20 and (b): 30 nodes and time limit of 10 hours}\label{fig:2}
\end{figure}