Die dynamischen Tourenplanungsprobleme wurden gerade in den letzten Jahren stärker erforscht. Dieses Buch gibt einen umfassenden Literaturüberblick zu diesem Themenbereich der Logistik, wobei die wesentlichen Bereiche der dynamischen Tourenplanung beleuchtet werden. Für eine detaillierte mathematische Modellbeschreibung dynamischer Planungsprobleme wird hier auf die einzelnen Literaturquellen verwiesen, da eine verbale Beschreibung der verschiedenen Problemstellungen für ein besseres Verständnis näher liegt. Zu diesem Zweck werden die Einordnung der dynamischen Tourenplanung in den Kontext der betriebswirtschaftlichen Logistik, die Abgrenzung zu anderen Problemklassen der Tourenplanung sowie Anwendungsbereiche in der Praxis erläutert. Zudem wird der Frage nach der Herkunft der Dynamik, den Auswirkungen von Dynamik, der Abbildung der Dynamik und der gängigen Ansätze zur Lösung von dynamischen Tourenplanungsproblemen nachgegangen. Anschließend werden weitere grundlegende Unterscheidungsmerkmale zwischen statischen und dynamischen Tourenplanungsproblemen bezüglich der zeitlichen Dimension, der Informationen, entscheidungsrelevanter und weiterer technischer Vorraussetzungen einer dynamischen Tourenplanung aufgezeigt. Dieses Buch richtet sich insbesondere an junge Studenten und alle Interessierten, die einen ersten Überblick zu diesem spannenden und interessanten Thema der Logistik gewinnen wollen darüber hinaus bietet es einen Anreiz zur vertiefenden Auseinandersetzung.

Textprobe: Kapitel 4.3.3, Integration der Warteschlangentheorie: Auch hier gibt es laut Psaraftis Unterschiede zwischen statischen und dynamischen Tourenplanungsproblemen. In der dynamischen Tourenplanung kann bei einem hohen Grad der Dynamik (siehe Kapitel 3.3) relativ schnell die Situation eintreten, dass neue Informationen bei Bekannt werden nicht mehr integriert werden können, weil das System überlastet ist. Während dieses im statischen Fall durch eine eventuelle Änderung der Fahrzeuganzahl nicht relevant ist, sind die Resultate im dynamischen Fall suboptimale Ergebnisse der Tourenplanungsverfahren oder übermäßige Verzögerungen. Wenn diese Informationen nicht außer Acht gelassen werden sollen, dann können sie mittels der Warteschlangentheorie dennoch integrieren werden. Das geschieht dann dadurch, dass eine Reihenfolge durch die Vergabe von Prioritäten festgelegt wird, nach der die wartenden Aufträge abgearbeitet werden, falls die Ankunftsrate neuer Informationen einen bestimmten Schwellenwert überschreitet. Natürlich besteht auch die Möglichkeit der Abweisung von Kunden, wenn sie geographisch schlecht gelegen sind, die Kosten einer Belieferung zu hoch wären oder unnötige Wartezeiten nicht in Kauf genommen werden sollen. Auch wenn die Tourenplanung und die Warteschlangentheorie zwei große spezielle Forschungsbereiche sind, ist es immer schwierig sie zu verbinden. Der Einsatz der Warteschlangentheorie oder die unbestimmte Zurückstellung von Aufträgen kann sich in stark frequentierten Systemen als sehr hilfreich erweisen, wenn die Nachfragerate einen gegebenen Schwellenwert überschreitet und die erwartete Wartezeit zur weiteren Einbeziehung dynamischer Kundenaufträge sehr stark ansteigt. In Problemstellungen mit Zeitfenstern sollte ein Fahrzeug am Ankunftsort warten, wenn es vor dem Zeitfenster dort eintrifft. In dynamischen Tourenplanungsproblemen ist es aber sinnvoller, wenn das Fahrzeug an dem zuletzt besuchten Kundenort so lange mit der Abfahrt wartet, bis es den Bestimmungsort zur unteren Zeitfenstergrenze erreichen kann (earliest departure policy). Oder das Fahrzeug wartet mit der Abfahrt noch länger, bis es den Bestimmungsort zur oberen Zeitfenstergrenze erreichen kann (latest departure policy). Durch diese einfachen Strategien können neue Kundenaufträge, die in der Zwischenzeit eingehen, eventuell noch berücksichtigt werden. Zum Beispiel beziehen Potvin, Xu, und Benyahia einfache Warte-Strategien bezüglich ob und wie lange das Fahrzeug warten soll im DVRPTW mit ein. Sie zeigen, dass durch Warten bis zu einem gewissen Grad Verbesserungen erzielt werden können, weil dadurch der größere Spielraum für Änderungen in der Tour besteht. In komplexeren Strategien können zusätzlich noch Wartezeiten an strategisch gut liegenden Standpunkten integriert werden. So haben Mitrovic-Minic und Laporte beispielsweise Warte-Strategien für das DPDPTW entwickelt. Dort untersuchen sie, ob durch Warte-Strategien der gesamte Umweg oder die Zahl der erforderlichen Fahrzeuge reduziert werden kann. Wenn das Fahrzeug immer an dem zuletzt besuchten Kundenort so lange mit der Abfahrt wartet, bis es den Bestimmungsort zur unteren Zeitfenstergrenze erreichen kann, dann kann der gesamte Umweg reduziert werden, aber mehr Fahrzeuge sind erforderlich, um die zusätzlichen Kunden zu bedienen. Wartet das Fahrzeug hingegen immer mit der Abfahrt, bis es den Bestimmungsort zur oberen Zeitfenstergrenze erreichen kann, dann kann die Gesamtzahl der Fahrzeuge auf Kosten von größeren Umwegen reduziert werden. Durch eine Kombination der beiden genannten Strategien werden allerdings sehr gute Ergebnisse in Bezug auf die Fahrzeuganzahl und die insgesamt zurückgelegte Strecke erzielt. Ein weiterer Ansatz ist die dynamische Einteilung der Tour in Segmente, die im näheren Umfeld des Fahrzeuges liegen. Dabei fährt das Fahrzeug, wenn es sich in einem Segment befindet, immer sofort zum nächsten Kunden. Müsste das Fahrzeug zur Bedienung des nächsten Kunden allerdings die Grenze dieses Segmentes überqueren, dann wartet es so lange es geht bei dem zuletzt bedienten Kunden. Ichoua, Gendreau und Potvin führen einen Ansatz mit guten Ergebnissen bei höher frequentierten Problemstellungen auf, den Ichoua in seiner Doktorarbeit thematisiert. Hier werden auch Wahrscheinlichkeiten mit in der Warte-Strategie berücksichtigt. Demnach muss ein Fahrzeug nach Beendigung der Bedienung eines Kunden an diesem Standort warten, wenn der nächste Kunde sehr weit entfernt liegt und die Wahrscheinlichkeit hoch genug ist, dass ein neuer Kundenauftrag in der Nähe des Fahrzeugstandortes eintreten könnte. Ist das der Fall, werden alle in der Nähe wartenden Fahrzeuge mit in die Planung eingebunden. Stellt die Bedienung des Kunden die kostengünstigste Alternative dar, dann wird sie ausgeführt. Andernfalls folgt das Fahrzeug seiner vorher bestimmten Tour. Auch Bent und Hentenryck benutzen eine Warte-Strategie, um die erzielten Lösungen zu verbessern. Dort wird die Abfahrt des Fahrzeuges bei einem bedienten Kundenstandort so lange verzögert, so lange es noch Probekunden zwischen dem aktuellen Kunden und dem nächsten bekannten Kunden in der geplanten Tour gibt. Branke et al. setzen sich mit weiteren Warte-Strategien in einem DVRP auseinander. Sie verfolgen dabei das Ziel die Wahrscheinlichkeit zu maximieren, neue dynamische Kundenaufträge in den bestimmten Tourenplan zu integrieren ohne Zeitrestriktionen zu verletzen. Das wird erreicht, indem die Fahrzeuge an günstig gelegenen Standorten innerhalb ihrer Tour warten, um das Erscheinen neuer Kunden möglichst optimal integrieren zu können. Dort werden zwar Problemstellungen ohne Zeitfenster betrachtet, dafür existiert allerdings eine zeitliche ‘Deadline’. In ihrer Arbeit wenden sie die Warte-Strategien auf die Problemstellung mit einem und mit zwei Fahrzeugen an. Bei der Betrachtung nur eines Fahrzeuges war die beste Strategie eine ‘no wait’-Strategie, also nicht zu warten, sondern immer gleich weiter zu fahren. Bei der Betrachtung zweier Fahrzeuge erwies sich der Start oder der wiederholte Start vom Depot als schlechteste Strategie. Als beste Strategie erwies sich eine ‘gemischte’ Strategie. Jedes Fahrzeug fährt ohne zu warten alle Kunden soweit ab, bis die Entfernung zum Depot der Schlupfzeit entspricht. Dann wird die verbleibende Wartezeit den restlichen Kunden im Verhältnis zu den verbleibenden Fahrentfernungen verteilt. Der Einsatz der Warteschlangentheorie oder die unbestimmte Zurückstellung von Aufträgen kann sich einerseits in stark frequentierten Systemen als sehr hilfreich erweisen. Auch unter anderen Gesichtspunkten stellen sich Warte Strategien als hilfreich heraus. So kann durch sie antizipativ zukünftigen Informationen begegnet werden. Dieses geschieht natürlich alles unter der Berücksichtigung der verfolgten Zielfunktionen (siehe Kapitel 4.3.4), die unterschiedlich in statischen oder dynamischen Problemstellungen ausfallen können. Nachdem in diesem Kapitel nun die Integration der Warteschlangentheorie unter gewissen Aspekten Berücksichtigung gefunden hat, werden im Folgenden Kapitel die Zielstellungen der Tourenplanung als weiteren unterscheidungsrelevanten Tatbestand näher betrachtet.

• Dynamische Tourenplanung

• Dynamic Vehicle Routing Problem

• VRP

• Real-time

• Literaturübersicht

• DVRP

• online

Björn Aufderheide wurde 1978 in Bremerhaven geboren. Sein Studium der Wirtschaftswissenschaft an der Universität Bremen schloss er im Jahre 2009 mit dem akademischen Grad Diplom Ökonom erfolgreich ab. Während des Studiums und seiner mehrjährigen studentischen Mitarbeit sammelte der Autor umfassende praktische Erfahrungen und Kenntnisse in der Logistik-Branche. So entwickelte er ein besonderes Interesse an dem stetig wachsenden Forschungsbereich der Tourenplanung, insbesondere der dynamischen Tourenplanung. Das Anliegen des Autors liegt darin, speziell jungen Studenten, aber auch allen Interessierten einen ersten umfassenden Überblick zu diesem spannenden und interessanten Thema der Logistik zu bieten sowie einen Anreiz zur vertiefenden Auseinandersetzung zu schaffen.