Kernel Search for the Capacitated Vehicle Routing Problem

Abstract

This paper addresses the Capacitated Vehicle Routing Problem (CVRP), which is a widely studied optimization problem due to its relevance to the field of transportation, distribution, and logistics. We present a matheuristic method for CVRP that adopts the main idea of the Kernel Search algorithm (KS) based on decomposing the original problem into sub-problems that are easier to solve. Unlike the original scheme of KS, our approach uses the Clarke–Wright savings algorithm to construct a sequence of smaller sub-problems, which are subsequently solved using mathematical programming strategies. The computational experiments performed on a set of benchmark instances showed that the proposed matheuristics achieves good results in acceptable computational time.

1. Introduction

The Capacitated Vehicle Routing Problem (CVRP), which is the focus of the study presented, is a classical operations research problem that can be described as a problem of designing routes for several vehicles traveling from a depot to a set of geographically dispersed customers and then returning back to the depot. The goal is to choose routes to serve all customers at a minimum total transport cost, without exceeding the vehicle capacity.

CVRP falls into the category of NP-hard problems, which are computationally difficult, and no algorithm is known to have solved them in polynomial time. Depending on their size, two main approaches are considered to handle this class of problems. For fairly small-sized instances, researchers usually use exact methods. Exact methods are guaranteed to find an optimal solution, but they have a high time complexity. Therefore, heuristics and particularly metaheuristics are applied to large-scale problems. These methods can obtain good results within shorter execution time. However, they do not guarantee the solution optimality. For a few decades, hybrid algorithms that combine different algorithmic concepts have been successfully applied to a wide range of optimization problems. A special class are matheuristics, where metaheuristics are hybridized with exact methods based on mathematical programming. Since the matheuristics have the advantages of both exact and heuristic methods, they are usually very effective at solving large complex optimization problems.

One of the recently developed matheuristics is Kernel Search (KS). Its strategy is to cleverly divide the solution space into smaller regions and explore them separately to find different feasible solutions. Because the most laborious part of the search relies on an optimization solver, KS is less demanding to implement than other heuristics. The matheuristic method presented in this paper applies the KS general framework to CVRP.

2. Materials and Methods

This part begins with a brief literature review. Then, the definition and mathematical formulation of the CVRP are presented. Finally, the details of the proposed matheuristics are provided.

2.1. Literature Review

CVRP was introduced by Dantzig and Ramser in 1959 [1] under the term of “the truck dispatching problem”, to formulate a real-world problem concerning the distribution of gasoline to service stations. Following this work, many studies have been carried out to solve CVRP, and they proposed various exact and heuristic (approximate) methods. General surveys can be found in [2]. The most successful exact methods are branch-cut-and-price algorithms [3,4,5]. As CVRP is NP-hard, most of the methods developed for this problem are heuristic, metaheuristic and hybrid methods. The state-of-the-art algorithms are the iterated local search with the set partitioning [6], the knowledge-guided local search [7], the fast iterated localized optimization [8], the slack induction by string removals [9], the partial optimization metaheuristic under special intensification conditions [10], and the hybrid adaptive iterated local search with diversification control [11]. The overview and classification of several matheuristic approaches proposed for routing problems are provided in [12].

KS was firstly published by Angelelli et al. [13] as “a heuristic framework for Mixed Integer Linear Programming (MILP) problems with binary variables”, and applied to solve the multi-dimensional knapsack problem [14]. Further applications included several different problems, e.g., the portfolio optimization [15], the capacitated facility location problem [16,17], the index tracking [18] and the Bi-objective index tracking [19], the capacitated p-median problem [20], the multivehicle inventory routing problem [21], or the generalized assignment problem [22]. As far as we know, no literature has reported the application of KS to CVRP so far.

2.2. The Problem Formulation

CVRP is defined on a complete directed graph $G=(V,E)$, where $V=\{0,1,\dots ,n\}$ is a set of nodes and $E=\left\{\right(i,j)\in V\times V,i\ne j\}$ is a set of arcs. The node 0 represents the depot for a fleet of p vehicles with the identical capacity Q, and the remaining n nodes represent customers, each with the demand $d_i,i\in V-\left\{0\right\}$. Every arc $(i,j)\in E$ is associated with the positive travel cost $c_{ij}$. We assume that the cost matrix is symmetric, i.e., $c_{ij}=c_{ji}$ for all $i,j\in V,i\ne j$, and it satisfies the triangular inequality, $c_{ij}+c_{jl}\ge c_{il}$ for all $i,j,l\in V$. The aim is to determine a minimum-cost set of p routes in order to satisfy the demands of all customers under the following constraints [23]:

(a)

Each route starts and ends at the depot,

(b)

Each customer is visited exactly once,

(c)

The total demand of all customers on any route must not exceed the vehicle capacity.

An illustrative example of a feasible CVRP solution is shown in Figure 1, where 7 customers (their demands are displayed next to the nodes) are served by three vehicles of the capacity 50. The arc labels correspond to travel costs between the nodes, so the total transport cost is 30.

The following mathematical model is taken from [24]. Two-index binary variables $x_{ij}$ are used as decision variables equal to 1 if arc $(i,j)$ belongs to the optimal solution and 0 otherwise. Additional continuous variables $y_i$ are defined for all $i\in V-\left\{0\right\}$, which model the load in the vehicle after it visits customer i. The mixed linear programming model of the CVRP can be stated as:

• MILP model of the CVRP

$$\begin{array}{cccc}\hfill \mathrm{minimize}& \sum _{(i,j)\in E}{c}_{ij}{x}_{ij},\hfill & & \hfill \end{array}$$

(1)

subject to

$$\begin{array}{cccc}& \sum _{\genfrac{}{}{0pt}{}{j\in V}{i\ne j}}{x}_{ij}=1,\hfill & \hfill \forall i\in V-\left\{0\right\},& \hfill \end{array}$$

(2)

$$\begin{array}{cccc}& \sum _{\genfrac{}{}{0pt}{}{j\in V}{i\ne j}}{x}_{ji}=1,\hfill & \hfill \forall i\in V-\left\{0\right\},& \hfill \end{array}$$

(3)

$$\begin{array}{cccc}& \sum _{j\in V-\left\{0\right\}}{x}_{0j}=p,\hfill & & \hfill \end{array}$$

(4)

$$\begin{array}{cccc}& \sum _{i\in V-\left\{0\right\}}{x}_{i0}=p,\hfill & & \hfill \end{array}$$

(5)

$$\begin{array}{cccc}& y_i+d_j-y_j\le (1-x_{ij})Q,\hfill & \hfill \forall i,j\in V-\left\{0\right\},i\ne j,& \hfill \end{array}$$

(6)

$$\begin{array}{cccc}& d_i\le y_i\le Q,\hfill & \hfill \forall i\in V-\left\{0\right\},& \hfill \end{array}$$

(7)

$$\begin{array}{cccc}& x_{ij}\in \{0,1\},\hfill & \hfill \forall (i,j)\in E.& \hfill \end{array}$$

(8)

The objective function (1), to be minimized, is the total transport cost. The constraints (2)–(5) are the degree constraints for the depot and customers, respectively. The constraints (6) impose both the capacity and connectivity of the feasible routes and also guarantee that sub-tours are avoided. The constraints given in (7) restrict the upper and lower bounds of $y_i$. Lastly, the obligatory constraints (8) express the binary requirements on the variables.

2.3. 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 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,\cdots ,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).

Algorithm 1 The KS framework [21]

Initialization phase 1: Solve the LP relaxation. 2: Construct an initial kernel and a sequence of buckets. 3: Solve a MILP problem on the initial kernel. Improvement phase 4: while a certain number of buckets not analyzed do 5:     Solve a MILP problem on the current kernel plus a bucket. 6:     Update the current kernel.

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\ne 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 Clarke and Wright (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. Linking two routes, one with the arc $(i,0)$ and another with the arc $(0,j)$, results in the cost of

$$s_{ij}=c_{i0}+c_{0j}-c_{ij}.$$

(9)

The CWS algorithm iteratively merges pairs of routes maximizing cost savings $s_{ij}$ subject to the merged route feasibility (respecting the capacity restriction). There are two versions of CWS: sequential and parallel. In the sequential version, routes are expanded one at a time, until they are no longer feasible, whereas in the parallel version, several routes are built at the same time. According to [2], the parallel version usually offers better results than the sequential one.

Due to its greedy nature, the CWS heuristics is not the most accurate. In order to achieve solutions with better qualities, the savings Formula (9) has been modified by adding new terms and parameters to it, as follows:

$$s_{ij}=c_{0j}+c_{i0}-\lambda c_{ij}+\mu |c_{0i}+c_{j0}|+\nu \frac{d_i+d_j}{\overline{d}}.$$

(10)

Here, $\lambda$ is a route shape parameter [27,28] that controls the relative significance of the distance between two customers, $\mu$ is a weight parameter [29] that takes into account the asymmetry between two merged customers in terms of their distances from the depot, and $\nu$ is a customer demand parameter [25] that prefers customers with larger demands relative to the average demand $\overline{d}$, i.e., ${\displaystyle \overline{d}={\displaystyle \frac{{\sum }_{i=1}^n{d}_i}{n}}}$.

To adjust the specific values of these three independent parameters, the authors evaluated 8820 different parameter vectors ($\lambda ,\mu ,\nu$) by varying $\lambda \in \langle 0.1,2\rangle$, and $\mu ,\nu \in \langle 0,2\rangle$, respectively, with a step size of 0.1. Later, a genetic algorithm [30], and empirically adjusted greedy heuristics [31] were used as the parameter tuning procedures, which required much shorter computing times. In our implementation, the Taguchi method [32] was applied to set the parameter values for the parameterized CWS algorithm.

The initialization phase of KS-CVRP works as follows: a parameterized CWS method is used to find the initial feasible solution of CVRP, and its value is saved as the initial upper bound $z^{*}$. All the variables $x_{ij}$ corresponding to the arcs $(i,j)$ between customers i and j that belong to the found CWS solution are taken to create the initial kernel K. Variables $x_{ij},i,j\in V,i\ne j$ not present in the kernel are ranked according to a suitable criterion reflecting the variable likelihood to be included in the optimal integer solution. Subsequently, a sequence of buckets with these such ordered variables is created.

Buckets ${\left\{B_i\right\}}_{i=1}^{N_b}$ are iteratively explored during the improvement phase. At each iteration a modified MILP sub-problem is solved on the union of the current kernel and the processed bucket $B_i$. Reminder: we are only seeking such a solution that is better than the current best one, and that uses at least one new item from the current bucket. Figure 3 illustrates the evolution of solution improvement of problem instance No. 8 with 40 nodes, two vehicles, and 11 buckets. Because the original KS (KS-O) did not find an initial feasible solution, the initial value is infinity (in the picture represented by value of 618). This method reached the first feasible solution only in the third iteration. KS-CVRP starts from the initial solution with a value of 464. While KS-O achieved the optimal solution (value of 458) after exploring all buckets, KS-CVRP was enough to explore the first bucket.

Regarding the latter constraint, in case of large-sized instances, a time limit must be set to solve each restricted problem. Therefore, some of these problems may not be solved optimally within the specified time. To facilitate computing, we devised an iterative improvement procedure that utilizes the strategy of the Exact Iterative Method for CVRP (EIM-CVRP) [33]. This method is based on so-called k-opt moves, where k edges in the current solution are replaced by a set of k different feasible edges in such a way that a better solution is achieved. Given a feasible solution, EIM-CVRP repeatedly performs k-opt moves that reduce the cost of the current solution, until a solution is reached for which no exchange yields an improvement. The value of k is changed adaptively throughout the search with step $\delta$ as the procedure parameter. The Algorithm 2 summarizes the mentioned procedure adapted to the KS-CVRP in pseudocode.

Algorithm 2 The iterative improvement procedure

Input: Kernel K, bucket $B_i$, current best solution $s^{*}$, cut-off value $z^{*}$, and parameter $\delta$. Output: Optimal solution $z_i$ and its value $s_i$.  1: $s_i\leftarrow s^{*}$  2: $z_i\leftarrow z^{*}$  3: $E\leftarrow B_i$  4: $m_1\leftarrow 1$  5: $m_2\leftarrow m_1+\delta$  6: while$m_1\le \left|B_i\right|$do  7:     Solve MILP($K\cup B_i$) with additional constraints:       Set an objective function cut-off value to $z_i$       Use k variables from E, where $m_1\le k\le m_2$  8:     if modified MILP($K\cup B_i$) is feasible with solution s and value z then  9:         $s_i\leftarrow s$ 10:         $z_i\leftarrow z$ 11:         Update E by removing all variables with positive value in $s_i$ 12:     else 13:         $m_1\leftarrow m_2+1$ 14:         $m_2\leftarrow m_1+\delta$

Of course, the procedure can be terminated after a predetermined computational time, or a certain number of iterations without any improvement. If $z_i<z^{*}$, it means that the found solution $s_i$ improves the current best one and so $z^{*}$ and $s^{*}$ are updated. Additionally, the kernel content is extended by adding the newly discovered variables, which have a non-zero value in the solution $s_i$.

When all buckets have been explored, the recent best-found solution $s^{*}$ and its value $z^{*}$ are returned as the final output.

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) ${\displaystyle \tau ={\displaystyle \frac{{\sum }_{i=1}^n{d}_i}{pQ}}}$ 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. Comparison of computational times.

Instance						KS-O		KS-CVRP1		KS-CVRP2
$\mathit{id}$	$\mathit{n}$	$\mathit{p}$	$\mathit{\tau }$	$\mathit{Opt}$	${\mathit{N}}_{\mathit{b}}$	${\mathit{z}}^{*}$	$\mathit{Time}$(s)	${\mathit{z}}^{*}$	$\mathit{Time}$(s)	${\mathit{z}}^{*}$	$\mathit{Time}$(s)
1.	16	8	0.88	450	2	450	0.560	450	0.254	450	0.460
2.	19	2	0.97	212	2	215	5.067	212	2.310	212	1.056
3.	20	2	0.97	216	2	216	2.361	216	1.930	216	1.022
4.	21	2	0.93	211	3	211	1.471	211	0.519	211	0.514
5.	22	2	0.96	216	3	216	1.106	216	0.730	216	0.467
6.	22	8	0.94	603	3	603	31.667	603	4.057	603	1.044
7.	23	8	0.93	529	2	538	1039.707	547	823.919	547	310.329
8.	40	5	0.88	458	11	458	4772.603	458	327.663	458	3.336
9.	45	5	0.92	510	12	584	17,098.917	520	1803.467	510	5.205

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. Results for KS-CVRP2.

Instance					CWS				KS-CVRP2
$\mathit{id}$	$\mathit{n}$	$\mathit{p}$	$\mathit{\tau }$	$\mathit{Opt}$	$\mathit{\lambda }$	$\mathit{\mu }$	$\mathit{\nu }$	${\mathit{z}}^{\mathit{cws}}$	${\mathit{N}}_{\mathit{b}}$	$\mathit{\delta }$	${\mathit{z}}^{*}$	$\mathit{Gap}$(%)	$\mathit{Time}$(s)
1.	16	8	0.88	450	0.4	1.2	0.0	456	2	4	450	0.00	0.460
2.	19	2	0.97	212	1.1	0.9	1.8	228	3	4	212	0.00	1.056
3.	20	2	0.97	216	1.3	0.9	0.0	227	3	4	216	0.00	1.022
4.	21	2	0.93	211	1.9	0.7	0.3	216	3	4	211	0.00	0.514
5.	22	2	0.96	216	1.7	0.2	0.8	218	3	4	216	0.00	0.467
6.	22	8	0.94	603	0.2	1.1	0.3	628	3	4	603	0.00	1.044
7.	23	8	0.98	529	0.1	0.1	1.9	592	1	2	529	0.00	20.021
8.	40	5	0.88	458	1.3	0.9	0.7	464	11	4	458	0.00	3.336
9.	45	5	0.92	510	1.4	0.3	0.8	520	12	4	510	0.00	5.205
10.	50	7	0.91	554	1.5	0.2	0.5	575	3	2	554	0.00	192.114
11.	50	10	0.95	696	1.8	1.1	1.6	712	10	2	697	1.14	266.805
12.	51	10	0.97	741	0.9	0.2	1.0	756	20	4	742	0.13	50.614
13.	55	7	0.88	568	1.4	0.3	1.5	584	23	2	575	1.23	26.845
14.	55	10	0.91	694	1.9	0.0	1.9	709	22	4	701	1.01	28.086
15.	60	10	0.95	744	0.4	0.9	1.6	773	11	2	746	0.27	651.237
16.	60	15	0.95	968	1.1	0.0	0.9	1019	5	4	972	0.41	356.353
17.	65	10	0.94	792	1.4	0.4	0.1	815	23	4	799	0.88	92.782
18.	70	10	0.97	827	1.5	0.0	1.8	849	8	4	833	0.73	84.718
19.	76	4	0.97	593	1.5	0.3	0.6	626	5	3	601	1.35	2087.261
20.	76	5	0.97	627	1.7	0.5	0.0	651	6	2	629	0.32	659.379
21.	101	4	0.91	681	0.1	1.0	0.0	693	9	4	682	0.15	265.871

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$, $\nu$), the initial solution value ($z^{cws}$), 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 ${\displaystyle Gap={\displaystyle \frac{z^{*}-Opt}{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. It was able to solve to optimality all 10 small-sized instances ($n<50$), and for medium-size instances ($50\le n\le 101$), the gaps are within $1.5\%$ of the optimal solution. The computation time does not exceed 1 h.

Table 3. Comparison of the KS-CVRP2 and the EIM-CVRP.

Instance						EIM-CVRP		KS-CVRP2
$\mathit{id}$	$\mathit{n}$	$\mathit{p}$	$\mathit{Opt}$	${\mathit{z}}^{\mathit{cws}}$	$\mathit{\delta }$	$\mathit{Gap}$(%)	$\mathit{Time}$(s)	${\mathit{N}}_{\mathit{b}}$	$\mathit{Gap}$(%)	$\mathit{Time}$(s)
1.	16	8	450	456	4	0.00	0.312	2	0.00	0.213
2.	19	2	212	228	4	0.00	0.700	3	0.00	0.617
3.	20	2	216	227	4	0.00	2.650	3	0.00	0.561
4.	21	2	211	216	4	0.00	0.237	3	0.00	0.167
5.	22	2	216	218	4	0.00	0.372	3	0.00	0.190
6.	22	8	603	628	4	0.00	0.617	3	0.00	0.380
7.	23	8	529	592	2	0.00	21.540	1	0.00	14.461
8.	40	5	458	464	4	0.00	29.893	11	0.00	1.515
9.	45	5	510	520	4	0.00	8.238	12	0.00	2.056
10.	50	7	554	575	2	0.00	463.060	3	0.00	113.440

compares the KS-CVRP2 and the EIM-CVRP in terms of the time consumption to reach the optimal solution. The EIM-CVRP ran under the same conditions as KS-CVRP2, i.e., with a time limit of 1800 s and a stopping criterion of three iterations without any improvement. Additionally, the initial solution and procedure parameter $\delta$ for particular test instances were identical for both methods. As expected, the KS-CVRP2 is quicker than EIM-CVRP. It is because, unlike the KS-CVRP2, the EIM-CVRP explores the whole solution space at each iteration. Figure 4 shows an example of the solution improvement over time by both methods for test instance No. 8.

4. Conclusions

In this paper, we presented the implementation of the matheuristics kernel search to solve the capacitated vehicle routing problem called KS-CVRP. Compared to the original KS framework, a different method has been proposed to construct the kernel and buckets, as well as to carry out the improvement phase so that the time available to find good solutions is used more efficiently. The computational experiments conducted on benchmark instances have shown that KS-CVRP is able to find high quality solutions in reasonable computation times.

The application of the algorithm to other routing problems will be the topic of our future research.