## 3 Methodology
### Clustering Features
#### 3.1.3 Analysis of Extracted Features  
The feature extraction process aims to describe a problem instance through numerical values. A quality set of features must be enough to distinguish dissimilar instances from each other and to group similar instances. As Homberger instances are grouped into subsets with different characteristics, we can validate the quality of our proposed feature set by clustering the instances concerning different feature subsets and checking whether we obtain a grouping similar to the a priori grouping defined at the instance sets creation. Figure 2: dynamicOPTICS clustering of Homberger instances. Black points are outliers not belonging to any cluster. Corresponding min_samples values are displayed at the top of each problem instance. For this purpose, k-means (Lloyd's Algorithm) was chosen to obtain high-quality clustering results for a given number of clusters on each execution. In preliminary experiments, spectral clustering [23] was briefly tested, but was discarded because it showed noisier results. For each execution, k-means was run with 1000 random centroid initializations, and the result of minimal inertia was chosen. All feature values were normalized to a [0, 1] range before clustering to equalize the weight of each feature. We validated the extracted features on the Homberger instances set. We first validated each feature subset independently (spatial, demand, and clustering features). Clustering with time window features was attempted, but it produced noisy results due to the wide variance of the randomly allocated time-windows. We conclude by presenting the clustering results using all the extracted features. Figure 3 shows the clustering results of all 300 Homberger instances using only spatial features, with \(k=3\). Both the _average_distance_to_centroid_ and _cv_distance_to_centroid_ features were discarded as they are perfectly correlated to depot-based features. In Figure 3, each column corresponds to a given number of clients, while each row shows five subsets of ten instances each. The instances in these subsets differ only in their time window allocation. From this, we notice a successful clustering process using spatial features to discriminate between small, medium, and large problem instances. Larger values of \(k\) do not produce more granular distinctions between instance sizes. This is likely due to the lack of inter-instance variance in depot- and centroid-related features. Clustering concerning the two demand-related features yields a perfect separation between the three vehicle capacity values in the subsets (see Figure 4). We notice, for the \(capacity=200\), subsets C1, \(R1\), and \(RC1\) are grouped together. Moreover, for the \(capacity=700\), subset C2 is in its cluster, and for the \(capacity=1000\) subsets, \(R2\) and \(RC2\) are clustered together. Figure 5 shows clustering regarding client-clustering-related features. Instances in yellow are easily clustered, those in blue are difficult to cluster, and the pink ones do not present clear client clustering. Most importantly, these clustering results are robust to the exclusion of the _optimal_min_samples_ feature, indicating that the remaining clustering features adequately measure the clusterability of the instanc  
Figure 3: Clustering of Homberger instances with three clusters, using only spatial features. The clustering results of Homberger instances with all extracted features and \(k=3\) are shown in Figure 6 and \(k=4\) are shown in Figure 7. The correct clustering of C1 instances is most noticeable, as these are the most different from all others due to their distinctive client distributions. In order to understand the differences between clusters 2, 3, and 4, we present Table 2, listing the most decisive features. Only features that present high inter-instance differences have been included. _Low_ and _High_ values are strictly relative. Cluster 4 correctly groups together instances that contain either large or sparse client-clusters; these instances also present high vehicle capacities.