Back to Search
Start Over
Selecting meta-heuristics for solving vehicle routing problems with time windows via meta-learning.
- Source :
-
Expert Systems with Applications . Mar2019, Vol. 118, p470-481. 12p. - Publication Year :
- 2019
-
Abstract
- 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]
- Subjects :
- *METAHEURISTIC algorithms
*MULTILAYER perceptrons
*LEARNING
*GREEDY algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 09574174
- Volume :
- 118
- Database :
- Academic Search Index
- Journal :
- Expert Systems with Applications
- Publication Type :
- Academic Journal
- Accession number :
- 132805016
- Full Text :
- https://doi.org/10.1016/j.eswa.2018.10.036