Dynamische Tourenplanung

Diplomarbeit von Björn Aufderheide

Einleitung:

Tourenplanungsprobleme gehören zu den am häufigsten untersuchten Problemstellungen des Operations Research. Dennoch beschäftigt sich der weitaus größere Anteil der Arbeiten mit statischen Tourenplanungsproblemen. Sie unterliegen der stark vereinfachenden Annahme der Planungssicherheit durch unveränderliche Informationen im Zeitablauf. In Problemstellungen der realen Welt sind allerdings fast alle Parameter mit Unsicherheit behaftet und ändern sich im Zeitablauf. Die Berücksichtigung dieses Aspektes für eine möglichst realitätsnahe Planung findet in der dynamischen Tourenplanung statt.

Gerade in der heutigen Zeit, in der die wirtschaftliche, ökologische Nachhaltigkeit und die ‘Just in Time’ Produktion im Rahmen der Öffnung der Märkte und der Globalisierung immer mehr in den Blickpunkt geraten, ist es wesentlich die notwendigen logistischen Dienstleistungen so effizient wie möglich zu gestalten. Die gestiegenen Rechnerleistungen und die Entwicklung im Bereich der Kommunikations- und Informationstechnologie bietet immer neuere Möglichkeiten große Mengen an Echtzeitdaten effektiv zu verarbeiten und solche Systeme kostengünstig für Unternehmen, die logistische Aufgaben im Bereich der Tourenplanung zu bewältigen haben, bereitzustellen. Des Weiteren zeigen die praktischen Anwendungsgebiete durch ihre Vielfalt und Breite, dass ein großer Bedarf an intelligenten Lösungen durch eine dynamische Tourenplanung besteht.

Was in dem wachsenden Gebiet der dynamischen Tourenplanung Diskussionsgegenstand in der Literatur ist, wird in dieser Arbeit durch einen Überblick im Rahmen der Grundlagen der dynamischen Tourenplanung und der grundlegenden Unterscheidungsmöglichkeiten gegenüber einer statischen Tourenplanung aufgezeigt. Bevor der Aufbau und Gang dieser Arbeit im Folgenden detaillierter behandelt wird, sollen zunächst der Gegenstand und die Zielstellung dieser Arbeit mit den dahinter stehenden Fragestellungen erfolgen.

Problemstellung:

Die dynamischen Tourenplanungsprobleme wurden gerade in den letzten Jahren stärker erforscht. Diese Arbeit soll einen Literaturüberblick über diesen Themenbereich der Logistik geben. Dabei wird zunächst auf den Gegenstand dieser Arbeit eingegangen, um anschließend anhand der einzelnen Fragestellungen die Zielstellung dieser Arbeit aufzuzeigen.

Im Rahmen eines Literaturüberblickes sollen in dieser Arbeit die wesentlichen Bereiche der dynamischen Tourenplanung beleuchtet werden. Daher kann und soll eine sehr tiefe Durchdringung gewisser Sachverhalte nicht erfolgen. Die Literaturübersicht findet sukzessive über die Auseinandersetzung mit den wesentlichen unten erläuterten Fragestellungen in dem Themenbereich der dynamischen Tourenplanung statt. Dabei ermöglicht es der behandelte Themenbereich, die grundlegende Literatur dieses Bereiches anhand eines möglichst umfassenden Überblicks wiederzuspiegeln. Für eine detaillierte mathematische Modellbeschreibung dynamischer Planungsprobleme wird hier auf die einzelnen Literaturquellen verwiesen, da hier eine verbale Beschreibung der verschiedenen Problemstellungen näher liegt. Im Folgenden sollen nun die grundlegenden Fragestellungen dieser Arbeit genannt werden.

Im zweiten Kapitel steht daher die Frage nach der Einordnung in den Themenbereich und der Abgrenzung zu anderen Problemstellungen im Vordergrund. Deshalb wird in einem ersten Schritt geschaut, wo die dynamische Tourenplanung im Kontext der betriebswirtschaftlichen Logistik angesiedelt ist. Dann ist die Frage, wie die dynamische Tourenplanung aufgrund der grundlegenden Begrifflichkeiten und Definitionen von anderen Problemklassen der Tourenplanung genauer abgegrenzt werden kann. Danach ist es interessant, wie die einzelnen Problemstellungen innerhalb des Bereiches der dynamischen Tourenplanung aussehen, um das Problemfeld weiter abzugrenzen. Anschließend ist die Frage, wo die dynamische Tourenplanung in der Praxis angewendet wird.

Im dritten Kapitel steht die Dynamik in Tourenplanungsproblemen im Mittelpunkt. Die dabei gestellten Fragen sind, welche Eingangsinformationen sind in dynamische Planungssituationen mit Unsicherheit behaftet, also wo kommt die Dynamik her? Was hat die Dynamik für Auswirkungen auf die Komplexität von Tourenplanungsproblemen? Wie kann die Dynamik abgebildet oder gemessen werden? Abschließend ist die Frage wie der Dynamik dann entgegnet wird und welche gängigen Ansätze zur Lösung von dynamischen Tourenplanungsproblemen es gibt.

Im vierten Kapitel wird der Frage nachgegangen, was weitere grundlegende Unterscheidungsmerkmale nach Psaraftis zwischen statischen und dynamischen Tourenplanungsproblemen bezüglich der zeitlichen Dimension, der Informationen, entscheidungsrelevanter und weiterer in der Literatur gefundener Aspekte sind. Außerdem ist die Frage, wie bis jetzt in der Literatur darauf eingegangen wurde.

Abschließend wird im fünften Kapitel die Frage gestellt, was einerseits die technischen Vorraussetzungen einer dynamischen Tourenplanung sind und was eine dynamische Tourenplanung notwendig erscheinen lässt. In Bezug auf die gestellten Fragestellungen ergibt sich daher der folgende Aufbau und Gang dieser Arbeit.

Gang der Untersuchung:

In Kapitel 2 sollen die wesentlichen Grundlagen der dynamischen Tourenplanung für eine weitere Vertiefung und eine erste Einordnung in den Themenbereich geschaffen werden. Deshalb bietet sich in Kapitel 2.1 eine kurze Einordnung der Tourenplanung in das Aufgabengebiet der betriebswirtschaftlichen Logistik an, um anschließend in Kapitel 2.2 die grundlegenden Begriffe und Definitionen für eine bessere Abgrenzung der dynamischen Tourenplanung von anderen Problemklassen aufzuzeigen. Im darauf folgenden Kapitel 2.3 werden dann einzelne Problemstellungen der dynamischen Tourenplanung näher betrachtet, um das Problemfeld aufzuzeigen. Abschließend wird in Kapitel 2.4 der große Anwendungsbereich der dynamischen Tourenplanung dargestellt, um einen Überblick über den Einsatzbereich in der Praxis zu geben.

In Kapitel 3 wird die Dynamik in Tourenplanungsproblemen näher betrachtet. Dabei beschäftigt sich Kapitel 3.1 näher mit Eingangsinformationen, die in Anlehnung an die reale Welt mit Unsicherheit behaftet sind und daher in einer dynamischen Tourenplanung berücksichtigt werden sollten. Zwar ist die Berücksichtigung dynamischer Aspekte eine wichtige Erweiterung des klassischen Tourenplanungsproblems, aber die Auswirkungen auf die Komplexität der dynamischen Problemstellungen werden in Kapitel 3.2 behandelt. Anschließend wird in Kapitel 3.3 anhand einer bedeutenden Kennzahl zur Charakterisierung dynamischer Tourenplanungsprobleme der Grad der Dynamik (DOD) thematisiert. Abschließend werden in Kapitel 3.4 die besonderen Herausforderungen im Umgang mit der Dynamik erörtert und die gängigsten Ansätze zur Lösung von dynamischen Tourenplanungsproblemen angeführt.

In Kapitel 4 werden die grundlegenden Unterscheidungsmerkmale zwischen statischen und dynamischen Tourenplanungsproblemen im Einzelnen diskutiert. Einerseits nehmen die zeitlichen Aspekte gerade in der dynamischen Tourenplanung einen bedeutenden Stellenwert ein. In Kapitel 4.1 wird daher die zeitliche Dimension als ersten wesentlichen Unterschied zwischen statischen und dynamischen Tourenplanungsproblemen behandelt, während daneben auch der Planungshorizont unterschieden wird. Dazu zählen des Weiteren modifizierte Zeitfensterrestriktionen, soweit diese berücksichtigt werden. In Kapitel 4.2 werden die Eingangsinformationen näher beleuchtet. Das betrifft insbesondere die Unsicherheit von weiter in der Zukunft liegenden Informationen, und daraus resultierend eine größere Wichtigkeit von unmittelbaren Informationen. Auch die fortlaufende Aktualisierung der Informationsgrundlage in dynamischen Tourenplanungsproblemen fällt in dieses Kapitel. Anschließend werden in Kapitel 4.3 entscheidungsrelevante Aspekte in dynamischen Problemstellungen vertieft. Das umfasst die Revision bereits getroffener Entscheidungen oder das vorläufige Zurückstellen und Aufschieben von ungünstigen Kundenaufträgen, sowie die Integration der Warteschlangentheorie, falls ungünstige Kundenaufträge nicht außer Acht gelassen werden sollen. Und auch die Zielsetzungen in dynamischen Tourenplanungsproblemen werden hier betrachtet. Schließlich werden in Kapitel 4.4 unter sonstigen Aspekten dann die Flexibilität der Flottengröße und die Rechenzeiten vor weiteren in der Literatur gefundenen Anregungen für Unterschiede behandelt. Darunter fallen die Unterscheidung anhand von verwendeten Lösungsverfahren, die Unterschiede in der Art der Aufgabenstellung und die Einbeziehung von Kursänderungen.

In Kapitel 5 werden dann die Vorraussetzungen thematisiert, die eine dynamische Tourenplanung ermöglichen und eine effektiveren Gestaltung hilfreich sind. Um in einer globalisierten Welt, in der der Wettbewerbsdruck zunimmt, die effiziente Verteilung der produzierten Güter zu gewährleisten, muss gerade die Tourenplanung den dynamischen Problemstellungen entsprechen können. Welche technologischen Rahmenbedingungen durch Entwicklungen dafür geschaffen wurden, wird in Kapitel 5.1 dargestellt. Anschließend wird in Kapitel 5.2 noch einmal betont werden, wie notwendig eine dynamische Tourenplanung ist und was für ein Nutzen aus ihr entspringt.

Zum Ende der Arbeit werden in Kapitel 6 die Ergebnisse noch einmal in Bezug auf die im vorherigen Kapitel gestellten Fragen zusammengefasst. Das geschieht in Kapitel 6.1 durch ein ‘State of the Art’, während im Anschluss dann weitere Herausforderungen im Bereich der dynamischen Tourenplanung abschließend in Kapitel 6.2 genannt werden.

Inhaltsverzeichnis:

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.