[Zurück]

S. Pourmanouchehri:
"A Hybrid Evolutionary Algorithm for the Vehicle Routing Problem with Stochastic Demands";
Betreuer/in(nen): G. Raidl; Institut für Computergraphik und Algorithmen, 2016; Abschlussprüfung: 01.09.2016.

Diese Arbeit behandelt eine stochastische Erweiterung des klassischen Routenplanungsproblem,
die den Kundenbedarf als Zufallsvariablen betrachtet. Der Schwerpunkt wird
auf die Entwicklung eines hybriden evolutionären Algorithmus zur Lösung dieses sogennanten
Vehicle Routing Problems mit stochastischem Bedarf (VRPSD) gelegt. Bei
solchen Routenplanungsproblemen verlassen die Fahrzeuge das Depot mit voller Fracht,
um Kunden zu bedienen, deren exakte Nachfrage jedoch zur Startzeit unbekannt ist
und erst bei Ankunft genau feststeht. Das VRPSD ist ein NP-schweres kombinatorisches
Optimierungsproblem. Dies bedeutet, dass es unter der Annahme von P6=NP keine Lösung
in Polynomialzeit für dieses Problem gibt. Aus diesem Grund wurde ein genetischer
Algorithmus entwickelt, der auf der Permutation von Knotenpunkten als Lösungskandidaten
beruht, so dass eine möglichst gute Lösung in einem akzeptablen Zeitrahmen
gefunden werden kann. Die Evaluierung einer solchen Permutation, die jene Positionen
bestimmt, an denen das Fahrzeug wieder befüllt werden muss, beruht auf dynamischer
Programmierung. In einem nächsten Schritt wurde eine 2-opt lokale Suche implementiert,
um die Suche zu intensivieren. Um die Suche zu beschleunigen, wurde ein Multi-level
Evaluierungsschma auf den genetischen Algorithmus angewandt. Mit dieser Methode
wurde der Zielfunktionswert eines Lösungskandidaten wiederholt und mit zunehmender
Genauigkeit approximiert bis er verworfen oder exakt evaluiert werden konnte. Um ein
wiederholtes Evaluieren bereits bekannter Lösungskandidaten zu vermeiden, wurde außerdem
ein vollständiges Trie-basiertes Lösungsarchiv implementiert, das Duplikatlösungen
in garantiert neue und meist ähnliche Lösungen konvertiert, was diesen Lösungsalgorithmus
im Prinzip zu einem exakten Verfahren macht. Die grundsätzliche Idee besteht darin,
alle Lösungskandidaten in einer Trie-Datenstruktur zu speichern. Sobald eine neue Lösung
generiert wird, wird diese mit dem Lösungsarchiv abgeglichen, um zu garantieren, dass
es sich um eine neue Lösung handelt. Sollte die Lösung schon vorhanden sein, produziert
das Archiv automatisch eine neue Lösung, die die Duplikatlösung ersetzt statt dieselbe
Lösung ein zweites Mal zu betrachten. Die Resultate auf einer Menge von Benchmark
Instanzen zeigen, dass das Multi-level Evaluierungsschema die für die Lösungevaluierung
benötigte Zeit drastisch reduzieren kann. Die Nutzung des Lösungsarchivs führt hingegen
nur in manchen Fällen zu besseren Ergebnissen. Verglichen mit bisher in der Literatur
angewandten Algorithmen kann der in dieser Arbeit vorgeschlagene Ansatz daher zu
deutlich verbesserten Lösungen des VRPSD beitragen.

This work considers a stochastic extension to the classical vehicle routing problem by
assuming that the customers´ demand are random variables. The focus lies on the
development of a hybrid evolutionary algorithm for solving the so-called vehicle routing
problem with stochastic demands and preventive restocking (VRPSD). In the VRPSD
vehicles leave from a depot with full load, and have to serve a set of customers whose
exact demand is only known upon arrival. The VRPSD is an NP-hard combinatorial
optimization problem which means that under the assumption that P6=NP there exists no
polynomial time solution algorithm. Therefore, a genetic algorithm using the permutation
of nodes as solution representation is developed so that an acceptably good solution can
be found in reasonable time. The evaluation of such a permutation, which determines
the restocking points depending on the current load of the vehicle, is performed by a
dynamic programming algorithm. In the next step, to intensify the search, a 2-opt local
search based is implemented. Additionally, a multi-level evaluation scheme is applied
to the genetic algorithm to speed up the solution evaluations. Using this scheme, the
objective value of a solution candidate will be repeatedly approximated with increasing
accuracy until it can be discarded or it is evaluated exactly. On top of that, a complete
trie-based solution archive is implemented in order to prevent revisiting known solutions
and converting them into guaranteed new and usually similar solutions. This makes the
overall solution method, in principle, to an exact algorithm. The idea behind is to save
all candidate solutions in a trie data structure. Each time a new solution generated, first
it is looked up in the solution archive to check whether this solution is already generated
or not. In case of revisiting an old solution, a guaranteed new solution candidate will be
produced directly by the archive which replaces the duplicate. Computational results
on a set of benchmark instances show that the multi-level evaluation scheme is able to
drastically reduce the time spent in solution evaluations and that applying the solution
archive leads to an improvement only in some instances. Compared to an algorithm of
the literature the proposed approach can significantly improve its results.

http://publik.tuwien.ac.at/files/publik_254592.pdf