Hybrid metaheuristics and matheuristics for problems in bioinformatics and transportation

Abstract

Das allgemeine Ziel dieser Dissertation bestand in der gründlichen Untersuchung unterschiedlicher hybrider Optimierungsstrategien für bestimmte Klassen NP-schwieriger kombinatorischer Optimierungsprobleme. Dazu sollten grundlegende Konzepte verfeinert und weiterentwickelt werden. Zweierlei Endziele wurden dabei verfolgt: mit sehr effektiven, neuen state-of-the-art Methoden zur Lösung der gewählten Benchmarkprobleme aufwarten zu können, als auch weitere Erfahrungen und Wissen hinsichtlich der spezifischen Vor- und Nachteile der Methoden zu erlangen, um sie generell auch sinnvoll auf andere Probleme anzuwenden.<br />Grundsätzlich versuchen derartige Hybride die Stärken von zwei oder mehr Verfahren, aus möglicherweise verschiedenen Richtungen, auf unterschiedliche Art und Weise zu kombinieren. Weiters war es beabsichtigt den Fokus gezielt auf die Kombination von exakten und (meta-)heuristischen Algorithmen zu legen, um speziell die Stärke von Methoden der mathematischen Programmierung auszunutzen, was in sogenannten Matheuristiken (oder modellbasierten Metaheuristiken) resultiert.<br />Die behandelten Probleme sind nicht nur von einem akademischen Standpunkt aus interessant, sondern besitzen auch hinsichtlich praktischer Anwendungsbereiche eine hohe Relevanz. Eines davon kommt aus dem Bereich der Bioinformatik, während die restlichen Probleme dem Transportbereich entstammen und allesamt Erweiterungen des kapazitierten Tourenplanungsproblems (Capacitated Vehicle Routing Problem) darstellen, die durch wichtige reale Aspekte motiviert sind.<br />Wir zeigen, dass eine geschickte Hybridisierung der entwickelten exakten und heuristischen Verfahren, oder unterschiedlicher Heuristiken, für alle behandelten Probleme im Allgemeinen zu einer signifikanten Verbesserung führt. Tatsächlich verleihen die exakten Erweiterungen für Heuristiken und umgekehrt, welche eine integrative Kombination darstellen, in so gut wie all unseren Fällen der Haupt- bzw.<br />Host-Methode einen beträchtlichen Performancegewinn. Dabei können entweder heuristische Komponenten erheblich die Laufzeit reduzieren oder exakte Komponenten signifikant die Lösungsgüte erhöhen. Zudem profitieren kollaborative Kombinationen deutlich von den unterschiedlichen Algorithmen in Verwendung.<br />Unsere meist verwendete zugrundeliegende Metaheuristik ist die Variable Nachbarschaftssuche, welche ein hohes Maß an Flexibilität hinsichtlich Erweiterung und Spezialisierung bietet. Insbesondere sinnvolle, auf das Problem zugeschnittene Nachbarschaftsstrukturen, die auf unterschiedlichen Leveln/Teilen des Problems operieren, tragen maßgeblich zum Gesamterfolg bei.<br />Im Nachhinein können wir tatsächlich bestätigen, dass Hybridverfahren, wenn sie entsprechend konzipiert, umgesetzt und schließlich angewendet werden, sehr leistungsfähig sein können und man damit sogar führende Lösungsansätze erhalten kann; etwas, das wir für die meisten der betrachteten Probleme erzielten.<br />Die erarbeiteten Matheuristiken erscheinen nicht nur speziell für andere, möglicherweise umfangreichere Varianten von Tourenplanungsproblemen vielversprechend, sondern ihr Konzept lässt sich auch relativ leicht auf andere Klassen von kombinatorischen Optimierungsproblemen anwenden. Vor allem die verwendete Kombination von sehr großer Nachbarschaftssuche und dem optimalen Kombinieren von mehreren Lösungen empfiehlt sich für Probleme die eine ähnliche Struktur aufweisen.<br />

The general aim of this doctoral thesis was to thoroughly investigate diverse hybrid optimization strategies for certain classes of NP-hard combinatorial optimization problems. For this basic concepts should be refined and further developed. The ultimate goals were twofold: to come up with highly effective, new state-of-the-art methods for solving the selected benchmark problems, and to gain further experience and knowledge of the specific pros and cons in order to apply the methods more generally in meaningful ways also to other problems.<br />In general, such hybrids try to combine in various ways the strengths of two or more methods from possibly different streams. It was further intended to focus in particular on combining exact and (meta-)heuristic algorithms, especially exploiting the power of mathematical programming techniques, yielding so-called matheuristics (or model-based metaheuristics).<br />The problems we deal with are not only interesting from an academic perspective but highly relevant in practical application areas, too. One of them is from the bioinformatics domain, whereas all others arise in the field of transportation and are extensions of the capacitated vehicle routing problem motivated by important real-world aspects.<br />We show that for all these problems a skillfull hybridization of the developed exact and heuristic methods, or of several heuristics, leads to a significant improvement in general. In fact, the exact add-ons for heuristics and vice versa, representing an integrative combination, give in our cases almost always a considerable performance boost to the main (or host) method. Thereby either heuristic components are able to notably reduce the required runtime or exact components can significantly increase the solution quality. Moreover, the collaborative combinations clearly benefit from the diverse algorithms in use.<br />Our most prominent underlying metaheuristic is variable neighborhood search, which offers a great flexibility when it comes to extension as well as specialization. In particular meaningful problem-tailored neighborhood structures, which vary on the level/part of the problem they operate, contribute a lot to the overall success.<br />In retrospect, we can actually confirm that hybrid methods, if appropriately conceived, implemented, and eventually applied, can be very powerful and one might even obtain leading solution approaches; something we achieved for most of the problems we considered.<br />Our devised matheuristics not only seem promising in particular for other, possibly even richer variants of routing problems, but their concept can fairly easily be applied to other classes of combinatorial optimization problems as well. Especially the applied combination of very large neighborhood search and optimal merging of several solutions is recommendable for problems exhibiting a similar structure.<br />