What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. (June 2019)

• Record Type: Journal Article
• Authors: Arnold, Florian; Sörensen, Kenneth
• Is Part Of: Computers & operations research. Volume 106(2019)
• Page Start: 280
• Page End: 288
• Publication Date: 2019-06
• Subjects: Data mining -- Heuristics -- Vehicle routing problem -- Problem-specific knowledge; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.02.007
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A framework to derive problem-specific knowledge is introduced. The framework detects distinguishing features of good solutions for the Vehicle Routing Problem. Good solutions are characterized by narrow, compact routes with few intersections. A case study demonstrates that these findings can make a good heuristic even better. Abstract: 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.