EconPapers    
Economics at your fingertips  
 

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 Applied 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)
New Economics Papers: this item is included in nep-cmp
Date: 2017-01
References: Add references at CitEc
Citations Track citations by RSS feed

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 Applied Economics Contact information at EDIRC.
Series data maintained by Joeri Nys ().

 
Page updated 2018-01-20
Handle: RePEc:ant:wpaper:2017003