[Zurück]

D. Trummer:
"Applying ant colony optimization to the periodic vehicle routing problem with time windows.";
Betreuer/in(nen): G. Raidl; Computergraphik und Algorithmen, 2014.

Das Periodic Vehicle Routing Problem with Time Windows (PVRPTW) ist eine komplexe Erweiterung des klassischen Tourenplanungsproblems. Einerseits müssen hierbei die Kunden an mehreren Tagen innerhalb einer definierten Planungsperiode besucht werden, wobei die Auswahl der Kombination von Besuchstagen zum Problem gehört. Andererseits bestimmt jeder Kunde einen Zeitbereich, in welchem der Besuch stattfinden muss. Das Ziel ist die Minimierung der gesamten Tourenkosten bei Berücksichtigung aller Nebenbedingungen.
In dieser Diplomarbeit untersuchen wir die Anwendung verschiedener Varianten der Ant Colony Optimization (ACO) Metaheuristik, um dieses
NP-harte kombinatorische Optimierungsproblem zu lösen. Zu diesem Zweck wenden wir ACO auf zwei verschiedene Arten an: als heuristischen Lösungsalgorithmus für das Pricing Subproblem, welches bei einem Spaltengenerierungs-Ansatz zum Lösen des linearen Programmierungs-relaxierten PVRPTW auftritt; und als näherungsweisen Lösungsalgorithmus für das gesamte PVRPTW.

In der ersten Anwendung zeigen wir, wie durch Einsatz von ACO die Lösungszeit des Column Generation Prozesses verkürzt wird. Dazu wird ACO als Lösungsalgorithmus des Pricing Subproblems verwendet, welches wir als Elementary Shortest Path Problem with Resource
Constraints (ESPPRC) identifiziert haben. Die Untersuchungsergebnisse spiegeln wieder, dass die Anwendung von ACO die Lösungsleistung bezüglich Laufzeit und Qualität der generierten Spalten verglichen mit einem exakten Lösungsansatz steigert. Allerdings konnten wir kei-
nen Nachweis erbringen, dass ACO anderen Metaheuristiken hierbei vorzuziehen ist. Vielmehr schließen wir, dass andere algorithmische Komponenten, wie z.B. die lokale Suche, größeren Einfluss auf die Lösungsleistung besitzen, als die Wahl der Metaheuristik.

Für die zweite Anwendung stellen wir einen neuen ACO Algorithmus vor: cascaded ACO. Das PVRPTW wird in ein übergeordnetes "upper level" und ein untergeordnetes "lower level" Problem zerlegt, welche beide mit spezifischen ACO Varianten gelöst werden. ACO für das "upper level" Problem optimiert die Kombination von Besuchstagen, während ACO für das "lower level" Problem die sich ergebenden Vehicle Routing Problems with Time Windows (VRPTW) löst. Beide ACO Algorithmen wurden durch Einführung diverser Optimierungstechniken aus der Literatur angepasst. Zusätzlich wird eine Methode gezeigt, die es uns erlaubt hat, semi-optimale Einstellungen der zahlreichen Parameter der ACO Algorithmen zu finden.

Ein umfassender Vergleich unserer Resultate mit den Ergebnissen von bisher veröffentlichten PVRPTW Lösungsalgorithmen beschließt die Diskussion der Anwendung von ACO als Lösungsalgorithmus für das gesamte Problem. Obwohl kürzlich entwickelte hybride Algorithmen
zur Lösung des PVRPTW eine bessere Lösungsleistung bei großen Probleminstanzen zeigen,konnte cascaded ACO den einzigen anderen bisher publizierten ACO Lösungsalgorithmus für das PVRPTW übertreffen.

The Periodic Vehicle Routing Problem with Time Windows (PVRPTW) is an extended, complex variant of the classical vehicle routing problem. On the one hand it differs from the latter by visiting a subset of the customers several times during a planning horizon spanning several days, where the selection of a visit day combination out of a set of viable ones for each such customer is part of the problem. On the other hand the customers have associated a time window in which
the visit is allowed. The objective is to minimize the overall travel costs while respecting all constraints.

In this thesis we investigate the application of variants of the Ant Colony Optimization(ACO) metaheuristic to solve this highly constrained NP-hard problem in combination with other techniques. For this purpose we apply ACO in two different ways: as heuristic solver for the pricing subproblem arising in a column generation approach for the linear programming-relaxed PVRPTW; and as an approximate problem solving method for the whole PVRPTW.

In the first approach we show that ACO can be used to speed up the column generation process. To achieve this ACO is used to solve the Elementary Shortest Path Problem with Resource Constraints (ESPPRC) that forms our pricing subproblem. The investigation results reflect that the application of ACO improves performance and quality of columns compared to an exact ESPPRC solver, although other applied metaheuristics produce the same effect. In fact we deduce that other components of the column generation algorithm, e.g. local search, have more influence on the solving performance than the choice of the metaheuristic.

For the second approach we present a new ACO algorithm: the cascaded ACO. The PVRPTW is decomposed in an upper level and a lower level problem which are both solved with specific ACO variants. The ACO for the upper level problem has to optimize the visit combinations, whereas the lower level ACO solves a Vehicle Routing Problem with Time Windows (VRPTW). Both ACO algorithms are optimized by introducing and combining several techniques from literature to improve performance. Additionally a method is shown that allows
us to find semi-optimal settings for the various parameters of the ACO algorithms.

An extensive comparison of our results to results from previously published PVRPTW solution algorithms concludes the approach of using ACO as solver for the whole problem. Although, recently developed hybrid algorithms to solve the PVRPTW show better performance
on large problem instances, our cascaded ACO outperforms the sole other ACO algorithm published so far.

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