Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 106, Issue -, Pages 280-288Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2018.02.007
Keywords
Data mining; Heuristics; Vehicle routing problem; Problem-specific knowledge
Ask authors/readers for more resources
Heuristics are the weapon of choice when it comes to solving complex combinatorial optimization problems. Even though a large amount of research focuses on tuning heuristics on a specific problem, little research has been done to investigate structural characteristics of the problem itself. We argue that knowledge about the structural characteristics that distinguish good from not-so-good solutions of a combinatorial optimization problem, can be instrumental in designing efficient heuristics. We develop a data-mining based approach that can generate such knowledge and apply it to the vehicle routing problem. We define several metrics to characterize both a VRP solution and a VRP instance, and generate and classify 192.000 solutions for various instances. With these metrics we are able to distinguish between optimal and non-optimal solutions with an accuracy of up to 90%. We discuss the most distinguishing characteristics of good VRP solutions, and show how the knowledge thus generated can be used to improve the performance of an existing heuristic. (C) 2018 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available