## 4 Experimental Setup
### Metaheuristic Parameter Tuning Step Details  
In this step, we execute a tuning algorithm to obtain suitable parameter values for the HGS metaheuristic. A tuning process is individually executed on each problem instance considered in the training set. We record the best parameter configuration found per problem instance. Different time budgets for the target algorithm can require different parameter values [32; 33]. Hence, in our experimental setup, we consider different computational efforts for the metaheuristic parameter tuning step in order to explore their effect on the prediction capabilities of the proposal.  
This work uses ParamILS [3] to tune HGS, a well-known iterated local search tuning method. From an initial parameter configuration, ParamILS searches its neighborhood by changing one parameter value each time. A discretization of parameter values is required to define reduced neighborhoods. ParamILS defines a specialized domination-based quality comparison considering both the average performance and the number of executions of each parameter configuration on a set of problem instances/seeds.  
We evaluate three parameter tuning scenarios, considering three runtime limits for HGS: 10, 30, and 60 s. The objective is to analyze HGS' convergence capability for different execution scenarios and its possible effects on the prediction of suitable configurations. For each time setting, we performed 10 independent runs of ParamILS per problem instance in the training set. We then chose the configuration that provided the best results according to ParamILS evaluation. The budget for each ParamILS execution was set to a maximum of 1000 evaluations of HGS. The quality of each HGS execution is measured as the total travel time of the best feasible solution found. Hence, ParamILS searches for the parameter configuration that allows HGS to find feasible solutions with the minimum travel times. The total tuning time to individually tune HGS with the 240 training instances and the three runtime limits was roughly 1400 h of computer time using 40 threads.  
In our experiments, we tuned five parameters of HGS:  
* \(\mu\): Minimum population size; lower bound of the number of solutions that are allowed to exist in either the feasible or unfeasible subpopulation.
* \(\lambda\): Generation size; the number of solutions over \(\mu\) allowed to exist. \(\lambda\) solutions are eliminated through a survivor selection phase once the maximum number is reached.
* \(n_{\texttt{Elite}}\): Number of elite solutions considered in the fitness calculation.
* \(n_{\texttt{Closest}}\): Number of close solutions considered in the diversity-contribution measure of the fitness solution.
* \(\xi^{\texttt{REF}}\): Target proportion of feasible individuals to total population size.  
Whereas _pyVRP_'s HGS implementation features a few additional parameters for modulating the _Penalty Manager_, only the previous five will be taken into account for our experiments, as they are the algorithm's most influential parameters.  
The parameter search space that ParamILS will search through is summarized in Table 3.  
The bold values show the best parameter values defined in [5]. The ranges of values for each parameter were obtained from the original paper [4].  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Parameter** & \multicolumn{5}{c}{**Values**} \\ \hline \(\lambda\) & 10 & 20 & **40** & 70 & 100 \\ \(n_{\texttt{Closest}}\) & 0.1 & **0.2** & 0.4 & 0.6 & 0.8 \\ \(n_{\texttt{Elite}}\) & 0.1 & 0.2 & **0.4** & 0.6 & 0.8 \\ \(\mu\) & 5 & 15 & **25** & 35 & 45 \\ \(\xi^{\texttt{REF}}\) & 0.1 & **0.2** & 0.4 & 0.6 & 0.8 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Discretization of parameters tuned. In bold are shown the parameter values suggested in [5].