[Back]

B. Biesinger:
"Complete Solution Archives for Evolutionary Combinatorial Optimization";
Supervisor, Reviewer: G. Raidl, C. Blum, U. Pferschy; Institut für Computergraphik und Algorithmen, 2016; oral examination: 2016-06-03.

Hybrid metaheuristics for solving hard combinatorial optimization problems have been
intensively studied over the last few decades. This thesis considers such a hybridization of
metaheuristics and tree search methods to overcome some weaknesses of each individual
method. On the one hand, especially in evolutionary algorithms the lack of information
on the search history usually leads to unnecessary re-evaluations, a loss of diversity, and
premature convergence. On the other hand, tree search methods like branch-and-bound
frequently have a high run-time requirement and scale not so well with the instance
size. The focus of this thesis lies in the hybridization of these methods using complete
trie-based solution archives within a metaheuristic framework. Such a solution archive
stores all generated solution candidates in an efficient tree data structure and thereby
avoids duplicates. Whenever a potential duplicate solution is identified it is converted
into a guaranteed new, usually similar solution directly by the archive. Applying this
archive to a metaheuristic turns it, in principle, into a complete exact search algorithm
which finds an optimal solution given enough time. Although this is usually only
possible for smaller instances, even when prematurely terminated, using the archive
can improve the performance of the metaheuristic. In this thesis such solution archives
are investigated in detail, extended with more advanced techniques, and applied to two
practical combinatorial optimization problems with real-world applications.
The first considered problem is the competitive facility location problem, in which two
non-cooperating companies, a leader and a follower, compete for market share by choosing
locations for opening stores. We consider six different customer behavior scenarios and
demand models to compute the market share for the leader and the follower and present
mathematical models for each of them. We approach this problem heuristically with an
advanced evolutionary algorithm using a solution archive with a randomized trie structure.
The algorithm employs an embedded local and tabu search procedure which is combined
with the solution archive in four different ways. The substantial time consumption of the
solution evaluation is reduced by utilizing a multi-level evaluation scheme using a greedy
algorithm and a mixed integer programming formulation in a combined way. As this
problem comprises both, a compact solution representation by only storing the locations
for the leader and an expensive evaluation function consisting of computing optimal
locations for the follower, using a solution archive results in a substantial improvement
of the final solution quality.
The second problem is the generalized vehicle routing problem with stochastic demands
and preventive restocking which is a combination of two generalizations of the classical
ix
vehicle routing problem. The aim of this problem is to find routes through a set of
nodes, which are partitioned into disjoint clusters and exactly one node of each cluster
has to be visited. The capacity of the vehicle is limited, and therefore the (stochastic)
demands of the clusters cannot always be satisfied within a route and restocking trips
must be planned. Determining optimal restocking points depends on the realizations
of the random variables and the actual load of the vehicle, and can be computed using
an exact but time-consuming dynamic programming algorithm. For this problem an
exact solution algorithm and two metaheuristics are developed and presented in this
thesis. The exact algorithm is based on a mixed integer linear programming model for
the generalized traveling salesman problem and solved via branch-and-cut, which uses the
dynamic programming algorithm for computing the restocking points as sub-procedure
in order to separate cuts. In the first metaheuristic a general variable neighborhood
search with three neighborhood structures is used. For decreasing the run-time of the
solution evaluations a multi-level evaluation scheme is developed, which uses the dynamic
programming algorithm and iteratively approximates the actual solution quality with
increasing accuracy by scaling down the vehicle capacity and the probability distributions
of the cluster demands. The second metaheuristic is a genetic algorithm using a complete
trie-based solution archive. This archive is further extended with a bounding procedure
to cut off areas of the solution space that evidently cannot contain optimal solutions.
Computational results show that while the exact algorithm is only able to solve smaller
instances, both metaheuristics can be used well for larger instances. The solution archive
turned out to be, also for this problem, an important component of the genetic algorithm
and together with the bounding procedure the approach was able to find optimal or
near-optimal results for many benchmark instances.
The overall results of the computational tests of the developed algorithms for these
problems show that complete trie-based solution archives are able to significantly boost
the performance of evolutionary algorithms for combinatorial optimization problems with
a compact solution representation and a time-consuming evaluation function. When
properly designed, extensions to the solution archive exploiting their tree structure
can lead to significant improvements of the metaheuristic. This thesis shows that the
combination of evolutionary algorithms with solution archives can lead to new state-ofthe-
art algorithms in the area of location and routing problems.

Hybride Metaheuristiken wurden in den letzten Jahrzehnten intensiv erforscht um schwierige
kombinatorische Optimierungsprobleme zu lösen. In dieser Dissertation werden
solche Hybridisierungen von Metaheuristiken mit auf Tree-Search basierenden Methoden
untersucht, um Schwächen beider einzelnen Verfahren auszugleichen. Auf der einen Seite
kommt es, insbesondere bei evolutionären Algorithmen, auf Grund der fehlenden Information
zum bisherigen Suchverlauf oft zu unnötigen Re-evaluierungen, einem Verlust
der Diversität und vorzeitiger Konvergenz. Auf der anderen Seite haben Tree-Search
Methoden wie Branch-and-Bound häufig eine hohe Laufzeit und skalieren schlecht mit der
Instanzgröße. Der Fokus dieser Arbeit liegt in der Hybridisierung dieser Methoden durch
vollständige Trie-basierte Lösungsarchive innerhalb metaheuristischer Frameworks. Ein
solches Lösungsarchiv speichert alle generierten Lösungskandidaten in einer effizienten
baumbasierten Datenstruktur und vermeidet dadurch Duplikate. Bei jedem Auftreten einer
Duplikatlösung wird diese in eine garantiert neue, üblicherweise ähnliche Lösung direkt
vom Archiv konvertiert. Wendet man dieses Lösungsarchiv innerhalb einer Metaheuristik
an, wird diese dadurch im Prinzip zu einem vollständigen, exakten Suchalgorithmus, der
eine optimale Lösung bei genügend langer Laufzeit garantiert findet. Obwohl dieser Fall
normalerweise nur bei kleineren Instanzen auftritt, kann das Archiv die Performance der
Metaheuristik verbessern, selbst wenn der Algorithmus vorzeitig abgebrochen wird. In dieser
Dissertation werden solche Lösungsarchive detailliert untersucht, mit fortgeschrittenen
Verfahren erweitert und auf zwei praxisrelevante Problemstellungen angewandt.
Die erste betrachtete Problemstellung ist das Competitive Facility Location Problem, in
dem zwei nicht kooperative Unternehmen, ein Leader und ein Follower, durch Auswählen
von Filialstandorten um Marktanteile konkurrieren. Wir betrachten sechs verschiedene
Szenarien für das Kundenverhalten und die Art des Bedarfs um die Marktanteile für
den Leader und den Follower zu berechnen und präsentieren mathematische Modelle
für jedes dieser Szenarien. Wir stellen einen heuristischen Ansatz vor, der auf einem
fortgeschrittenen evolutionärem Algorithmus und einem Lösungsarchiv mit randomisierter
Baumstruktur basiert. Der Algorithmus nutzt eine eingebettete lokale Suche und
Tabusuche, die mit dem Lösungsarchiv auf vier verschiedene Arten kombiniert werden.
Die hohe Laufzeit der Lösungsevaluierung wird durch ein multi-level Evaluierungsschema
reduziert, welches einen Greedy-Algorithmus und ein Mixed Integer Linear Programming
Modell kombiniert einsetzt. Da dieses Problem sowohl eine kompakte Lösungsrepräsentierung
besitzt, da nur die Standorte des Leaders gespeichert werden, als auch eine
teure Evaluierungsfunktion hat, die aus dem Finden optimaler Standorte für den Folvii
lower besteht, konnte mit dem Lösungsarchiv eine substantielle Verbesserung der finalen
Lösungsgüte erreicht werden.
Die zweite Problemstellung ist das Generalized Vehicle Routing Problem with Stochastic
Demands and Preventive Restocking, welches eine Kombination aus zwei Generalisierungen
des klassischen Routenplanungsproblems ist. Ziel dieses Problems ist, Routen
durch eine Menge von Standorten (Knoten) zu finden, die in disjunkte Cluster eingeteilt
sind, wobei genau ein Knoten von jedem Cluster zu besuchen ist. Da die Kapazität eines
Fahrzeugs beschränkt ist und daher der (stochastische) Bedarf der Cluster nicht immer
erfüllt werden kann, müssen zusätzliche Wege zum Auffüllen des Fahrzeugs geplant werden.
Um die optimalen Positionen für so ein Auffüllen in der Tour zu finden, die von der
Realisierung der Zufallsvariablen und der derzeitigen Ladung abhängt, kann ein exakter
aber zeitaufwändiger Algorithmus basierend auf dynamischer Programmierung eingesetzt
werden. Für dieses Problem werden ein exakter und zwei metaheuristische Lösungsansätze
entwickelt und in dieser Arbeit präsentiert. Der exakte Algorithmus basiert auf einem
Mixed Integer Linear Programming Modell für das generalisierte Traveling Salesman
Problem, welches via Branch-and-Cut gelöst wird und die dynamische Programmierung
für das Finden optimaler Auffüllpositionen benutzt. Die erste Metaheuristik ist eine
General Variable Neighborhood Search mit drei Nachbarschaftsstrukturen. Um die Laufzeit
der Lösungsevaluierungen zu reduzieren, wird ein Multi-level Evaluierungsschema
verwendet, welches die dynamische Programmierung benutzt und iterativ mit immer
größerer Genauigkeit die exakte Lösungsqualität approximiert. In diesem Evaluierungsschema
wird die Kapazität des Fahrzeugs und die Wahrscheinlichkeitsverteilungen des
Bedarfs in den Clustern herab skaliert. Die zweite Metaheuristik ist ein genetischer
Algorithmus, der ein vollständiges Trie-basiertes Lösungsarchiv benutzt. Das Archiv
wird mit einer Bounding Erweiterung versehen, die Teile des Suchbereichs wegschneidet,
welche garantiert keine optimale Lösung beinhalten. Empirische Resultate zeigen, dass
der exakte Algorithmus nur kleinere Instanzen lösen kann, aber beide Metaheuristiken
gut für größere Instanzen eingesetzt werden können. Das Lösungsarchiv stellte sich auch
für dieses Problem als wichtiger Teil des genetischen Algorithmus heraus und gemeinsam
mit der Bounding Erweiterung war es möglich, optimale oder nahezu optimale Lösungen
für viele Benchmark Instanzen zu finden.
Die Resultate der entwickelten Algorithmen für die vorgestellten Probleme zeigen
insgesamt, dass vollständige Trie-basierte Lösungsarchive in der Lage sind, die Performance
von evolutionären Algorithmen für kombinatorische Optimierungsprobleme mit
einer kompakten Lösungsrepräsentierung und zeitaufwändiger Evaluierungsfunktion signifikant
zu steigern. Erweiterungen für Lösungsarchive, die deren Baumstruktur ausnutzen,
können zu substantiellen Verbesserungen der Metaheuristik führen. Diese Dissertation
zeigt, dass die Kombination aus evolutionären Algorithmen und Lösungsarchiven zu
neuen state-of-the-art Lösungsverfahren in dem Gebiet der Standort- und Routenplanung
führen können.