Complete solution archives for evolutionary combinatorial optimization : application to a competitive location and a stochastic vehicle routing problem

Abstract

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 Tabu\-suche, 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 Follower besteht, konnte mit dem Lösungsarchiv eine substantielle Verbesserung der finalen Lösungsgüte erreicht werden. Die zweite Problemstellung ist das Generalized Vehicle 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.

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 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-of-the-art algorithms in the area of location and routing problems.