| Fachbereiche | |
|---|---|
| Buchreihen (99) |
1420
|
| Nachhaltigkeit |
3
|
| Gesundheitswesen |
3
|
| Geisteswissenschaften |
2425
|
| Naturwissenschaften |
5433
|
| Mathematik | 230 |
| Informatik | 321 |
| Physik | 982 |
| Chemie | 1371 |
| Geowissenschaften | 131 |
| Humanmedizin | 247 |
| Zahn-, Mund- und Kieferheilkunde | 10 |
| Veterinärmedizin | 112 |
| Pharmazie | 147 |
| Biologie | 838 |
| Biochemie, Molekularbiologie, Gentechnologie | 121 |
| Biophysik | 25 |
| Ernährungs- und Haushaltswissenschaften | 45 |
| Land- und Agrarwissenschaften | 1006 |
| Forstwissenschaften | 201 |
| Gartenbauwissenschaft | 20 |
| Umweltforschung, Ökologie und Landespflege | 149 |
| Ingenieurwissenschaften |
1827
|
| Allgemein |
97
|
|
Leitlinien Unfallchirurgie
5. Auflage bestellen |
|
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 |