Online Publikationen der Hochschule Konstanz

Hinweis zum Urheberrecht

Master Thesis, Diplomarbeit zugänglich unter
URL: http://opus.bsz-bw.de/htwg/volltexte/2003/40/

---

Analyse und Verbesserung von iterierter lokaler Optimierung für das Kapazitive Vehicle-Routing-Problem mit Zeitfenstern

Müller, Kai

pdf-Format:		Dokument 1.pdf (1.147 KB)
SWD-Schlagwörter:		Transportplanung , Tourenplanung , SAP APO
Freie Schlagwörter (Deutsch):		Vehicle-Routing-Problem
Institut:		Informatik (IN)
DDC-Sachgruppe:		Informatik
Dokumentart:		Master Thesis, Diplomarbeit
Sprache:		Deutsch
Erstellungsjahr:		2003
Publikationsdatum:		11.08.2003
Kurzfassung in Deutsch:		Ein wichtiger Entscheidungsbereich im Supply Chain Management ist die Transportplanung, bei der es um eine kostenoptimale Zuordnung von Aufträgen zu Fahrzeugen und Routenplanung geht. Typischerweise sind hierbei zusätzliche Constraints einzuhalten, wie etwa Fahrzeugkapazitäten oder Öffnungszeiten (Zeitfenster) bei der Warenannahme. SAP’s Advanced Planner and Optimizer enthält einen Optimierer für Transportprobleme, der im wesentlichen auf iterierter lokaler Optimierung beruht und damit dem aktuellen Stand der Forschung im Bereich Routenplanung entspricht. Der bestehende Optimierer ist an realen Kundenszenarien orientiert, sollte aber auch auf Benchmarks aus der Literatur effizient und effektiv arbeiten. Ziel der Diplomarbeit ist es daher, den Optimierer auf seine Leistungsfähigkeit bei akademischen Vehicle-Routing-Problemen, die teilweise auch Kapazitäten und Zeitfenster beinhalten, hin zu untersuchen und Verbesserungspotential zu erkennen. Die im Internet verfügbaren klassischen Benchmarks gliedern sich in unterschiedliche Klassen (z.B. mit oder ohne Zeitfenster), die in ein allgemeineres Vehicle-Routing-Modell zu abstrahie-ren sind. Im Rahmen dieser Arbeit soll das Design und die Implementation dieses abstrakten Modells realisiert werden. Zur Evaluation des bestehenden Optimierers wird dann eine Transformation dieses Modells in das bereits vorhandene – und für reale Kundenprobleme ausgelegte – interne Optimierungsmodell benötigt. Die jeweiligen Schnittstellen sollen relational sein und auf der bereits für diesen Zweck realisierten relationalen Schicht basieren. Für den Optimierer stehen bereits Test-Tools zur Verfügung, die systematische Testläufe auf einer Menge von gegebenen Instanzen erlauben. Diese Test-Tools sind in eigene Analyseskripte zu integrieren, so dass umfassende empirische Untersuchungen des Optimierers weitgehend automatisiert durchgeführt werden können. Zur detaillierten Untersuchung konkreter Testläufe bietet sich weiterhin die Einbindung vorhandener Diagnose-Funktionalität an, um gezielt die in der lokalen Optimierung verwendeten Move-Operatoren zu untersuchen. Die durch systematische Testläufe gewonnenen Erkenntnisse und Ideen sollen dann prototypisch in den vorhandenen Optimierer integriert werden, wobei hier die speziellen Design- und Architekturgegebenheiten zu berücksichtigen sind.