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

Diplomarbeit aus dem Jahr 2008 im Fachbereich Mathematik - Angewandte Mathematik Note: 10 Hochschule für Technik Wirtschaft und Kultur Leipzig Sprache: Deutsch Abstract: In den letzten Jahrzehnten rückte ein Bereich der kombinatorischen Optimierungsprobleme immer mehr in den Brennpunkt der Forschung:die Klasse der Tourenplanungsprobleme. Immer mehr Güter müssen in immer kürzerer Zeit von einem Ort zum anderen transportiert werden. Bei der Tourenplanung werden daher Fragestellungen diskutiert wie eine Zusammenstellung von Auslieferungs- und Sammelaufträgen aussehen muss um einen möglichst effizienten Ablauf zu gewährleisten. Die Schwierigkeit dieser Organisation liegt darin die dem Problem zu Grunde liegenden Restriktionen einzuhalten. In der Praxis treten häufig Einschränkungen in Form einer begrenzten Ladekapazität der zur Verfügung stehenden Fahrzeuge oder zeitlicher Vorgaben der Kunden auf. Diese zeitlichen Vorgaben beinhalten den frühest beziehungsweise den spätest möglichen Belieferungszeitpunkt des Kunden. Beispielsweise kann ein Kunde aus der Just-in-Time Fertigung keine Lieferung vor diesem Zeitfenster annehmen da ihm dafür schlicht Lagerkapazitäten fehlen. Eine Belieferung nach Ende des Zeitfensters ist ebenfalls nicht erlaubt da es in diesem Szenario unter Umständen 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 primären sowie einem sekundären Ziel. Vorrangig ist hierbei die Minimierung der benötigten Fahrzeuge nachrangig die Minimierung der zurückgelegten Gesamtfahrstrecke. Seit Mitte der Siebziger Jahre werden zur Lösung des VRPTW die dafür entwickelten Metaheuristiken eingesetzt. Sie basieren auf der Grundidee physikalische oder biologische Prozesse nachzuahmen. Typische Vertreter solcher Verfahren sind Genetische und Evolutionäre Algorithmen Simulated Annealing und T