Detailansicht
Using problem instance feature extraction for automated metaheuristic selection and configuration to solve the vehicle routing problem
Matthias Weinwurm
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Betriebswirtschaft
Betreuer*in
Jan-Fabian Ehmke
DOI
10.25365/thesis.70283
URN
urn:nbn:at:at-ubw:1-11192.13733.135097-0
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Aufgrund der stetig zunehmenden Anzahl an immer komplexeren Metaheuristiken für das Lösen schwerer Optimierungsprobleme, die in der wissenschaftlichen Literatur präsentiert werden, wird die Auswahl einer Metaheuristik sowie das Setzen ihrer Parameter für eine gegebene Probleminstanz immer schwerer und zeitaufwändiger. Das Automated Algorithm Selection sowie Configuration Problem zielt darauf ab, die jeweiligen Aufgaben, zumeist mithilfe von Machine Learning Ansätzen, zu automatisieren. Während diese beiden Domänen in der Literatur jedoch als separat betrachtet werden, versucht diese Arbeit ein integriertes Modell zu erschaffen, das Komponenten und Konzepte der jeweiligen Domänen verwendet und diese zu einem Modell kombiniert, welches dann an einem Set von Vehicle Routing Problem (VRP) Instanzen getestet wird. Zuerst wird ein Feature Set, das VRP Instanzen beschreiben soll, aus mehreren Quellen konstruiert, wobei gezeigt wird, das Features für das Traveling Salesman Problem mit guter Vorhersagekraft für das VRP wiederverwendet werden können. Anschließend wird gezeigt, dass das vorgestellte Modell gegenüber Algorithm Selection oder Algoritm Configuartion Ansätzen, die entweder allein oder hintereinander ausgeführt werden, bessere Ergebnisse erzielt, was impliziert, dass die beiden Domänen tatsächlich miteinander verbunden sind. Des Weiteren wird gezeigt, dass diese Leistungssteigerungen innerhalb einer sehr kurzen Laufzeit realisiert werden können, was das Modell potenziell für eine Anwendung in der realen Welt eignet.
Abstract
(Englisch)
With a steadily rising number of increasingly complex metaheuristics for solving hard optimization problems being presented in the scientific literature, the choice of one metaheuristic and the setting of its parameters for a given problem instance becomes more and more difficult and time-consuming. The automated algorithm selection and configuration problems, respectively, aim to automate these tasks, often using machine learning approaches. While these two domains are treated separately in the literature, this thesis aims to create an integrated model by using components and concepts of the respective domains and combining them into one, while testing the model on a set of vehicle routing problem (VRP) instances. First, a feature set describing VRP instances is constructed using multiple sources and it is thereby shown, that features for the traveling salesman problem can be reused for the VRP with good predictive performance. It is then shown that the proposed model outperforms algorithm selection or algorithm configuration approaches, that are run individually or sequentially, which implies that the domains are in fact interconnected. Furthermore, it is shown that the performance gains can be realized within a very short runtime, which makes the model potentially applicable to real-world scenarios.
Schlagwörter
Schlagwörter
(Englisch)
algorithm selection problem algorithm configuration problem machine learning vehicle routing problem
Schlagwörter
(Deutsch)
Algorithm Selection Problem Algorithm Configuration Problem Maschinelles Lernen Vehicle Routing Problem
Autor*innen
Matthias Weinwurm
Haupttitel (Englisch)
Using problem instance feature extraction for automated metaheuristic selection and configuration to solve the vehicle routing problem
Paralleltitel (Deutsch)
Verwenden von Probleminstanz-Feature-Extraktion für die automatisierte Metaheuristik-Auswahl und Konfiguration zur Lösung des Vehicle Routing Problems
Publikationsjahr
2021
Umfangsangabe
74 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Jan-Fabian Ehmke
Klassifikationen
54 Informatik > 54.72 Künstliche Intelligenz ,
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC16468519
Utheses ID
60290
Studienkennzahl
UA | 066 | 915 | |