Mathematische Optimierungsverfahren werden seit Jahrzehnten erfolgreich in der Tourenplanung eingesetzt und wurden dementsprechend umfangreich erforscht. Allerdings wurden meist nur vereinfachte, idealisierte Modelle betrachtet. Erst durch die Kapazitäten moderner Rechner wurde es in den letzten Jahren möglich auch eine dreidimensionale Beladung zu berücksichtigen. Aber auch diese Ansätze berücksichtigen wesentliche, für die Praxis relevante Anforderungen nicht, die die Komplexität signifikant erhöhen. Wir realisieren in dieser Arbeit, ausgehend von einem metaheuristischen Ansatz unter Verwendung eines Ameisenkolonie-Algorithmus, eine direkt in der Logistik einsetzbare Lösung. Dementsprechend berücksichtigen wir unter anderem die Verladung passend zur Reihenfolge in der die Kunden beliefert werden, die detaillierte Stabilität der Beladung, die Verwendung von Anhängern, inhomogene Fahrzeugflotten, Arbeitszeitbeschränkungen, Priorisierung einzelner Ziele und Straßengegebenheiten. Als Ergebnis stehen Touren- und Beladungspläne in unmittelbar anwendbarer Form zur Verfügung.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

Wir betrachten in dieser Arbeit ein Vehicle Routing Problem (VRP) mit einer Kapazitätsbeschränkung unter Berücksichtigung einer dreidimensionalen Beladung. Diese besondere Problemstellung wurde erstmals von Gendreau et al. [11] untersucht. Grundsätzlich ist das VRP ein Modell für die Tourenplanung [13, 19]. Gegeben ist eine Anzahl von Zielen, die von einem einheitlichen Depot aus mit unterschiedlichen Gütern zu beliefern sind. Weiters ist die Distanz (bzw. die Fahrtkosten und die Fahrzeit) zwischen je zwei dieser Orte bekannt. Die mathematische Modellierung erfolgt dementsprechend durch einen vollständigen Graphen mit Kantengewichten. Gesucht sind nun Routen zur kostenoptimalen Auslieferung der Waren. Dabei muss jede Fahrt sowohl beim Depot starten als auch enden und jedes andere Ziel insgesamt genau einmal angesteuert werden.

Diese Aufgabenstellung wird in der Literatur mit den unterschiedlichsten Nebenbedingungen erweitert und untersucht. Dazu zählen z.B. verschiedenste Beschränkungen der Ladekapazität, die Anzahl der eingesetzten Fahrzeuge oder Zeitfenster für den Besuch eines Zielortes. Details finden sich beispielsweise in [13] oder [19]. Insgesamt entsteht so eine Aufgabenstellung, die mehrere für sich allein bereits nur sehr schwer lösbare Teilprobleme enthält, darunter das Rundreiseproblem (Travelling Salesman Problem, TSP) und das Bin-Packing Problem. Diese gehören beide zur Komplexitätsklasse der NP-vollständigen Probleme [14]. Dementsprechend ist kein allgemein anwendbarer effizienter Algorithmus bekannt, der eine optimale Lösung für eine größere Anzahl an Zielorten bzw. Frachtgütern exakt berechnet. Abhängig von der Aufgabenstellung kann eine exakte Lösung eventuell mit Methoden der Ganzzahligen Linearen Optimierung erfolgen [13], oft werden in der Literatur jedoch heuristische Verfahren eingesetzt [10, 11, 16]. Dies trifft insbesondere für die komplexen Nebenbedingungen zu, die wir in diesem Artikel betrachten. Diese werden im folgenden Abschnitt erläutert. Daran anschließend werden die einzelnen Bestandteile unserer Lösung erläutert. Unsere Vorgehensweise orientiert sich hierbei am metaheuristischen Ameisenkolonie-Algorithmus von Füllerer et al. [10], welcher bessere Ergebnisse als die in [11] verwendete Tabu-Suche liefert. Im Gegensatz zu den in diesen beiden Arbeiten verwendeten synthetischen Datensätzen beruhen unsere Berechnungen auf realen Daten eines unserer Kunden. Abschließend präsentieren wir entsprechende Ergebnisse.

2 Anforderungen

Das Ziel unserer Optimierung ist wie bereits angesprochen die Minimierung der auftretenden Gesamtkosten. Wir gehen dabei zunächst von einem fixen Kostensatz je gefahrenem Kilometer aus. Dementsprechend wird die Anzahl der zurück gelegten Straßenkilometer minimiert. Unsere Lösung ist hier jedoch sehr flexibel und kann beliebige zusätzliche Kosten wie Fixkosten pro LKW, Zuschläge für mehrtägige Fahrten, Mautzuschläge, typabhängige Kosten etc. unmittelbar berücksichtigen.

Wir beginnen zunächst mit einer Beschreibung der Nebenbedingungen wie sie in den Arbeiten [10, 11] betrachtet werden, die bereits eine dreidimensionale Beladung berücksichtigen:

1. Jedes einzelne Frachtstück verfügt über eine quaderförmige Gestalt, sowie über ein bekanntes Gewicht. Die einzelnen Maße können dabei höchst unterschiedlich sein, d.h. es wird nicht vorausgesetzt, dass ein Großteil der Frachtstücke dieselbe Dimension besitzt.

2. Für den Transport steht eine Flotte von einheitlichen LKW mit quaderförmigem Laderaum und vorgegebener Nutzlast zur Verfügung. Die Be- und Entladung erfolgt dabei vom Heck, wobei die Größe der Ladeöffnung der vollständigen Rückwand entspricht.

3. Die Beladung muss die Dimensionen des Laderaums einhalten, eine „überstehende“ Beladung ist unzulässig. Ebenso darf die Nutzlast nicht überschritten werden.

4. Die Reihenfolge in der die Kunden beliefert werden, muss bei der Erstellung des Beladeplans berücksichtigt werden. Das Abladen der gesamten einem Kunden zugeordneter Fracht muss also stets ohne die Bewegung von Frachtstücken anderer Kunden auf direktem Weg möglich sein. So blockiert beispielsweise das grau dargestellte Frachtstück in Abbildung 1a die beiden anderen, wenn die Entladungsrichtung entlang des eingezeichneten Pfeils angenommen wird.

5. Die einzelnen Frachtgüter werden stets parallel zu den Seitenflächen des jeweiligen LKW geladen (siehe Abbildung 1). Dabei sind Drehungen um 90◦ an der Grundfläche erlaubt, allerdings kein „kippen“, d.h. die Deckfläche ist eindeutig festgelegt.

6. Es wird zwischen zerbrechlichen und nicht zerbrechlichen Gütern unterschieden. Letztere dürfen nicht auf zerbrechliche Güter gestapelt werden, ansonsten darf beliebig gestapelt werden.

7. Werden Frachtstücke aufeinander gestapelt, so muss ein vorgegebener Prozentsatz (z.B. 75%) der Grundfläche des sich oberhalb befindlichen Quaders unterstützt sein.

Bild 1: Zwei Beladungen

Diese Bedingungen versuchen bereits einige relevante Details zu berücksichtigen, dennoch bleiben wichtige Punkte unberücksichtigt. Insbesondere ist in der Realität von der Verwendung unterschiedlicher LKW und der Verwendung von Anhängern auszugehen. Weiters ist eine einfache Überprüfung der unterstützen Fläche nicht ausreichend, um eine stabile Beladung sicher zu stellen, so ferne ein Prozentsatz von weniger als 100% angenommen wird. Eine Instabilität kann  so beispielsweise durch wiederholtes Aufstapeln größer werdender Boxen entstehen, wie dies in Abbildung 1b veranschaulicht wird. Wir berücksichtigen daher folgende Änderungen und Ergänzungen: (Nicht erneut angeführte Punkte haben wir unverändert übernommen.)

2a. Wir unterscheiden verschiedene LKW-Typen und auch verschiedene Anhänger, jeweils in beschränkter Anzahl. Auch Fahrzeuge mit mehreren, übereinander angeordneten Ladeebenen werden unterstützt. Alle Ladeflächen werden grundsätzlich gleichberechtigt genutzt. Mehrere Frachtstücke von ein und demselben Kunden können auf die einzelnen Ladeflächen eines Transports (also i.A. Motorwagen und Anhänger) aufgeteilt werden. Alternativ zur Heckladung berücksichtigen wir auch die Möglichkeit einer Entladung mittels Fahrzeugkran über die Bordwände bzw. die seitliche Beladung mittels Gabelstapler.
5a. Für jedes Frachtstück wird einzeln festgelegt ob die zuvor angesprochene Drehung um 90◦ zulässig ist.
6a. Zusätzlich zur Berücksichtigung der Zerbrechlichkeit werden Frachtstücke unterschieden, auf die keinesfalls gestapelt werden darf.
7a. Die ein Paket unterstützende Fläche wird mit dem Faktor gewichtet, mit dem sie selbst aufliegt. Dadurch wird die Stabilität gewährleistet und das Auftreten einer Situation analog zu Abbildung 1b verhindert.
8. Vereinzelt ist die Zufahrt zu Kunden nicht mit Anhänger möglich. Gegebenenfalls wird dann der Anhänger vor der Lieferung abgestellt und im Rahmen der Rückfahrt wieder aufgenommen. In diesem Fall darf die entsprechende Fracht selbstverständlich nicht im Anhänger geladen sein.
9. Einzelne Kunden können priorisiert werden, diese müssen am Beginn einer Tour beliefert werden.
10. Der Sonderfall, dass die Bestellung eines Kunden selbst die Ladekapazität des größten vorhandenen Transportmittels übersteigt, wird berücksichtigt. Nur in dieser Situation darf der Kunde von mehreren LKW beliefert werden.

Die Verwendung von Anhängern und nicht per Anhänger erreichbare Kunden werden beispielsweise bereits in den Arbeiten [2] und [16] berücksichtigt, allerdings nur mit einheitlicher Kapazität und eindimensionaler Kapazitätsschranke. Unterschiedliche Fahrzeugdimensionen finden sich bei [17], aber wiederum nur mit linearer Kapazitätsbeschränkung und auch ohne Berücksichtigung von Anhängern. Obwohl die in dieser Arbeit betrachteten Nebenbedingungen für sich betrachtet durchaus bereits untersucht wurden, so ergibt sich zusammen mit der dreidimensionalen Beladung eine wesentlich andere und neue Problemstellung. Es ist somit nicht möglich, die bereits bekannten Ansätze unmittelbar zu übertragen.

Eine signifikante Beschränkung unseres Modells bleibt weiterhin durch Annahme von quaderförmingen Dimensionen erhalten. Beladungsalgorithmen, die allgemeinere Objektformen berücksichtigen sind durchaus erforscht [18], erfordern aber wesentlich höheren Rechenaufwand. Ein kombiniertes Verfahren, das vollkommen beliebige Ladeformen zulässt erscheint derzeit nicht praktisch umsetzbar. Allerdings lässt sich die hier vorgestellte Lösung problemlos mit einer auf eine spezielle Kundenanforderung abgestimmte Beladungsroutine erweitern. Auch allgemeine Drehungen der Güter können so berücksichtigt werden, erfordern jedoch ebenfalls zusätzlichen Rechenaufwand. Weiters wird auf die Gewichtsverteilung der Beladung keine Rücksicht genommen, da davon ausgegangen wird, dass Güter mit verhältnismäßig geringer Masse transportiert werden. Jedoch ist es bei Bedarf auch möglich, dies in unserem Verfahren zu berücksichtigen, vergleiche auch [8]. Wir möchten festhalten, dass diese Bedingungen dann auch für jede auf einzelnen Fahrstrecken auftretende Teilbeladung einzuhalten sind. Sofern keine Verschiebung der verbleibenden Fracht erfolgen soll, was in dieser Arbeit vorausgesetzt wird, stellt dies demnach eine sehr restriktive Anforderung dar. Diese sollte deshalb nicht ohne unmittelbare praktische Relevanz berücksichtigt werden, um Lösungsqualität und Laufzeit nicht unnötig zu verschlechtern.

3 Beladungsalgorithmus

Die Erstellung einer Beladung stellt gemäß unserer Aufgabenstellung einen der Schwerpunkte dar. Ein Verladeplan wird von uns stets unter Vorgabe einer bestimmten Liste von Kunden ermittelt, für die auch bereits die Anfahrreihenfolge und der LKW Typ festgelegt wurden. Dadurch ist es möglich, dieses Teilproblem gewissermaßen isoliert zu betrachten. Dennoch darf nicht vergessen werden, dass es sich hierbei um ein schwieriges Problem handelt. Weiters ermöglicht diese Vorgehensweise den einfachen Austausch und die Erweiterbarkeit der Beladeroutine, sowie die Parallelisierung der Berechnung. Dieses dreidimensionale Bin-Packing Problem mit komplexen Nebenbedingungen wird in Zuge der Optimierung typischerweise tausende Male aufgerufen und ist demnach sehr zeitkritisch. Auf Grund dessen, ist eine exakte Lösung nicht möglich. In [10] werden deshalb zwei Heuristiken herangezogen. Die erste basiert auf einem Bottom-Left-Fill Ansatz, die zweite auf Maximierung der Berührungsfläche. Die Autoren benutzen beide Algorithmen sequentiell und wählen anschließend die bessere Lösung. Bei unseren Tests ergab sich durch die Verwendung beider Verfahren nur eine Steigerung der Erfolgsrate um etwa ein Prozent, bei Verdoppelung des Aufwandes. Aus diesem Grund haben wir uns entschieden nur die erste der beiden Methoden anzuwenden und wir beschreiben auch nur diese im Folgenden näher. Unabhängig davon stellen wir zunächst einige generelle Überlegungen an.

Vor dem Start des eigentlichen Beladevorgangs prüfen wir ob einer der drei folgenden Fälle eintritt, da dann die Existenz einer gültigen Beladung von vorne herein ausgeschlossen werden kann:

- Das Frachtgewicht übersteigt die zulässige Nutzlast.

- Das Gesamtvolumen der Fracht überschreitet das insgesamt vorhandene Ladevolumen.

- Die Summe der Deckflächen der Güter auf die nicht gestapelt werden darf, ist größer als die Grundfläche des Laderaums aller Ladeflächen.

Wir befassen uns zunächst mit der Beladung eines einzelnen Frachtraumes, d.h. ohne Berücksichtigung von Anhängern etc. Die Positionierung eines Frachtstücks erfolgt eindeutig durch Festlegung der Orientierung und durch Angabe der Koordinaten eines ausgezeichneten Eckpunktes. Die Orientierung ist eindeutig für Güter die nicht gedreht werden dürfen, ansonsten entspricht die Drehung um 90◦ in der Grundfläche einer Vertauschung von Länge und Breite.

3.1 Positionierung der Fracht

Die Laufzeit des Positionierungsalgorithmus wird wesentlich davon beeinflusst, auf welche Art und Weise die Koordinaten bestimmt werden, die für den ausgezeichneten Eckpunkt in Frage kommen. Ein Ansatz hierzu ist eine Diskretisierung des kontinuierlichen Raums mit Hilfe eines Würfelgitters, wie dies in [18] erfolgt. Als gravierender Nachteil ergibt sich eine sehr große Anzahl an Punkten, die zu berücksichtigen ist. Aus diesem Grund werden in [9] nur Punkte des Raumes betrachtet, die sich aus der schon teilweise erfolgten Beladung ergeben. Sei X die Menge aller x - Koordinaten aller Eckpunkte von bereits platzierten Frachtstücken, vereinigt mit 0. Analog werden die Mengen Y und Z definiert. Um einen neuen Quader einzufügen, kommen jetzt genau die Punkte aus dem kartesischen Produkt X × Y × Z in Frage. Die Idee bei dieser Auswahl ist, unnötigen Leerraum zwischen den einzelnen Quadern zu vermeiden.

Allerdings hat diese Methode den Nachteil, dass durch die „blinde“ Verknüpfung mittels des kartesischen Produkts viele zusätzliche Kombinationen entstehen, die einzig zu einem erhöhten Rechenaufwand führen. Ein in [4] beschriebenes Verfahren kann hier Abhilfe schaffen. Dieses beruht auf der Projektion der Eckpunkte eines neu platzierten Frachtstücks auf die Seitenflächen des LKW und der bereits eingeladenen Boxen. Dies wird in Abbildung 2 veranschaulicht. Die mit einem Kreis markierten Punkte geben jene Positionen an, an denen die nächste Box eingefügt werden kann. Die strichlierten Linien verdeutlichen die Projektion auf nicht unmittelbar angrenzende Flächen. In einzelnen Situationen werden jedoch auch brauchbare Punkte nicht ermittelt, die das ursprüngliche Verfahren gefunden hätte. Zwei dieser Punkte sind in unserem Beispiel durch Rauten gekennzeichnet. Dennoch haben wir uns entschlossen, diese Variante einzusetzen, da unsere Experimente keinen signifikanten Unterschied in der Lösungsqualität aber sehr wohl eine Verbesserung der Laufzeit um einen Faktor von ca. 4 zu Tage förderten.

Unabhängig davon, wie die Liste der möglichen Platzierungen erstellt wird, ist davon auszugehen, dass sie Einträge enthält die für keines der vorhandenen Frachtstücke geeignet sind. Um diese a priori von weiteren Überprüfungen auszuschließen, ziehen wir einen Quader heran, der in jeder Dimension die kleinste tatsächlich auftretende Abmessung aufweist. So konnten wir eine zusätzliche Laufzeitverbesserung von einigen Prozentpunkten erzielen.

Bild 2: Anwendung des Projektionsprinzips

3.2 Überprüfung einer Positionierung

Zunächst wird getestet, ob bei einer Positionierung des betrachteten Quaders an der aktuellen Stelle die Grenzen des Laderaumes eingehalten werden. Anschließend berechnen wir mit jedem bereits eingeladenen Frachtstück die Überschneidungen in allen drei Koordinatenrichtungen, siehe auch [9]. Tritt dabei mit ein und derselben Box in allen Dimensionen eine Überlappung auf, so würden die Objekte in einander liegen, die Platzierung ist klarerweise ungültig. Falls analog in genau zwei Koordinaten ein gemeinsames Intervall überdeckt wird, so sind die Gegenstände in der dritten Richtung sequentiell angeordnet - also direkt neben, vor oder über einander. Dies ermöglicht es, in Kombination mit der Anfahrtsreihenfolge der einzelnen Kunden, die Einhaltung der erforderlichen Entladungsreihenfolge zu überprüfen. Ist eine Entladung von mehreren Seiten erlaubt, so ist es ausreichend, sicher zu stellen, dass eine dieser Richtungen nicht blockiert ist.

Im Falle einer Anordnung unmittelbar über einem bereits eingeladenen Quader wird die Fläche der Überschneidung ermittelt. Die unterstützte Fläche ergibt sich unmittelbar durch Summation. Wie in Abschnitt 2 erläutert, führen wir diese gewichtet mit dem Anteil der eigenen Unterstützung durch. Abbildung 1b zeigt eine Reihe von Frachtstücken, so dass zwar 75% der Grundfläche eines jeden einzelnen auf dem vorhergehenden aufliegt, aber dennoch keine Stabilität gegeben ist. Unser modifizierter Algorithmus erkennt dies. Im gezeigten Bild beispielsweise, beträgt die gewichtete Unterstützung des obersten Quaders nur ca. 42%.

3.3 Bottom-Left-Fill Algorithmus

Der Bottom-Left-Fill Ansatz beruht darauf, für jedes Frachtgut die zugehörige Liste möglicher Punkte in aufsteigender Reihenfolge auf Zulässigkeit zu testen. Der Algorithmus stoppt, sobald ein geeigneter Ort gefunden wurde. Falls die Drehung des aktuellen Frachtstücks erlaubt ist, werden hierbei stets beide Orientierungen überprüft. Die Ordnung der Platzierungspunkte erfolgt hierbei lexikografisch, es finden sich jedoch in der Literatur verschiedene Vorschläge für die Reihenfolge der Koordinaten, siehe [9, 10, 11]. Abweichend von diesen Angaben sortieren wir zunächst an Hand der Längen-Koordinate, dann nach der Breiten-Koordinate und erst abschließend nach der Höhe, um so die größtmögliche Kompaktheit der Ladung zu erreichen. Die gesamte Beladung entsteht, in dem die Quader in einer zuvor fest gelegten Reihenfolge Stück für Stück eingeladen werden. Die Intuition legt nahe, dass die Ware der zuerst belieferten Kunden als letztes eingeladen werden sollte, um die Entladbarkeit zu gewährleisten. Dementsprechend werden die Frachtstücke invers zur Lieferreihenfolge sortiert. Innerhalb der Zugehörigkeit zu einem Kunden werden Gegenstände zuerst gereiht, auf die gestapelt werden darf. Gibt es in einer dieser Gruppen mehrere Stücke, werden diese nach absteigendem Volumen angeordnet.

Bild 3: Beladungspläne zu Abbildung 2

Ändert man die Reihenfolge der Frachtstücke und wiederholt die Heuristik von Beginn an, so ergibt sich im Allgemeinen auch ein anderes Ergebnis. Dies wird ausgenutzt, falls keine gültige Beladung gefunden wurde. So wird erst nach einer gewissen Anzahl von Fehlschlägen das Verfahren abgebrochen und die zugehörige Route muss verworfen werden. Detaillierte Vorschläge für eine systematische Umsortierung finden sich in [9]. Zu beachten ist, dass komplexitätsbedingt meist nur ein verschwindend kleiner Teil aller möglichen Permutationen tatsächlich angewandt werden kann. Die Anzahl der Wiederholungen begrenzen wir abhängig von der Anzahl der beteiligten Kunden sowie einem adjustierbaren Faktor.

Für den Fall, dass z.B. durch Verwendung eines Anhängers mehrere Laderäume zur Verfügung stehen, haben wir das folgende Verfahren entwickelt: Die Beladung selbst wird gemäß obiger Beschreibung für jede Ladefläche separat ermittelt. Wir führen jedoch eine gemeinsame Liste der noch einzuladenden Güter und bestimmen die zu verwendende Ladefläche jeweils zufällig. Ist die Platzierung auf der gewählten Ladefläche nicht mehr möglich, werden die anderen reihum heran gezogen. Durch diese Vorgangsweise erreichen wir eine gleichmäßige Verteilung und einfache Randomisierung die keine Umsortierung der Stückliste erfordert. Alternativ kann auch die zufällige Wahl der Ladefläche nur einmal und einheitlich für alle Frachtstücke eines Kunden erfolgen.

3.4 Beladungspläne

Sofern benötigt, erstellen wir aus den geometrischen Daten auch Beladungspläne. Zu beachten ist, dass die Beladungsreihenfolge von der inversen Entladungsreihenfolge abweichen kann. Dies kann insbesondere auftreten, wenn mit unterschiedlichen Hilfsmitteln gearbeitet wird. Beispielsweise ist dies der Fall bei Beladung mittels Gabelstapler über eine Seite, aber Entladung über beide Bordwände mittels Fahrzeugkran. Die jeweils zulässige Einladereihenfolge lässt sich jedoch einfach durch angepasste lexikographische Ordnung der zugehörigen Platzierungspunkte ermitteln.

Bei der Darstellung der fertigen Pläne ist auf das zur Verfügung stehende Medium zu achten. So eignet sich eine dreidimensionale Visualisierung wie in Abbildung 2 zur schrittweisen Veranschaulichung am PC. Zur Erstellung von Papierausdrucken generieren wir jedoch zweidimensionale Schnittdarstellungen, wie sie in Abbildung 3 dargestellt sind. Der Pfeil markiert dabei die Beladungsrichtung.

Bild 4: Die Clarke & Wright Einsparungsheuristik

4 Clarke & Wright Einsparungsheuristik

Hierbei handelt es sich um ein einfaches aber bewährtes Verfahren zur Erzeugung einer Näherungslösung [3, 13], das von einer homogenen und stückmäßig unbegrenzten Fahrzeugflotte ausgeht. Im ersten Schritt wird jedem Kunden ein eigener LKW zugewiesen, der ausschließlich ihn beliefert. Nun berechnet man für je zwei Kunden die Ersparnis die sich ergibt, wenn ein LKW direkt vom ersten zum zweiten Kunden fährt. Durch diese Zusammenlegung fällt einerseits die Fahrt vom ersten Kunden zum Depot und die Fahrt vom Depot zum zweiten Kunden weg, sowie andererseits allenfalls vorhandene Fixkosten des eigesparten LKW. Anschließend werden diese Werte absteigend sortiert und jenes Paar gewählt, für das sich die größte Einsparung ergibt und alle Nebenbedingungen eingehalten werden können. Insbesondere muss für unsere Aufgabenstellung also auch eine zulässige Beladung gefunden worden sein. Dieses Verfahren wird so lange iteriert, bis keine weitere Zusammenlegung mehr möglich ist. Die Liste der Einsparungen ist dabei stets durch Wegstreichen nicht mehr zulässiger Kombinationen aktuell zu halten.

Abbildung 4 veranschaulicht ein simples Beispiel ohne Berücksichtigung von Nebenbedingungen. Der erste Graph zeigt die (symmetrischen) Entfernungen einer Aufgabenstellung mit einem Depot D und drei Kunden. In der Mitte wird der Initialschritt veranschaulicht. Die größte Einsparung ergibt sich nun durch die Paare (1, 2) bzw. (2, 1), wir entscheiden uns zufällig für das erste. Das Ergebnis ist im dritten Graphen dargestellt. Hier sind nur mehr die Kombinationen (2, 3) und (3, 1) für den folgenden Schritt zulässig.

Dieser Algorithmus kann auch einfach randomisiert werden. Statt immer die lokal beste Wahl zu treffen, kann aus einer Liste von attraktiven Kandidaten eine gemäß der Einsparung gewichtete zufällige Auswahl erfolgen. Dadurch ist eine direkte Verwendung in einem metaheuristischen Verfahren möglich, worauf im Folgenden genauer eingegangen wird. Eine strikte Priorisierung, die erfordert, dass ein bestimmter Kunde am Beginn der Tour beliefert wird, lässt sich auf einfache Weise realisieren. Hierfür werden alle Zusammenlegungen die den entsprechenden Kunden an zweiter Stelle einfügen, a priori ausgeschlossen. Andere Regeln, wie z.B. die Vorgabe eines spätest zulässigen Lieferzeitpunkts, können analog zu den anderen Nebenbedingungen berücksichtigt werden.

5 Ameisenkolonie-Algorithmus

Ameisenkolonie-Algorithmen orientieren sich am natürlichen Verhalten von Ameisen bei der Futtersuche [7, 9]. Diese verwenden Duftstoffe (Pheromone) zur Markierung des von ihnen zurück gelegten Weges. Abbildung 5 veranschaulicht dieses Prinzip. Das linke Bild zeigt die möglichen Wege, die von den einzelnen Ameisen vom Nest zur Position des Futters gewählt werden können. Existieren mehrere unterschiedlich lange Wege zu einer Nahrungsquelle, so entsteht auf dem kürzesten Pfad auf natürliche Weise die intensivste Pheromonspur, wie dies in der mittleren Grafik durch die Strichstärken dargestellt wird. Daraufhin wird dieser Weg vermehrt genutzt, was eine weitere Verstärkung bewirkt, bis wie im letzten Bild größtenteils diese Lösung verfolgt wird. Dabei ist jedoch die Konzentration auf einen einzelnen Weg nicht ausschließlich, so dass weiterhin die Möglichkeit besteht einem lokalen Optimum zu entkommen. Die so entstehende Lösung ist einem unabhängigen, rein zufälligen Verhalten weit überlegen, jedoch nicht notwendigerweise optimal.

Bild 5: Die Entwicklung einer Pheromonspur

Unsere Lösung basiert auf dem in [9] und [10] beschriebenen Algorithmus. Da wir hier keine wesentlichen Änderungen durchgeführt haben, beschränken wir uns auf eine kurze Beschreibung der wesentlichen Vorgangsweise und verweisen für Details auf die angegebenen Quellen. Auch die dort verwendeten Parameterwerte erwiesen sich als gut brauchbarer Ausgangspunkt für ein an unsere konkreten Daten angepasstes Feintuning. Die Bewältigung des Problems erfolgt dabei in mehreren Stufen bzw. Generationen von Lösungen. In jeder Generation wird eine gewisse Anzahl von Lösungen erstellt, und die besten davon werden heran gezogen, um die Pheromonverteilung für die Erstellung der folgenden Generation zu aktualisieren. Genauer gesagt wird zu jedem geordneten Paar von Zielpunkten ein Pheromonwert gespeichert, der misst wie Erfolg versprechend es ist, diese Ziele unmittelbar hintereinander in der gegebenen Reihenfolge in eine Tour aufzunehmen. Um die Gefahr der schnellen Konvergenz zu einem lokalen Optimum zu verkleinern, erfolgt zusammen mit jedem Update eine Abschwächung der zuvor vorhandenen Werte. Zum Start des Algorithmus wird eine gleichmäßige Aufteilung des Pheromons angenommen.

Unser algorithmisches Konzept wird in Abbildung 6 veranschaulicht. Die Berechnung der einzelnen Touren erfolgt mit der randomisierten Einsparungsheuristik von Clarke & Wright. Die Attraktivität einer Kombination ergibt sich dabei aber nicht nur aus dem Einsparungspotential sondern, auch durch die zusätzliche Berücksichtigung der Pheromonwerte. Anschließend werden diverse lokale Verbesserungsheuristiken auf jede Lösung so lange angewandt, bis keine weitere Steigerung mit diesen Verfahren mehr möglich ist. Wir verwenden dabei die in [12] beschriebenen Algorithmen 2-Opt, Or-Exchange, Relocation und Exchange.

Im Rahmen dieser Berechnungsschritte werden einzelne Touren - und die dazu gehörenden Beladungen - wiederholt abgefragt. Aus diesem Grund ist es sinnvoll einen Pool bereits untersuchter Touren zu führen, wie dies in [9] vorgeschlagen wird. Dadurch ergibt sich eine Verringerung der Laufzeit um ca. 70%. Als Nachteil bleibt festzuhalten, dass dadurch die Parallelisierung auf Grund der erforderlichen Synchronisation erschwert wird. Wir haben deswegen ausschließlich die Beladungssubroutine parallelisiert, wodurch wir unter Verwendung von vier Rechenkernen größenordnungsmäßig eine weitere Halbierung der Laufzeit erreichen konnten.

Bild 6: Algorithmisches Gesamtkonzept

6 Verwendung mehrerer LKW-Typen in beschränkter Anzahl

Eine aktuelle Übersicht, die sich auf Arbeiten mit inhomogenen Fahrzeugflotten konzentriert, findet sich in [1]. Grundsätzlich sind dabei zwei Standpunkte in der Literatur zu finden. Betrachtet man das Problem ohne Obergrenzen für die Anzahl der einzelnen LKW jedes Typs, so wird die optimale Flottenzusammenstellung für ein gegebenes Problem gesucht. Wir befassen uns jedoch mit der zweiten Aufgabe, der optimalen Abwicklung unter Ausnutzung der tatsächlich vorhandenen Mittel.

Stehen unterschiedliche LKW-Typen zur Verfügung, so empfiehlt es sich in unserem Anwendungsfall, nicht jede einzelne Tour mit jeder möglichen Fahrzeugkombination mehrfach zu berechnen, da dies den Aufwand stark erhöht. Selbst wenn diese Ergebnisse vorliegen, wäre noch immer das schwierige Problem zu lösen, wie die begrenzte Anzahl an Fahrzeugen jedes Typs letztendlich zugewiesen wird, siehe [17]. Wir gehen stattdessen davon aus, dass eine lineare Ordnung der Transportmittel nach aufsteigender Kapazität sinnvoll möglich ist. Unser Sortierkriterium ist hierbei das Ladevolumen. Wir setzen dabei implizit voraus, dass die Kosten je gefahrenem Kilometer mit steigendem Ladevolumen nicht sinken. Weiters gehen wir davon aus, dass - sofern ein LKW ein bestimmtes Frachtgut transportieren kann - auch jeder andere mit größerem Ladevolumen dazu in der Lage ist. Alle diese Voraussetzungen sind im Allgemeinen realistisch und auch in unserem Anwendungsfall erfüllt.

Im Initialisierungsschritt der Clarke & Wright Einsparungsheuristik versorgen wir jeden Kunden mit dem kleinsten LKW mit dem dies möglich ist. Hierbei lassen wir auch eine Überschreitung der Anzahlen der zur Verfügung stehenden LKW zu. Ist selbst die Kapazität des größten vorhandenen Transportmittels nicht ausreichend, die vollständige Bestellung eines Kunden aufzunehmen, nehmen wir an dieser Stelle im Ablauf eine Aufteilung vor. Die einzelnen Teillieferungen werden in der weiteren Rechnung so behandelt, als ob es sich um unterschiedliche Kunden handeln würde. Der einzige Unterschied ist, dass nicht versucht wird, mehrere dieser künstlichen Ziele in einer Tour zu vereinen.

Bei der Kombination zweier Touren und bei Verbesserungsschritten wird analog das kleinste ver-fügbare Transportmittel verwendet. Als zur Verfügung stehend betrachtet werden dabei momentan nicht verplante LKW, sowie jene, die bei der bzw. den zu ersetzenden Touren eingeplant waren. Am Ende dieser Schritte kann es bedingt durch die anfängliche Zuweisung dazu kommen, dass mehr LKW eines Typs heran gezogen werden, als zur Verfügung stehen. Dies ist jedoch ein seltener Fall, da bei jedem Optimierungsschritt auf die noch nicht verplante Fahrzeugflotte geachtet wird und eine anfängliche Überschreitung sich so meist ausgleicht. Ist dies jedoch nicht der Fall, so wird abschließend versucht die Beschränkung zu erfüllen, indem einzelne Touren unverändert auf den nächstgrößeren freien LKW umgeplant werden. Für den Fall, dass die einzelnen Fahrzeugtypen unterschiedliche Kostensätze aufweisen, ist weiters eine Modifikation der Clarke & Wright Heuristik erforderlich. Ist nämlich durch eine Zusammenlegung zweier Touren ein größerer LKW erforderlich, so können dadurch die Gesamtkosten steigen, obwohl die gefahrenen Kilometer sinken. Andererseits kann gerade ein solcher Schritt eine weitere Kombination ermöglichen, die insgesamt eine Verbesserung bewirkt, die sonst unmöglich wäre. Aus diesem Grund gehen wir analog zum Realistic Opportunity Savings Algorithm [5] vor und berücksichtigen zukünftig mögliche Einsparungen durch einen zusätzlichen Summanden. Diesen legen wir proportional zum Restvolumen und in Abhängigkeit der jeweiligen Daten fest.

Tabelle 1: Charakteristik unserer Musterdaten und Ergebnisse

Dieses Verfahren liefert für unseren konkreten Einsatz ausgezeichnete Ergebnisse ohne die Laufzeit wesentlich zu verlängern. Wesentlich hierfür ist die Randomisierung des Algorithmus, die es zusammen mit dem metaheuristschen Ansatz ermöglicht, lokalen Optima zu entkommen. Die Verwendung der Pheromonwerte und der weitere Ablauf bleiben dabei unverändert. Auch in dieser Variante ist es effizient einen Pool von bereits untersuchten Problemen zu speichern, wobei zusätzlich der verwendete LKW-Typ abzuspeichern ist.

7 Ergebnisse

Wir untersuchen die Performance unseres Verfahrens unter anderem an Hand von Daten, die von unserem Kunden zur Verfügung gestellt wurden. Tabelle 1 zeigt die Größe der entsprechenden Probleme und die Eckdaten der ermittelten Lösungen. Der Algorithmus wurde hierfür in C++ implementiert und unter Windows 7 auf einem PC ausgeführt, der mit einem 2,83 GHz getakteten Intel Q9550 Vierkernprozessor und 8 GB Ram ausgestattet wurde. Die Geokoordinaten der einzelnen Zieladressen und die Entfernungen zwischen diesen wurden mit einem Online- Kartendienst ermittelt. Zur besseren Vergleichbarkeit geben wir die Laufzeiten bei nicht aktivierter Parallelisierung an.

Jeder der Datensätze 1 bis 5 von Tabelle 1 umfasst dabei Ziele aus einer abgegrenzten Region innerhalb Österreichs und besteht aus realen Daten wie sie bei unserem Kunden regelmäßig anfallen. Im Vergleich zu den tatsächlich gefahrenen Routen erreicht unser Algorithmus Einsparungen von mehr als 30% und ermöglicht so eine signifikante Reduktion der Kosten. Abbildung 7 zeigt ein Beispiel einer erstellten Tour. Der letzte angeführte Datensatz kombiniert alle Zielgebiete und berechnet eine gemeinsame Lösung für ganz Österreich. Wie aus der Tabelle ersichtlich ist, ermöglicht dies die Einsparung eines Fahrzeugs und die insgesamt zurück gelegte Strecke sinkt um ca. 500 km im Vergleich zur Summe der Einzellösungen. Auf der anderen Seite erfordert die Berechnung beinahe die 12-fache Laufzeit, ist aber dennoch innerhalb einiger Minuten fertig gestellt.

 Bild 7: Ein Tourenplan

Auch wenn aus diesen Ergebnissen nicht auf das genaue Laufzeitverhalten geschlossen werden kann, so ist doch deutlich, dass der Aufwand superlinear mit der Größe des Problems wächst, siehe auch [10]. Dementsprechend ist es nicht ratsam, Datensätze mit mehreren hundert bzw. tausend Kunden direkt zu berechnen. Solche Probleme können zunächst mit einem Clustering- Ansatz in mehrere Teilprobleme zerlegt werden, wie dies in [15] beschrieben ist.

8 Fazit

Mit unserem Algorithmus realisieren wir eine einmalige Kombination aus Routen- und Beladungsoptimierung zur Minimierung der Transportkosten inklusive Erstellung eines Verladeplans, die sämtliche Anforderungen üblicher Transport- und Logistikproblemstellungen erfüllt. Insbesondere wird eine dreidimensionale Beladung berücksichtigt, die sicherstellt, dass die Frachtstücke in der erforderlichen Reihenfolge stets frei zugänglich sind. Weiters ist die Auswirkung einzelner Vorgaben wie z.B. die Flottenzusammenstellung inkl. unterschiedlicher Anhänger, die Vorgabe erster Abladeorte und nicht per Anhänger belieferbarerKunden, unmittelbar ersichtlich. Dadurch werden den Anwendern die Auswirkungen verschiedener Strategien aufgezeigt.

Algorithmisch betrachtet, verbindet diese Aufgabenstellung das Traveling Salesman Problem mit einem Bin Packing Problem. Da die in der Praxis auftretenden Problemgrößen aus wissenschaftlicher Sicht eine exakte Lösung nicht zulassen, werden effiziente heuristische Verfahren eingesetzt. Die einzelnen Touren werden durch lokale Suche optimiert. Die Verwendung eines Ameisenkolonie-Algorithmus stellt insgesamt bestmögliche Resultate sicher und erlaubt es uns, in einem konkreten Anwendungsfall die Anzahl der gefahrenen Kilometer um mehr als 30% zu reduzieren. Unser Verfahren übersteigt die Möglichkeiten einer manuellen Planung oder herkömmlichen Berechnungen, die die Beladung nicht berücksichtigen, um viele Größenordnungen, wodurch diese gravierende Einsparung erzielt werden kann.

Literatur

[1]    Baldacci, Roberto, Maria Battarra, and Daniele Vigo: Routing a heterogeneous fleet of vehicles. In Golden, Bruce, S. Raghavan, and Edward Wasil (editors): The Vehicle Routing Problem: Latest Advances and New Challenges, page 337–360. Springer, New York, NY, 2008.

[2]    Chao, I Ming: A tabu search method for the truck and trailer routing problem. Computers and Operations Research, 29:33–51, 2002.

[3]    Clarke, G. and J.W. Wright: Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12:568–581, 1964.

[4]    Crainic, Teodor Gabriel, Guido Perboli, and Roberto Tadei: Extreme point-based heuristics for three-dimensional bin packing. INFORMS Journal on Computing, 20(3):368–384, 2008.

[5]    Desrochers, Martin and T. W. Verhoog: A new heuristic for the fleet size and mix vehicle routing problem. Computers & Operations Research, 18(3):263–274, 1991.

[6]    Domschke, Wolfgang und Armin Scholl: Logistik II: Rundreisen und Touren. Oldenbourg- Verlag, München - Wien, fünfte Auflage, 2010.

[7]    Dorigo, Marco and Christian Blum: Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2-3):243–278, 2005.

[8]    Eley, Michael: Solving container loading problems by block arrangement. European Journal of Operational Research, 141(2):393–409, 2002.

[9]    Füllerer, Günther Josef: Vehicle routing with multi-dimensional loading constraints. Dissertation, Universität Wien, Fakultät für Wirtschaftswissenschaften, 2008.

[10]    Fuellerer, Guenther, Karl F. Doerner, Richard F. Hartl, and Manuel Iori: Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, 201(3):751–759, 2010.

[11]    Gendreau, Michel, Manuel Iori, Gilbert Laporte, and Silvano Martello: A tabu search algorithm for a routing and container loading problem. Transportation Science, 40(3):342–350, 2006.

[12]    Kindervater, G.A.P. and M.W.P. Savelsbergh: Vehicle routing: Handling edges exchanges windows. In Aarts, E. and J.K. Lenstra (editors): Local Search in Combinatorial Optimization, page 337–360. John Wiley and Sons, Chichester, 1997.

[13]    Laporte, Gilbert: The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59:345–358, 1992.

[14]    Papadimitriou, Christos H. and Kenneth Steiglitz: Combinatorial Optimization. Dover Publications, Mineola, New York, 1998.

[15]    Reimann, Marc, Karl Doerner, and Richard F. Hartl: D-ants: Savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 31(4):563–591, 2004.

[16]    Semet, Frédéric and Eric Taillard: Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations Research, 41:469–488, 1993.

[17]    Taillard, Éric D.: A heuristic column generation method for the heterogeneous fleet vrp. RAIRO Rech. Opér., 33(1):1–14, 1999.

[18]    Tiwari, Santosh, Georges Fadel, and Peter Fenyes: A fast and efficient compact packing algorithm for sae and iso luggage packing problems. Journal of Computing and Information Science in Engineering, 10(2):021010, 2010.

[19]    Toth, Paolo and Daniele Vigo (editors): The Vehicle Routing Problem. SIAM, Philadelphia, Pa., 2002.