Instance space analysis of the capacitated vehicle routing problem

These features aim to answer the question: "What is the general shape of the problem and how does the arrangement of the nodes influence its optimization difficulty?". The following features are used to analyze the geometry of the problem: G1: Area of the enclosing rectangle [11], [12] G2: Convex hull area [12], [15] G3: Ratio of points on the hull [12], [15] G4: Distance of enclosed points to the convex hull contour [12] G5: Edge lengths of the convex hull 5) Nearest neighborhood (NN) features: This features' category regards relationships between each node and its nearest neighbors, capturing the local search space structure and node connectivity. Unlike MST or geometric features, which focus on overall structure, NN features focus on relationships between a node and its closest nodes. These features aim to answer the question: "How are nodes connected to each other in their immediate neighborhoods, and how do these connections influence the optimization difficulty?". The following features are used to describe the neighborhood of each node: NN1: Distance to 1st NN [11], [15] NN2: Number of strongly connected components [16] NN3: Number of weakly connected components [16] NN4: Size of strongly connected components [16] NN5: Size of weakly connected components [16] NN6: Node input degree in directed kNN graph [16] NN7: Ratio of number of strongly and weakly connected components [16] NN8: Angles between a node and its two nearest neighbor nodes [12] 6) VRP Specific Features: This category of features is composed by values obtained directly from the parameter values of the VRP instances, such as vehicle capacity, customer demands, etc.