A hybrid evolutionary algorithm for the vehicle routing problem with stochastic demands

Abstract

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, alleLösungskandidatenineinerTrie-Datenstrukturzuspeichern.SobaldeineneueLö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 polynomialtimesolutionalgorithm. Therefore,ageneticalgorithmusingthepermutation 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, -rst 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 signi-cantly improve its results.