## 2 Materials and Methods
### Kernel Search  
The KS algorithm relies on partitioning the set of decision variables into smaller sub-sets and then solving a restricted version of the problem on those sub-sets. Thanks to the reduction of the solution space, the obtained sub-problem is easier to solve using the MILP solver. More specifically, KS algorithm runs through two phases: initialization and improvement (Algorithm 1). In the initialization phase, heuristics searches for the initial feasible solution. The Linear Programming (LP) relaxation of the problem is solved in order to create the initial kernel \(K\) that is composed of all variables which take a value greater than zero in the LP optimal solution. Those variables are regarded as promising because they are the most likely to belong to the original MILP optimal solution. The remaining binary variables  
Figure 1: A feasible CVRP solution. are sorted in descending order according to their reduced costs in the optimal solution to the LP relaxation: the lower the reduced cost a variable has, the more promising it is. Using this order, they are partitioned into a sequence of \(N_{b}\) sub-sets \(B_{1},B_{2},\ldots,B_{N_{b}}\), called buckets, where the number of buckets \(N_{b}\) has to be predetermined depending on the problem instance. Then the initial feasible solution is found by solving the MILP sub-problem restricted to the initial kernel, denoted by MILP(\(K\)). ```
1:Initialization phase
2:Solve the LP relaxation. 3:Construct an initial kernel and a sequence of buckets. 4:Solve a MILP problem on the initial kernel. 5:Improvement phase
6:while a certain number of buckets not analyzed do
7:Solve a MILP problem on the current kernel plus a bucket. 8:Update the current kernel. ```  
**Algorithm 1** The KS framework [21]  
The improvement phase is an iterative phase, where heuristics tries to improve the initial solution: at each iteration \(i\), a new sub-problem MILP(\(K\cup B_{i}\)) is solved with two additional constraints. The first constraint is that the objective value should be better than or equal to the objective value of the best solution found so far, whereas the second constraint requires that the solution contains at least one variable from the bucket \(B_{i}\). In the event of this restricted MILP sub-problem being feasible, the current best solution is updated and all variables in bucket \(B_{i}\) with a non-zero value in the solution of MILP(\(K\cup B_{i}\)) are added to the kernel. When all iterations have been performed, the current best-found solution is returned as the final solution. The general scheme of the KS framework needs to be adapted to the specific problem. In the next subsection, we describe the modification of KS for CVRP. Kernel Search for CVRP  
KS for CVRP (KS-CVRP) is based on the MILP model (1)-(8). The kernel and sequence of buckets are built considering only variables \(x_{ij}\) for all \(i,j\in V\), \(i\
eq j\). All the remaining variables \(x_{ij}\) and continuous variables \(y_{i}\) are included in each restricted MILP problem. As explained before, the goal of the _initialization phase_ is to construct the initial kernel and buckets. The original KS algorithm exploits the optimal solution of the continuous (or LP) relaxation of the problem. However, this way is not quite suitable for CVRP. An illustrative example in Figure 2 shows the arcs associated with variables \(x_{ij}\) that take the positive value in the optimal solution of the LP relaxation of the problem with 40 nodes and two vehicles (problem instance No. 8). Evidently, LP relaxation does not provide enough information to obtain a feasible initial solution. Hence, we decided on a different approach, utilizing a solution produced by the parameterized Clarke-Wright Savings (CWS) method [25]. The CWS algorithm, developed by [PERSON] and [PERSON] (1964) [26], is probably the most commonly used heuristics to solve CVRP because of its simplicity, speed, and easy implementation. It begins with a solution where every customer is served separately.