What makes a solution good? The generation of problem-specific knowledge for heuristics

Florian Arnold and Kenneth Sörensen

Working Papers from University of Antwerp, Faculty of Business and Economics

Abstract: 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)
Pages: 25 pages
Date: 2017-01
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://repository.uantwerpen.be/docman/irua/7ad34f/140763.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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 Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().