## 3 Results  
Computational experiments were performed on a computer with an Intel i7-5960X, 3.00 GHz processor and 32 GB of RAM. The matheuristics was implemented in Python 3.7, and all optimization problems were solved using the correspondent Python API of the commercial solver Gurobi version 9.1.1. In our experiments, we used 21 problems taken from set P of benchmark problems from [34], which are publicly available at www.coin-or.org/SYMPHONY/branchandcut/VRP/data/ (accessed on 10 January 2022). The size of problems ranges between 16 and 101 nodes including the depot. All problem instances are very tight capacity constrained, since the proportions of the demand on the capacity (the tightness) \(\tau=\dfrac{\sum_{i=1}^{n}d_{i}}{p\,Q}\) are close to 1.0. To test and analyze the proposed solution method, we have implemented the original KS framework (referred to as KS-O), and two variants of KS-CVRP: basic variant with an initial CWS solution, and its iterative variant with an iterative improvement procedure (denoted as KS-CVRP1 and KS-CVRP2, respectively). Because the setting of the algorithm parameters influences the trade-off between computational effort and solution quality, numerous preparatory experiments were accomplished on benchmark instances to achieve desired control parameters of the aforementioned implementations of KS, but without a serious statistical evaluation. Tuning an appropriate number of created buckets was especially challenging, as it affects the computational time required for solving the restricted MILP problem. The larger the value is, the greater the number of sub-problems of a smaller size has to be solved. It means that the algorithm works faster, but at the cost of a lower quality result. The experiments indicated that the value of \(N_{b}\) has to be accommodated to each problem instance individually. Regarding the criterion used to sort the variables in the bucket list, we have considered three different approaches: a non-decreasing order of \(s_{ij}\) (Sorting A), a non-increasing order of \(c_{ij}\) (Sorting B), and a random order (Sorting C), respectively. The preliminary experiments showed that the best performing criterion was Sorting B. For each restricted MILP problem, the maximum running time assigned to Gurobi optimizer was set to 1800 s, and the loop of the iterative improvement procedure was stopped after three iterations without any improvement. Below, only the main results of the experiments performed are presented and commented on. The results reported in Table 1 compare the performance of three variants of KS in terms of computational time. Such analysis could only be done for the small-sized instances (\(n<50\)), as KS-O requires huge computational times to solve large problems. For each instance, the number of nodes (\(n\)) and vehicles (\(p\)) are given, as well as the tightness (\(\tau\)), and the optimal solution value (\(Opt\)) known from literature. For all the tested variants, we have assumed the same number of buckets (\(N_{b}\)) adapted to the size of the problem instance. The next columns provide the objective values obtained by particular KS variant (\(z^{*}\)), and the computational time in seconds (_Time_). This result seems to show that the variant KS-CVRP2 dominates over the average variant KS-CVRP1 which, in turn, outperforms KS-O. Table 2 shows a summary of the results obtained by KS-CVRP2, where the following quantities are shown: the instance parameters (\(n\), \(p\), \(\tau\)), the optimal solution value (\(Opt\)), the parameters of the CWS algorithm (\(\lambda\), \(\mu\), \(\
u\)), the initial solution value (\(z^{\text{c}us}\)), the number of buckets (\(N_{b}\)), the parameter of the iterative improvement procedure (\(\delta\)), the objective value produced by KS-CVRP2 (\(z^{*}\)), the average percentage gap (\(Gap\)) computed as \(Gap=z^{*}-Opt\) 100, and the computational time in seconds (\(Time\)). We can observe that the proposed matheuristics KS-CVRP2 achieves very good results in an acceptable amount of time.