I
n diesem Artikel soll gezeigt werden, wie sich verschiedene Restriktionen auf die Planung von Rundtouren auswirken. Sind keine zusätzlichen Restriktionen vorhanden, hat man als Mensch ein gutes Gefühl dafür, wie eine „gute“ Tour aussieht. Gut heißt in diesem Fall eine möglichst geringe Gesamtlänge oder Fahrtzeit. Im einfachsten Fall möchte man also nur die kürzeste Rundtour finden und, wie der Name schon suggeriert, erwartet man ein kreisförmiges Bild, wenn man diese Tour auf einer Karte zeichnet. Wenn auch nicht unbedingt optimal, kann man so doch auch von Hand gute Touren ermitteln. In der Praxis tritt dieser einfache Fall jedoch selten auf. Häufig gibt es verschiedene Nebenbedingungen, die für eine gültige Tourenplanung erfüllt sein müssen. Diese Restriktionen können dazu führen, dass Rundtouren plötzlich alles andere als rund aussehen. Es könnte sogar passieren, dass die beste Planung auf einer Landkarte ein Zick-Zack-Muster bildet.
Es ist in der Praxis nicht immer möglich, Kunden zu jedem beliebigen Zeitpunkt zu besuchen. Hier kommen Zeitfenster ins Spiel. Sie beschreiben einen Zeitraum, in dem ein Kunde erreicht werden kann. Kennt man eine besonders kurze Rundtour ohne Zeitfenster, z.B. bezüglich der Gesamtfahrzeit, so kann diese komplett den Zeitfenstern widersprechen. Im schlimmsten Fall ist jeder zweite Kunde auf der Rundtour nur nachmittags erreichbar und die restlichen nur vormittags. Jetzt wäre die geplante Tour sogar ungültig. Denn um sie einzuhalten, müsste der Fahrer vor dem ersten Kunden, der nur nachmittags besucht werden kann, warten. Danach wäre aber das Zeitfenster des nächsten Kunden bereits abgelaufen. Er kann also nicht mehr besucht werden. Abbildung 1 zeigt dieses Phänomen und wie eine optimale Tour mit Zeitfenstern aussehen würde.
ZEITFENSTER
Es ist in der Praxis nicht immer möglich, Kunden zu jedem beliebigen Zeitpunkt zu besuchen. Hier kommen Zeitfenster ins Spiel. Sie beschreiben einen Zeitraum, in dem ein Kunde erreicht werden kann. Kennt man eine besonders kurze Rundtour ohne Zeitfenster, z.B. bezüglich der Gesamtfahrzeit, so kann diese komplett den Zeitfenstern widersprechen. Im schlimmsten Fall ist jeder zweite Kunde auf der Rundtour nur nachmittags erreichbar und die restlichen nur vormittags. Jetzt wäre die geplante Tour sogar ungültig. Denn um sie einzuhalten, müsste der Fahrer vor dem ersten Kunden, der nur nachmittags besucht werden kann, warten. Danach wäre aber das Zeitfenster des nächsten Kunden bereits abgelaufen. Er kann also nicht mehr besucht werden. Abbildung 1 zeigt dieses Phänomen und wie eine optimale Tour mit Zeitfenstern aussehen würde.
Abbildung 1: Unterschied zwischen einer optimalen Tour ohne (oben) und mit (unten) Zeitfenstern
Dass die Tour direkt ungültig wird, ist ein Extremfall. Aber es können dennoch hohe Wartezeiten entstehen, so dass es sinnvoller ist, zunächst einen anderen Kunden zu besuchen. Betrachtet man jetzt nur die Fahrstrecke, scheinen Zeitfenster kein Problem zu sein, da warten keine zusätzliche zurückgelegte Strecke bedeutet. Das Problem einer ungültigen Tour bleibt jedoch bestehen und führt auch hier zu anderen Touren.
BESUCHSABHÄNGIGKEITEN
In manchen Fällen ist es notwendig einen Ort A vor dem Ort B zu besuchen. Dies ist z.B. für einen Kurierdienst der Fall. Ein Paket muss zunächst an einem Ort abgeholt werden, bevor es woanders ausgeliefert werden kann. Gleiches gilt für den Transport von Personen. Man spricht hierbei auch von Pickup and Delivery Problemen oder im konkreten Fall des Personentransportes von Dial-A-Ride Problemen. Wenn man nun wieder das Beispiel aus Abbildung 1 betrachtet, aber andere Restriktionen hinzufügt, ergibt sich eine ähnliche Situation. Gehören die ersten Orte zu Auslieferungen, wäre die Tour wieder ungültig. Dieses Problem könnte einfach behoben werden, indem die Tour andersherum gefahren wird. Schwieriger ist der Fall, in dem eine Mischung aus Abholung und Auslieferungen vorliegt. Abbildung 2 zeigt ein solches Beispiel.
Abbildung 2: Unterschied zwischen einer Tour ohne (oben) und mit (unten) Besuchsabhängigkeiten. Im rechten Bild sind Orte, die zu einer Abholung gehören, mit einem P markiert und Orte, die zu einer Auslieferung gehören, mit D. Der Index gibt an, welche Orte zusammengehören.
Selbst der Fall, dass die ersten drei Orte Abholungen und die letzten drei Auslieferungen sind, ist nicht zwangsläufig einfach. Häufig geht mit dieser Art von Restriktionen auch eine Kapazitätsbeschränkung einher. Es könnte sein, dass es gar nicht möglich ist, alle drei Lieferungen auf einmal einzuladen und in diesem Fall ändert sich die Tour wieder. Insbesondere wenn Abholung und Auslieferung weit auseinanderliegen, können lange Umwege unvermeidlich sein.
WEITERE RESTRIKTIONEN
Die oben genannten Restriktionen sind gute Beispiele dafür, warum optimale Touren auf einer Landkarte nicht zwangsläufig „gut“ aussehen. Es gibt jedoch auch noch andere Restriktionen, die einen ähnlichen Effekt haben. Beispiele wären tageszeitabhängige Fahrtzeiten oder eine Beschränkung der Fahrtzeit zwischen zwei Orten. Die oben genannten Restriktionen können auch verschiedene Ausprägungen annehmen, z.B. mehrere Zeitfenster, Zeitfenster die gegen Zahlung einer Strafe verletzt werden dürfen, Besuchsreihenfolgen für mehr als zwei Orte, usw.
FAZIT: BEI DER TOURENPLANUNG MIT RESTRIKTIONEN IST DER EINSATZ VON ALGORITHMEN SINNVOLL
Das Ziel dieses Beitrags war es, dafür zu sensibilisieren, warum eine gute Tour nicht unbedingt gut auf einer Landkarte aussehen muss. Anhand der gezeigten Beispiele kann man gut erkennen, wie es dazu kommt. In beiden Fällen sind neue Informationen hinzugekommen, die zu berücksichtigen waren. Diese Informationen liefert eine Landkarte nicht. Sie ist im Wesentlichen darauf beschränkt, Informationen über Distanzen zu liefern. Mit jeder weiteren Nebenbedingung fügt man dem Problem jedoch eine weitere Dimension hinzu und auch wenn man versucht, diese in eine Landkarte zu integrieren und sie mit Informationen anzureichern, stößt man früher oder später an die Grenzen des Visualisierbaren. Für Probleme mit vielen Nebenbedingungen wird es also nie möglich sein, anhand ihrer Darstellung auf einer Landkarte zu entscheiden, ob eine Tour gut oder schlecht ist. Im Umkehrschluss bedeutet das jedoch auch, dass von Hand angefertigte Tourenpläne häufig problematisch sind, wenn es viele Nebenbedingungen gibt. In diesem Fall sind dann Algorithmen wie beispielsweise der PowerOpt notwendig. Denn sie sind, anders als das menschliche Auge, in der Lage, mehr als drei Dimensionen zu verarbeiten.