Title (eng)
Using problem instance feature extraction for automated metaheuristic selection and configuration to solve the vehicle routing problem
Parallel title (deu)
Verwenden von Probleminstanz-Feature-Extraktion für die automatisierte Metaheuristik-Auswahl und Konfiguration zur Lösung des Vehicle Routing Problems
Author
Matthias Weinwurm
Advisor
Jan-Fabian Ehmke
Assessor
Jan-Fabian Ehmke
Abstract (deu)
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 (eng)
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.
Keywords (eng)
algorithm selection problemalgorithm configuration problemmachine learningvehicle routing problem
Keywords (deu)
Algorithm Selection ProblemAlgorithm Configuration ProblemMaschinelles LernenVehicle Routing Problem
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1398638
rdau:P60550 (deu)
74 Seiten : Illustrationen
Number of pages
74
Association (deu)
Title (eng)
Using problem instance feature extraction for automated metaheuristic selection and configuration to solve the vehicle routing problem
Parallel title (deu)
Verwenden von Probleminstanz-Feature-Extraktion für die automatisierte Metaheuristik-Auswahl und Konfiguration zur Lösung des Vehicle Routing Problems
Author
Matthias Weinwurm
Abstract (deu)
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 (eng)
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.
Keywords (eng)
algorithm selection problemalgorithm configuration problemmachine learningvehicle routing problem
Keywords (deu)
Algorithm Selection ProblemAlgorithm Configuration ProblemMaschinelles LernenVehicle Routing Problem
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1398639
Number of pages
74
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0