Detailansicht
Genetic algorithms to solve multi-objective optimization problems
adopting NSGA-II to a periodic vehicle routing problem
Hans-Christian Zohmann
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Betreuer*in
Walter Gutjahr
DOI
10.25365/thesis.16419
URN
urn:nbn:at:at-ubw:1-29945.37048.493366-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Ziel dieser Masterarbeit ist die Evaluierung der Anwendbarkeit eines Genetischen Algorithmus auf ein periodisches Vehicle Routing Problem (PVRP). Bei dem zu evaluierenden Algorithmus handelt es sich um den sogenannten "Non-Dominated Sorting Algorithm Version II"(NSGA-II). Der angesprochene Algorithmus gehört zur Gruppe der Genetischen Algorithmen und zeichnet sich durch die gleichzeitige Optimierung mehrerer Zielfunktionen aus. Im Zuge der vorliegenden Arbeit wird der NSGA-II auf ein periodisches Vehicle Routing Problem angewandt. Einführend wird der betriebswirtschaftliche Hintergrund des PVRP angedeutet und das PVRP wird von ähnlichen Optimierungsproblemen abgegrenzt. Daraufhin wird die Funktionsweise von genetischen Algorithmen im Allgemeinen und von Mehrzieloptimierungsproblemen im Speziellen vorgestellt. Anschließend wird der Ansatz zur Lösung eines PVRP basierend auf dem NSGA-II diskutiert. Das Hauptmerkmal ist die Teilung des Problems in ein Haupt- und in ein Subproblem, wobei das Hauptproblem von der Lösung des Subproblems abhängt. Der NSGA-II ist verantwortlich für die Lösung des Hauptproblems welches sich mit der Generierung eines periodischen Belieferungsschemas beschäftigt. Das Subproblem entspricht dem Problem des Handlungsreisenden (TSP) und wird in einem Fall als Integer Linear Program (ILP) mit Hilfe von CPLEX und in einem zweiten Fall durch eine modifizierte Variante der Nearest-Neighbor-Heuristik gelöst. In weiterer Folge wird eine Übersicht über die PVRP Implementierung gegeben. Danach werden der Aufbau der Testumgebung und der Entwurf der Testreihen erläutert. Abschließend werden die Ergebnisse der Testläufe ausgewertet und das Verhalten der beiden PVRP Implementierungen basierend auf den unterschiedlichen Subproblem-Lösungsansätzen wird diskutiert.
Abstract
(Englisch)
The aim of the paper is to evaluate the applicability of a multi-objective genetic algorithm to a Periodic Vehicle Routing Problems (PVRP). In the beginning of the paper the theoretical background of the areas involved will be outlined. The PVRP will be explained from a business administrative point of view, followed by a positioning of the PVRP in the area of optimization
problems. In the following section, firstly, genetic algorithms in general and then multi-objective genetic algorithms will be discussed. A further discussion of the NSGA-II in detail will be followed by the presentation of approach how the genetic algorithm can be adopted to a PVRP. The main characteristic of this approach is the division of the problem into a master problem and a sub-problem. The NSGA-II will be responsible for solving the
master problem which refers to providing a periodic delivery schema. The sub-problem refers to solving a Travelling Salesman Problem (TSP). The sub-problem will be solved as an Integer Linear Program (ILP) with the help of CPLEX in one case and with a Next-Neighbor heuristic enhanced by a two-opt move in the later case. After introducing the NSGA-II there will be given an overview about the structure of the actual PVRP implementation
and the interdependencies to CPLEX. Then the setting up of the test environment and how the test runs are designed will be presented. In the final sections the results from the various test runs will be discussed showing the performance of the two different PVRP implementations.
Schlagwörter
Schlagwörter
(Englisch)
Periodic Vehicle Routing Problem NSGA-II Genetic Algorithm Multi-Objective Optimization Evolutionary Algorithm Vendor Managed Inventory
Schlagwörter
(Deutsch)
Periodisches Vehicle Routing Problem NSGA-II Genetischer Algorithmus Mehrzieloptimierung Evolutionärer Algorithmus Vendor Managed Inventory
Autor*innen
Hans-Christian Zohmann
Haupttitel (Englisch)
Genetic algorithms to solve multi-objective optimization problems
Hauptuntertitel (Englisch)
adopting NSGA-II to a periodic vehicle routing problem
Paralleltitel (Deutsch)
Genetischer Algorithmus zur Lösung von Optimierungsproblemen mit mehreren Zielfunktionen ; Anwendung des NSGA-II auf ein periodisches Vehicle Routing Problem
Publikationsjahr
2011
Umfangsangabe
60 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Walter Gutjahr
AC Nummer
AC08808018
Utheses ID
14724
Studienkennzahl
UA | 066 | 926 | |