1 Search Results for "Kärkkäinen, Tommi"

Document
DOI: 10.4230/OASIcs.SCOR.2016.7
Feature Extractors for Describing Vehicle Routing Problem Instances

Authors: Jussi Rasku, Tommi Kärkkäinen, and Nysret Musliu

Published in: OASIcs, Volume 50, 5th Student Conference on Operational Research (SCOR 2016)

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.
Cite as

Jussi Rasku, Tommi Kärkkäinen, and Nysret Musliu. Feature Extractors for Describing Vehicle Routing Problem Instances. In 5th Student Conference on Operational Research (SCOR 2016). Open Access Series in Informatics (OASIcs), Volume 50, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{rasku_et_al:OASIcs.SCOR.2016.7,
  author =	{Rasku, Jussi and K\"{a}rkk\"{a}inen, Tommi and Musliu, Nysret},
  title =	{{Feature Extractors for Describing Vehicle Routing Problem Instances}},
  booktitle =	{5th Student Conference on Operational Research (SCOR 2016)},
  pages =	{7:1--7:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-004-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{50},
  editor =	{Hardy, Bradley and Qazi, Abroon and Ravizza, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2016.7},
  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}
}
  • Refine by Author
  • 1 Kärkkäinen, Tommi
  • 1 Musliu, Nysret
  • 1 Rasku, Jussi

  • Refine by Classification

  • Refine by Keyword
  • 1 Automatic Algorithm Configuration
  • 1 Feature extraction
  • 1 Metaheuristics
  • 1 Unsupervised learning
  • 1 Vehicle Routing Problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact