Detailansicht

Heuristic solution approaches for the covering tour problem

Patrick Kubik

Art der Arbeit

Diplomarbeit

Universität

Universität Wien

Fakultät

Fakultät für Wirtschaftswissenschaften

Betreuer*in

Karl Dörner

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.334

URN

urn:nbn:at:at-ubw:1-29428.58896.250762-6

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Diese Arbeit beschäftigt sich mit dem Covering Tour Problem (CTP) und verschiedenen heuristischen Lösungsmethoden. Dieses Problem der Tourenplanung zählt zu den kombinatorischen Optimierungsproblemen, welche sehr oft im Bereich der Distributionslogistik international agierender Großunternehmen auftreten und durch deren Lösung man entsprechend Kosten einsparen und Gewinne maximieren kann. Im Zuge der Globalisierung der Weltwirtschaft rückt das Problem der Distributionskosten immer mehr in den Mittelpunkt. Das CTP kann auf einem ungerichteten Graphen G=(V U W, E)definiert werden. V U W ist eine Menge von Knoten. V sind jene Knoten, die von der zu konstruierenden Tour besucht werden können. T ist eine Teilmenge von V und beinhaltet jene Knoten, die von der Tour besucht werden müssen. W ist die Menge jener Knoten, welche von der Tour abgedeckt werden müssen, also in einer vorgegebenen Entfernung zur Tour liegen müssen. Das Kantenset E beinhaltet die Verbindungen zwischen sämtlichen Knoten. Ziel ist es nun, eine möglichst kurze Tour zu finden, die im Punkt v0 beginnt, alle Knoten aus T besucht, sämtliche Knoten aus W abdeckt und wieder in v0 endet. Um das Problem zu lösen, wurde das CTP gemäß einer bereits angewandten Methode in zwei Subprobleme, nämlich das Traveling Salesman Problem (TSP) und das Set Covering Problem (SCP) unterteilt und diese wurden vorgestellt. Nach einer kurzen Einführung der Ant Colony Optimierung wurden die Algorithmen GENI, GENIUS und GENI Ant Colony System für den TSP Teil und PRIMAL1 sowie ein Set Covering Ant Colony System für den SCP Teil detailliert beschrieben. In weitere Folge wurde erklärt, wie man die Algorithmen kombinieren kann, um das CTP zu lösen. Sämtliche Algorithmen wurden mit Hilfe der Programmiersprache C++ simuliert und getestet. Zunächst wurden die Algorithmen an Instanzen einer Datenbank getestet und mit bereits vorhandenen Lösungen verglichen, um ihre Funktionalität und Konkurrenzfähigkeit zu überprüfen. Da für das CTP keine Vergleichsinstanzen vorhanden sind, wurden stochastische Probleme entworfen und mit dem H-1-CTP Algorithmus und der von mir entworfenen Metaheuristik Covering Tour Ant Colony System bestehend aus GENI Ant Colony System und Set Covering Ant Colony System gelöst und die Ergebnisse verglichen, um dann die beiden Lösungsansätze zu bewerten.

Abstract

(Englisch)

This thesis deals with the Covering Tour Problem (CTP) and different heuristic solution approaches. It can be classified as a combinatorial optimization problem. Logistics and distribution departments of economic global players have to handle this sort of problems to reduce costs and maximize profit. Distribution costs enjoy increasing importance due to the globalization of world economy. The CTP is defined on a complete undirected graph G=(V U W, E) with a set of vertices V U W where V is a set of vertices that can be visited, W defines the set of vertices that have to be covered by the tour and E is the set of edges. “Covered by the tour” means that any vertex v has to lie within a predefined distance of a vertex on the tour. The set V includes the subset T which holds the vertices that have to be visited by the tour. The solution to the CTP is a minimum length tour. The tour starts and ends at the depot and is defined by a certain subset so that all vertices that have to be visited are visited by the tour and all vertices that have to be covered lie within a predetermined distance of a vertex belonging to the tour. In order to solve the problem, it was classified as a combination of the Traveling Salesman Problem (TSP) and the Set Covering Problem (SCP) and the components were introduced. After a short description of Ant Colony Optimization, algorithms GENI, GENIUS and GENI Ant Colony System for the TSP part and PRIMAL1 as well as Set Covering Ant Colony System for the SCP part were introduced in detail. Then the combinations of these algorithms for solving the CTP were described. All algorithms were simulated and tested with the help of C++ programming language. First, algorithms were tested individually on instances from data libraries to ensure their functionality and competitiveness. Then stochastic instances were developed for the CTP because no comparable benchmarks exist and the H-1-CTP algorithm as well as the Covering Tour Ant Colony System, that I created myself, were run on these instances and results were compared.

Autor*innen

Patrick Kubik

Haupttitel (Englisch)

Heuristic solution approaches for the covering tour problem

Paralleltitel (Deutsch)

Heuristische Lösungsansätze für das Covering Tour Problem

Publikationsjahr

2007

Umfangsangabe

86 S.

Sprache

Englisch

Beurteiler*in

Karl Dörner

Klassifikation

85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges

AC Nummer

AC06536932

Utheses ID

239

Studienkennzahl

UA | 157 | | |

Detailansicht

Abstracts

Schlagwörter