Vergleich unterschiedlicher heuristischer Verfahren für das Vehicle routing problem with time windows

Diplomarbeit aus dem Jahr 2005 im Fachbereich BWL - Unternehmensforschung Operations Research Note: gut FernUniversität Hagen (Wirtschaftsinformatik) Sprache: Deutsch Abstract: Das Transportwesen und die damit verbundene logistische Planung des Warenflusses sowie die Tourenplanung spielen eine wichtige Rolle im betriebswirtschaftlichen Umfeld. Unter Tourenplanung versteht man allgemein eine Klasse von Planungsproblemen die verschiedene Ausprägungen bezüglich der Zielfunktion und den Nebenbedingungen aufweisen. Eine konkrete Problemstellung der Tourenplanung sieht etwa folgendermaßen aus: Von einem oder mehreren Lagern ausgehend sind mit einem vorhandenen Fuhrpark ein oder mehrere Kunden entsprechend den vorhandenen Aufträgen zu beliefern. Hierbei ist die Kapazität der Fahrzeuge beschränkt. Eine in der betrieblichen Praxis häufig auftretende weitere Restriktion ist die Vorgabe von Zeitfenstern. Unter Zeitfenstern versteht man Intervalle die den frühesten und spätesten Beginn einer Auftragsdurchführung begrenzen. Ein typisches Beispiel für ein Tourenplanungsproblem mit Zeitfenstern ist die „just-in-time Belieferung durch Paketdienste. Im angelsächsischen Sprachbereich wird das Problem auch als „vehicle routing problem with time windows (VRPTW) bezeichnet. In der Regel liegt dem VRPTW eine hierarchische Zielsetzung zugrunde die die benötigte Fahrzeugzahl in einem ersten Schritt und die Minimierung der Gesamtdistanz in einem zweiten Schritt berücksichtigt.Das VRPTW ist ein kombinatorisches Optimierungsproblem welches zur Klasse der NP-harten (engl.: non-deterministic polynomial time) Probleme gezählt wird. Dies bedeutet dass bislang kein Algorithmus bekannt ist mit dem eine optimale Lösung in polynomialer Zeit gefunden werden kann. Stattdessen wächst der Lösungsaufwand mit der Problemgröße exponentiell. Deshalb bietet sich der Einsatz von heuristischen Verfahren an.Hierzu zählen insbesondere Metaheuristiken wie das Tabu Search Verfahren Simulated An