Selecting meta-heuristics for solving vehicle routing problems with time windows via meta-learning

• Published in: Expert systems with applications 2019-03, Vol.118, p.470-481
• Main Authors: Gutierrez-Rodríguez, Andres E., Conant-Pablos, Santiago E., Ortiz-Bayliss, José C., Terashima-Marín, Hugo
• Format: Article
• Language: English
• Subjects: Artificial intelligence; Classifiers; Expert systems; Heuristic; Heuristic methods; Meta-heuristic; Meta-learning; Multilayer perceptrons; Route planning; Routing; Solvers; Time windows; Traffic control; Vehicle routing; Vehicle routing problems; Windows (intervals)
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2018.10.036

•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. 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.