Search

Highlights • A new method to solve vehicle routing through meta-learning techniques. • Two sets of meta-features are used: basic and landmarking meta-features. • A multilayer perceptron classifier is used to select meta-heuristics. • Our proposal statistically improves the overall performances previously reported. Abstract This paper describes a method for solving vehicle routing problems with time windows, based on selecting meta-heuristics via meta-learning. Although several meta-heuristics already exist that can obtain good overall results on some vehicle routing problem instances, none of them performs well in all cases. By defining a set of meta-features that appropriately characterize different routing problem instances and using a suitable classifier, our model can often correctly predict the best meta-heuristic for each instance. The main contributions of this paper are the definition of two meta-feature sets, one based on what we call 'basic' instance properties and another based on the number of feasible solutions found by perturbative heuristics via a greedy process. We use a multilayer perceptron classifier, combined with a wrapper meta-feature selection method, to predict the most suitable meta-heuristic to apply to a given problem instance. Our experimental results show that the proposed method can significantly improve upon the overall performance of well-known meta-heuristics in the field. Therefore, this paper proposes to store, share and exploit in an off-line scheme the solutions obtained in instances of different scenarios such as the academy or industry, with the aim of predicting good solvers for new instances when necessary. [ABSTRACT FROM AUTHOR]

• Features of initial solutions predict the performance of perturbation algorithms. • Low performance variation within portfolios makes algorithm selection difficult. • Hybrid selection models are useful for portfolios with low performance variation. • Accuracy is not a fair measure to evaluate the performance of algorithm selectors. In this paper, we present the construction process of a per-instance algorithm selection model to improve the initial solutions of Curriculum-Based Course Timetabling (CB-CTT) instances. Following the meta-learning framework, we apply a hybrid approach that integrates the predictions of a classifier and linear regression models to estimate and compare the performance of four meta-heuristics across different problem sub-spaces described by seven types of features. Rather than reporting the average accuracy, we evaluate the model using the closed SBS-VBS gap, a performance measure used at international algorithm selection competitions. The experimental results show that our model obtains a performance of 0.386, within the range obtained by per-instance algorithm selection models in other combinatorial problems. As a result of the process, we conclude that the performance variation between the meta-heuristics has a significant role in the effectiveness of the model. Therefore, we introduce statistical analyses to evaluate this factor within per-instance algorithm portfolios. [ABSTRACT FROM AUTHOR]