License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SCOR.2016.7
URN: urn:nbn:de:0030-drops-65193
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6519/
Rasku, Jussi ;
Kärkkäinen, Tommi ;
Musliu, Nysret
Feature Extractors for Describing Vehicle Routing Problem Instances
Abstract
The vehicle routing problem comes in varied forms. In addition to usual variants with diverse constraints and specialized objectives, the problem instances themselves – even from a single shared source - can be distinctly different. Heuristic, metaheuristic, and hybrid algorithms that are typically used to solve these problems are sensitive to this variation and can exhibit erratic performance when applied on new, previously unseen instances. To mitigate this, and to improve their applicability, algorithm developers often choose to expose parameters that allow customization of the algorithm behavior. Unfortunately, finding a good set of values for these parameters can be a tedious task that requires extensive experimentation and experience. By deriving descriptors for the problem classes and instances, one would be able to apply learning and adaptive methods that, when taught, can effectively exploit the idiosyncrasies of a problem instance. Furthermore, these methods can generalize from previously learnt knowledge by inferring suitable values for these parameters. As a necessary intermediate step towards this goal, we propose a set of feature extractors for vehicle routing problems. The descriptors include dimensionality of the problem; statistical descriptors of distances, demands, etc.; clusterability of the vertex locations; and measures derived using fitness landscape analysis. We show the relevancy of these features by performing clustering on classical problem instances and instance-specific algorithm configuration of vehicle routing metaheuristics.
BibTeX - Entry
@InProceedings{rasku_et_al:OASIcs:2016:6519,
author = {Jussi Rasku and Tommi K{\"a}rkk{\"a}inen and Nysret Musliu},
title = {{Feature Extractors for Describing Vehicle Routing Problem Instances}},
booktitle = {5th Student Conference on Operational Research (SCOR 2016)},
pages = {7:1--7:13},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-004-0},
ISSN = {2190-6807},
year = {2016},
volume = {50},
editor = {Bradley Hardy and Abroon Qazi and Stefan Ravizza},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6519},
URN = {urn:nbn:de:0030-drops-65193},
doi = {10.4230/OASIcs.SCOR.2016.7},
annote = {Keywords: Metaheuristics, Vehicle Routing Problem, Feature extraction, Unsupervised learning, Automatic Algorithm Configuration}
}
|
Keywords: |
|
Metaheuristics, Vehicle Routing Problem, Feature extraction, Unsupervised learning, Automatic Algorithm Configuration |
|
Collection: |
|
5th Student Conference on Operational Research (SCOR 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
23.08.2016 |
