Characterization of Vehicle Routing Problem Instances: Challenges and Opportunities

This paper investigates the characterization of instances of the Capable Vehicle Routing Problem (CVRP), with the objective of identifying patterns that enable the choice and configuration of metaheuristics (MHs). To this end, we analyzed twelve data sets present in the CVRPLIB library, using six descriptors, five of which were based on distance and the sixth on the Hopkins coefficient. This analysis aims to investigate the heterogeneity of CVRP instances present in the literature. The methodology adopted by this study is inspired by the extit{Instance Space Analysis} (ISA) approach. We conclude that the process of characterization of CVRP instances still needs improvements, especially in relation to the specification of descriptors, that is, the identification of what should be measured. We encourage the discussion of the importance of creating new instances through a structured process so that the instances generated highlight the strengths and weaknesses of the MHs.