# Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows
## 5 Computational Experiments
### Numerical Results  
In the following we provide a detailed comparison of the following methods. First, we applied both CPLEX (version 12.10) and our C&W savings heuristic to all problem instances. Hereby, CPLEX was given a time limit of 2 h of CPU time for each problem instance. Next we also applied two versions of VNS. The full version of VNS is henceforth denoted by \(\text{VNS}_{\text{full}}\). In contrast, \(\text{VNS}_{\text{red}}\) is a reduced version of VNS that only utilizes classical inter-route and intra-route shaking operators. A comparison of these two variants is interesting, because it shows how much the destroy and repair operators add to the performance of VNS. Note that both versions of VNS were applied with a computation time limit of 150 CPU seconds in the case of small problem instances, and 900 CPU seconds for large problem instances. Moreover, both versions of VNS were applied 10 times to each problem instance. Tables 5-7 show the numerical results for small problem instances with 5, 10, and 15 customers, respectively. The structure of these tables is as follows. Instance names are given in the first column, and the maximum number of vehicles in the first and second echelons are provided in the second and third columns, respectively. These numbers are only necessary for the application of CPLEX. After the first three table columns, there are four blocks of columns, presenting the results of our four approaches. The first three columns of each block (with headings '_n_', '_m_', and 'dist') are the same for all four approaches. Hereby, columns '_n_' and '_m_' provide the number vehicles utilized by the respective solutions in the first echelon and the second echelon, respectively. In the case of \(\text{VNS}_{\text{full}}\) and \(\text{VNS}_{\text{red}}\) these numbers refer to the best solution found within 10 independent runs. Column 'dist' provides the objective function values of the solutions generated by the four approaches. In the case of \(\text{VNS}_{\text{full}}\) and \(\text{VNS}_{\text{red}}\), 'dist' shows the objective function value of the best solution found in 10 runs, while an additional column with the heading 'avg' provides the average objective function value of the best solutions of each of the 10 runs. Next, columns with heading '\(\overline{t(s)}\)' show the computation time of CPLEX, our C&W savings heuristic and the average computation times of \(\text{VNS}_{\text{full}}\) and \(\text{VNS}_{\text{red}}\) to find the best solutions in each run. Finally, column 'gap(%)' provides the gap (in percent) between the best solution and the best lower bound found by CPLEX. Note that, in the case where the gap value is zero, CPLEX has found an optimal solution. \begin{table}
\begin{tabular}{c c c|c c c c|c c c c|c c c c|c c c c c|c c c c} \hline \hline \multicolumn{1}{c|}{**Instances**} & \multicolumn{5}{c|}{**CPLEX**} & \multicolumn{5}{c|}{**C\&W Savings Heuristic**} & \multicolumn{5}{c|}{\(\text{VNS}_{\text{red}}\)} & \multicolumn{5}{c}{\(\text{VNS}_{\text{full}}\)} \\
**Name** & \(\text{\  
The following observations can be made: First, apart from instances R103_C10, RC102_C10, and RC108_C10, CPLEX was able to solve the mathematical model--within 2 h of CPU time--for all instances with five and ten customers to optimality. For two of the remaining three cases, CPLEX was able to provide feasible solutions of the same quality as VNS\({}_{\text{full}}\) and VNS\({}_{\text{red}}\), without being able to prove optimality. However, for the instances with 15 customers, the performance of CPLEX heavily starts to degrade. The reason for the rapidly decreasing performance of CPLEX is that the size and complexity of the MILP model sharply increase based on the instance size. For instance, the average number of variables and constraints of the MILP model for the instances containing five customers is 986 and 2235, respectively. These values increase to 4008 and 9363 for the instances with 10 customers and to 13,125 and 31,482 for the instances with 15 customers.