What makes a solution good? Datasets for the vehicle routing problem

For many combinatorial optimization problems, heuristics based on either local search or constructive strategies have been demonstrated to provide the best trade-off between solution quality and computation time. In recent years, it has become apparent that the efficiency of a heuristic strategy depends to a large extent on how well it is able to exploit the characteristics of the problem being solved. In other words, to be as efficient as possible, heuristic search strategies require some knowledge on what distinguishes a good solution from a not-so-good solution.

We used a data-mining based approach that can generate such knowledge and applied it to the vehicle routing problem (VRP). For this study, we generated datasets that incorporate several metrics to characterize both a VRP solution and a VRP instance. Each dataset is characterized by the gap between the good and not-so-good solution, as well as the properties of the considered VRP instance. One row is composed of a indicator for whether the solution is good (1) or not (0), the solution metrics (columns 2-11) and the instance metrics (columns 12-19). The datasets and all metrics are defined in the working paper.

file.datasets

What makes a solution good? Datasets for the vehicle routing problem
Tagged on: