Zweistufen-Metaheuristik zur Lösung des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen unter Verwendung Lokaler Suche in zufallsgeste

ISBN-13: 9783640286133 / Niemiecki / Miękka / 2009 / 120 str.

Armin Bayer

Opis

Diplomarbeit aus dem Jahr 2008 im Fachbereich Mathematik - Angewandte Mathematik, Note: 1,0, Hochschule fur Technik, Wirtschaft und Kultur Leipzig, 59 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: In den letzten Jahrzehnten ruckte ein Bereich der kombinatorischen Optimierungsprobleme immer mehr in den Brennpunkt der Forschung: die Klasse der Tourenplanungsprobleme. Immer mehr Guter mussen in immer kurzerer Zeit von einem Ort zum anderen transportiert werden. Bei der Tourenplanung werden daher Fragestellungen diskutiert, wie eine Zusammenstellung von Auslieferungs- und Sammelauftragen aussehen muss, um einen moglichst effizienten Ablauf zu gewahrleisten. Die Schwierigkeit dieser Organisation liegt darin, die dem Problem zu Grunde liegenden Restriktionen einzuhalten. In der Praxis treten haufig Einschrankungen in Form einer begrenzten Ladekapazitat der zur Verfugung stehenden Fahrzeuge oder zeitlicher Vorgaben der Kunden auf. Diese zeitlichen Vorgaben beinhalten den fruhest beziehungsweise den spatest moglichen Belieferungszeitpunkt des Kunden. Beispielsweise kann ein Kunde aus der Just-in-Time Fertigung keine Lieferung vor diesem Zeitfenster annehmen, da ihm dafur schlicht Lagerkapazitaten fehlen. Eine Belieferung nach Ende des Zeitfensters ist ebenfalls nicht erlaubt, da es in diesem Szenario unter Umstanden zu einem Stillstand der Produktion in Folge fehlender Ressourcen kommen kann. In der Literatur wird dem Tourenplanungsproblem mit Zeitfensterrestriktionen meist eine hierarchische Zielstellung zu Grunde gelegt, einem primaren sowie einem sekundaren Ziel. Vorrangig ist hierbei die Minimierung der benotigten Fahrzeuge, nachrangig die Minimierung der zuruckgelegten Gesamtfahrstrecke. Seit Mitte der Siebziger Jahre werden zur Losung des VRPTW die dafur entwickelten Metaheuristiken eingesetzt. Sie basieren auf der Grundidee, physikalische oder biologische Prozesse nachzuahmen. Typische Vertreter solcher Verfahren sind Genetische und Evolutionare Algor