Instance Space Analysis of the Capacitated Vehicle Routing Problem with Mixture Discriminant Analysis

In this paper, we attempt a deeper understanding of the relative performance of two state-of-the-art metaheuristic solvers for the capacitated vehicle routing problem (CVRP). To this end, we employ a novel CVRP instance generator to expand the set of CVRP instances used to assess heuristics. This generator modifies existing problem instances using the outliers of node clusters to produce relevant new CVRP instances. We consider a large number of features to characterise each problem instance, and propose to use mixture discriminant analysis (MDA) to obtain both a low dimensional representation of the instance space and a classifier of algorithm performance. MDA has not been previously used in instance space analysis, and as a supervised dimension reduction method has the advantage that the tasks of dimension reduction and classification are handled in a unified framework (rather than two separate steps). The resulting predictive models perform as well as more complex classifiers that involve more tuning parameters and are computationally more expensive (like support vector machines). Our analysis highlights that the performance comparison between the two CVRP metaheuristics is nuanced and the best algorithm depends on the time budget, as well as certain key characteristics of the problem instance.