Cuvillier Verlag

37 Jahre Kompetenz im wissenschaftlichen Publizieren
Internationaler Fachverlag für Wissenschaft und Wirtschaft

Cuvillier Verlag GmbH

De En Es
Online Vehicle Routing Set Partitioning Problems

Printausgabe
EUR 29,00 EUR 27,55

E-Book
EUR 0,00

Download
PDF (2,4 MB)

Online Vehicle Routing Set Partitioning Problems

Luis M. Torres (Autor)

Vorschau

Inhaltsverzeichnis, Datei (420 KB)
Leseprobe, Datei (760 KB)

Diese Arbeit befaßt sich mit zwei verschiedenen Aspekten der kombinatorischen
Optimierung: Online-Einsatzplanung von Fahrzeugen unter Echtzeit-Bedingungen
und Mengenpartitionierungsprobleme. In der Online-Fahrzeugeinsatzplanung geht
es darum, Routen zu berechnen, mit denen eine Flotte von Fahrzeugen eine gege-
bene Menge von Aufträgen optimal bedient. Das Wort “Online” weist auf die Tat-
sache hin, dass unmittelbare Entscheidungen auf Basis unvollständiger Information
getroffen werden müssen. Darüber hinaus fordern die Echtzeit-Bedingungen ga-
rantierte Antworten innerhalb kurzer Zeit. Das Mengenpartitionierungsproblem,
andererseits, ist ein grundlegendes Problem in der kombinatorischen Optimierung:
Gegeben ein Untermengensystem F ⊆ 2X einer Grundmenge X und eine Kos-
tenfunktion c : F → R+, finde ein Subsystem F ′ ⊆ F minimaler Kostensumme,
dessen Mengen eine Partition von X bilden.
Die Probleme der Online-Fahrzeugeinsatzplanung, die wir hier betrachten,
stammen aus einem Kooperationsprojektes des Konrad-Zuse Zentrums für In-
formationstechnik in Berlin mit dem Allgemeinen Deutschen Automobil-Club
(ADAC), in dem ein Online-Dispatching-Verfahren für die Disposition der Pan-
nenhilfefahrzeugen vom ADAC entwickelt wird. In dieser Arbeit wird die Aufstel-
lung eines solchen Einsatzplans als Online-Optimierungsproblem modelliert und
ein Lösungsalgorithmus dafür entworfen. Dieser verwendet einen Spaltengenerie-
rungsansatz, um einen kostengüstigen Dispositionsplan zu berechnen, der alle zu
einem bestimmten Zeitpunkt bekannten Aufträge mit den vorhandenen Hilfsfahr-
zeugen bedient. Mit denselben Methoden werden auch untere Schranken für die
Kosten eines optimalen Plans ermittelt. Wir berichten über praktische Erfahrung
mit dem Verfahren, das sich seit Herbst 2002 im Pilotbetrieb beim ADAC befindet.
Auf der anderen Seite untersuchen wir das Online-Problem aus theoretischer Sicht.
Für eine vereinfachte Problemstellung stellen wir einen kompetitiven Algorithmus
vor und beweisen untere Schranken.
Ein weiterer theoretischer Beitrag dieser Arbeit ist die Untersuchung von Men-
genpartitionierungsproblemen einer besonderen Form. Sie werden von unserem
Algorithmus für die Aufstellung eines Fahrzeugeinsatzplans als Unterprobleme ge-
löst. Ihre Besonderheit besteht darin, dass die Kardinalität jeder Menge im gegebe-
nen Mengensystem F von einer kleinen Konstante k begrenzt wird. Wir widmen
uns diesem Problem aus der Perspektive der Polyedertheorie. Für das verwandte
Mengenpackungsproblem erforschen wir, wie sich die Kardinalitätsbegrenzung der
Untermengen auf die Struktur der Facetten vom Packungspolytop auswirkt.
Schlüsselbegriffe: Fahrzeugeinsatzplanung, Spaltengenerierung, Online-Op-
timierung, polyedrische Kombinatorik, Mengenpartitionierung

ISBN-13 (Printausgabe) 3865371272
ISBN-13 (Printausgabe) 9783865371270
ISBN-13 (E-Book) 9783736911277
Buchendformat A5
Sprache Deutsch
Seitenanzahl 226
Auflage 1
Band 0
Erscheinungsort Göttingen
Promotionsort Göttingen
Erscheinungsdatum 28.07.2004
Allgemeine Einordnung Dissertation
Fachbereiche Mathematik
Schlagwörter Online-Fahrzeugroutenplanung, Fahrzeugeinsatzplanung in Echtzeit, Mengenpartitionierungsprobleme, Spaltengenerierung, Kombinatorische Optimierung, Polyedrische Kombinatorik, Ganzzahlige Programmierung, Kompetitive Analyse, Fahrzeugroutenplanung mit Zeitfenstern, Mengenpackungsprobleme