[Back]


Doctor's Theses (authored and supervised):

S. Pirkwieser:
"Hybrid Metaheuristics and Matheuristics for Problems in Bioinformatics and Transportation";
Supervisor, Reviewer: G. Raidl, K. Dörner; Institut für Computergraphik und Algorithmen, 2012; oral examination: 2012-06-14.



English abstract:
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.
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).
Although we did not decide on the problems which would be tackled right from the start-
as I was more interested in the methodical aspect-it eventually turned out that we dealt
with problems that are not only interesting from an academic perspective but highly relevant
in practical application areas, too. The first is the consensus tree problem which primarily
arises in phylogenetics and thus belongs to the domain of bioinformatics. Its objective is to
build a single solution tree out of several phylogenetic trees given as input, somehow best
representing the whole available information. All remaining problems arise in the field of
transportation and are extensions of the capacitated vehicle routing problem (CVRP) motivated
by important real-world aspects. These variants are in fact generalizations, as the
CVRP can be considered a special case of each one. Following ones are considered: the periodic
vehicle routing problem and the periodic vehicle routing problem with time windows,
where customers usually need to be visited multiple times in a given planning horizon, also
respecting (hard) customer time windows in case of the latter; the location-routing problem
as well as the periodic location-routing problem, which add to the CVRP the task of simultaneously
placing some facilities at given locations (i.e. corresponding to the NP-hard facility
location problem); and finally the vehicle routing problem with compartments, considering
not a single loading area and product but several compartments and products, possibly involving
certain incompatibilities.
Several forms of hybridization are investigated in this work: collaboratively exchanging solutions,
tight integration of the concepts of a method in another one, multilevel refinement, the
guidance of a method by information gathered by another one, heuristic column generation
as well as heuristic cut separation, very large neighborhood search based on integer linear
programming and a more sophisticated variant of it also realizing an optimal merging by exploiting
the information of several solutions, and finally solving subproblems to optimality.
v
We show that for all considered 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.
In addition, the role of the individual methods or the single underlying method is not to be
underestimated. In our case variants of variable neighborhood search (VNS) are the most
prominent metaheuristics applied, and for all but one problem a solution approach based
on VNS is presented for the first time. The simple elegance of VNS offers a great flexibility
when it comes to extension as well as specialization, as neighborhood structures can be
added like building blocks in order to eventually assemble a powerful solution method. Especially
meaningful problem-tailored neighborhood structures, which vary on the level/part
of the problem they operate, contribute a lot to the overall success. Combined with appropriate
embedded local search components, and in some cases to also accept worse solutions
with a certain probability as well as to allow infeasible solutions, we always achieve a good
balance of exploration and intensification.
In thorough comparisons to previous solution approaches we almost always achieve at least
competitive results. In many cases they are even clearly better, hence obtaining currently
leading approaches. This is also documented by numerous new best known solutions obtained.
However, the improvement is not only in solution quality, but often our methods
also exhibit much better runtime behaviors and thus scalability to larger instances. As a consequence
of this, already competitive results can often be obtained with considerably less
runtime. Since the means to compare to other approaches are after all quite limited, we
are all the more concerned with comparing our "baseline methods" to the subsequently enhanced
hybrid methods whenever meaningful. Overall, it turns out that our hybrid methods
almost always show statistically significant better results, in some cases for whole instance
sets; with nearly none or at most a moderate increase in runtime.
Note that each of these hybrid variants has its strengths and weaknesses, which are addressed
in this work. Not surprisingly, none clearly dominates all others and is the preferred variant
for each possible problem - also for hybrid methods there is "no free lunch". Nevertheless,
our work provides additional guidelines concerning under which conditions which
hybridization schemes can be promising. For one thing, 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 is recommendable for problems exhibiting a similar structure.
Despite all their potential benefits, hybrid methods generally also have some drawbacks
which one should be aware of: they have a higher complexity, they require more effort
for design and implementation, to combine algorithms/concepts from different streams an
appropriate knowledge of each individual stream is a prerequisite, and they are likely to be
harder to tune. However, if one copes with these issues such hybridizations might give rise
to promising solution approaches for many problems.

German 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 Vorund
Nachteile der Methoden zu erlangen, um sie generell auch sinnvoll auf andere Probleme
anzuwenden.
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. Obwohl wir die zu behandelnden Probleme nicht
von Anfang an festgelegt haben - da ich auch eher am methodischen Aspekt interessiert war
- stellte sich schließlich heraus, dass diese nicht nur von einem akademischen Standpunkt
aus interessant sind, sondern auch hinsichtlich praktischer Anwendungsbereiche eine hohe
Relevanz besitzen. Das erste ist das Konsensus-Baum Problem (Consensus Tree Problem),
welches hauptsächlich in der Phylogenetik auftritt und daher dem Bereich der Bioinformatik
angehört. Das Ziel ist einen einzelnen Lösungsbaum anhand von mehreren gegebenen phylogenetischen
Bäumen derart zu erstellen, sodass dieser die gesamte Information bestmöglich
repräsentiert. Die restlichen Probleme entstammen dem Transportbereich und stellen allesamt
Erweiterungen des kapazitierten Tourenplanungsproblems (Capacitated Vehicle Routing
Problem (CVRP)) dar, die durch wichtige reale Aspekte motiviert sind. Genaugenommen
handelt es sich bei diesen Varianten um Generalisierungen des CVRP, da dieses jeweils
als Spezialfall angesehen werden kann. Folgende werden betrachtet: das periodische Tourenplanungsproblem
(Periodic Vehicle Routing Problem) und das periodische Tourenplanungsproblem
mit Zeitfenster (Periodic Vehicle Routing Problem with Time Windows), bei denen
Kunden üblicherweise mehrmals innerhalb eines Planungszeitraums besucht werden müssen,
wobei bei zweiterem auch (strikte) kundenseitige Zeitfenster zu berücksichtigen sind;
das Standort-Tourenplanungsproblem (Location-Routing Problem) als auch das periodische
Standort-Tourenplanungsproblem (Periodic Location-Routing Problem), welche das CVRP
um die Aufgabe erweitern gleichzeitig bestimmte Einrichtungen an gewissen Standorten zu
platzieren, welches dem NP-schweren Standortplanungsproblem (Facility Location Provii
blem) entspricht; und schlussendlich das Tourenplanungsproblem mit Ladeabteilen (Vehicle
Routing Problem with Compartments), bei dem nicht nur eine Ladefläche und ein Produkt
sondern mehrere Ladeabteile sowie Produkte berücksichtigt werden, wobei bestimmte Inkompatibilitäten
auftreten können.
Verschiedene Arten der Hybridisierung werden in dieser Arbeit betrachtet: kollaboratives
Austauschen von Lösungen, enge Integration von Konzepten einer Methode in eine andere,
Multilevel Refinement, das Lenken einer Methode anhand von Informationen gewonnen
durch eine andere, heuristische Spaltengenerierung als auch heuristisches Separieren
von Schnittebenen, sehr große Nachbarschaftssuche basierend auf ganzzahliger linearer Programmierung
und eine komplexere Variante davon die zusätzlich ein optimales Kombinieren
realisiert, welches die Information von mehreren Lösungen ausnutzt, und zuletzt das optimale
Lösen von Subproblemen.
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. 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.
Des Weiteren darf auch die Rolle der individuellen Verfahren oder des alleinigen zugrundeliegenden
Verfahrens nicht unterschätzt werden. In unserem Fall stellen Varianten der Variablen
Nachbarschaftssuche (VNS) die meist verwendeten Metaheuristiken dar, und für alle
außer einem Problem wird zum ersten mal ein auf VNS basierender Lösungsansatz vorgestellt.
Die schlichte Eleganz der VNS bietet ein hohes Maß an Flexibilität hinsichtlich
Erweiterung und Spezialisierung, da Nachbarschaftsstrukturen wie Bausteine hinzugefügt
werden können um letzten Endes ein leistungsfähiges Lösungsverfahren zusammenzustellen.
Insbesondere sinnvolle, auf das Problem zugeschnittene Nachbarschaftsstrukturen, die
auf unterschiedlichen Leveln/Teilen des Problems operieren, tragen maßgeblich zum Gesamterfolg
bei. Kombiniert mit geeigneten eingebetteten Komponenten zur lokalen Suche,
und zum Teil der Akzeptanz von schlechteren Lösungen mit einer gewissenWahrscheinlichkeit
sowie dem Erlauben von ungültigen Lösungen, erreichen wir immer eine gute Balance
zwischen Exploration und Intensivierung.
In gründlichen Vergleichen zu vorherigen Lösungsansätzen erzielen wir fast immer zumindest
gleichwertige Ergebnisse. In vielen Fällen sind diese sogar deutlich besser, womit wir
mit derzeit führenden Ansätzen aufwarten können. Dies wird auch durch zahlreich gefundene
neue beste Lösungen dokumentiert. Allerdings spiegelt sich die Verbesserung nicht nur in
der Lösungsqualität wider, sondern unsere Methoden zeigen oftmals auch ein viel besseres
Laufzeitverhalten und damit auch Skalierbarkeit gegenüber größeren Instanzen. Infolgedessen
können oftmals gleichwertige Ergebnisse bereits mit wesentlich weniger Laufzeit erzielt
werden. Da die Mittel sich mit anderen Ansätzen zu vergleichen doch recht begrenzt sind,
sind wir umso mehr damit befasst, wann immer sinnvoll, einen Vergleich unserer "Basismethoden"
mit den in weiterer Folge verbesserten hybriden Methoden anzustellen. Insgesamt stellt sich heraus, dass unsere Hybridverfahren fast immer statistisch signifikant bessere Lösungen
aufweisen, teilweise für gesamte Instanz-Sets; mit fast keinem oder allenfalls moderatem
Anstieg der Laufzeit.
Es ist zu beachten, dass jede dieser Hybrid-Varianten ihre Stärken und Schwächen hat, welche
in dieser Arbeit behandelt werden. Wenig überraschend dominiert keine alle anderen
und ist die bevorzugte Variante für alle möglichen Probleme - auch für Hybridverfahren gibt
es nichts umsonst ("no free lunch"). Dennoch bietet unsere Arbeit zusätzliche Richtlinien
unter welchen Bedingungen welche Hybridisierungsschemata vielversprechend sein können.
Zum Beispiel erscheinen die erarbeiteten Matheuristiken 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 empfiehlt sich für Probleme die eine
ähnliche Struktur aufweisen.
Trotz aller möglichen Vorteile haben hybride Verfahren in der Regel auch einige Nachteile,
derer man sich bewusst sein sollte: sie besitzen eine höhere Komplexität, sie erfordern mehr
Design- als auch Implementierungsaufwand, um Algorithmen/Konzepte aus unterschiedlichen
Richtungen zu kombinieren ist ein entsprechendes Wissen jeder einzelnen Richtung
eine Voraussetzung, und sie sind sehr wahrscheinlich schwieriger einzustellen bzw. zu parametrisieren.
Wenn man jedoch mit diesen Problemen zurechtkommt, dann können derartige
Hybridisierungen zu vielversprechenden Lösungsansätzen für viele Probleme führen.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_212521.pdf


Created from the Publication Database of the Vienna University of Technology.