Instance space analysis of the capacitated vehicle routing problem
This work provides a new method for instance analysis in the CVRP field, which is incremental as it applies an existing ISA methodology to a specific domain problem.
The paper tackled the challenge of understanding how instance characteristics affect metaheuristic performance in the capacitated vehicle routing problem (CVRP), resulting in the identification of 23 relevant characteristics and the creation of a two-dimensional projection of the instance space using Instance Space Analysis (ISA).
This paper seeks to advance CVRP research by addressing the challenge of understanding the nuanced relationships between instance characteristics and metaheuristic (MH) performance. We present Instance Space Analysis (ISA) as a valuable tool that allows for a new perspective on the field. By combining the ISA methodology with a dataset from the DIMACS 12th Implementation Challenge on Vehicle Routing, our research enabled the identification of 23 relevant instance characteristics. Our use of the PRELIM, SIFTED, and PILOT stages, which employ dimensionality reduction and machine learning methods, allowed us to create a two-dimensional projection of the instance space to understand how the structure of instances affect the behavior of MHs. A key contribution of our work is that we provide a projection matrix, which makes it straightforward to incorporate new instances into this analysis and allows for a new method for instance analysis in the CVRP field.