What makes a solution good? The generation of problem-specific knowledge for heuristics
Florian Arnold and
Working Papers from University of Antwerp, Faculty of Applied Economics
Heuristics are the weapon of choice when it comes to solving complex combinatorial optimization problems. Even though some research focuses on tuning a heuristic with respect to a certain problem, little research has been done to investigate structural characteristics of the problem itself. In this paper we argue that knowledge about a problem is highly valuable when it comes to designing effi cient heuristics, and we show how it can be generated. With knowledge we hereby mean that we can defi?ne desirable structural characteristics of good solutions. Our knowledge generation approach is based on data mining and we demonstrate its concept with the help of the most prominent combinatorial problem in Operations Research, the Vehicle Routing Problem. We de?fine metrics to measure a solution and an 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 93%. Furthermore, we reveal the most distinguishing characteristics of good VRP solutions, and use them to improve an existing heuristic.
Keywords: Multi-depot vehicle routing problem; Multi-product; Inventory management; Inventory allocation; Metaheuristics (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations Track citations by RSS feed
Downloads: (external link)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:ant:wpaper:2017003
Access Statistics for this paper
More papers in Working Papers from University of Antwerp, Faculty of Applied Economics Contact information at EDIRC.
Series data maintained by Joeri Nys ().