Kundenseparierung
Ausladen ohne Hindernisse
Bisher haben wir nur die Auswirkung der Laderaumkapazitäten auf die Tourenfestlegung betrachtet. In einem realistischen Szenario ist die Kopplung der Probleme Vehicle-Routing und dreidimensionales Packen wechselseitig: Eine Packreihenfolge, bei der vor jedem Ausladen erst eine Reihe blockierender, für spätere Tourkunden bestimmte Teile entnommen und danach wieder eingeladen werden müssen, ist nicht akzeptabel. Bei jedem Kunden müssen alle auszuladenden Waren sofort frei zugä nglich sein. Somit definiert die Tourreihenfolge auch eine Nebenbedingung für das Packmuster im Laderaum.Die Integration in einen am ZPR entwickelten, exakten Packalgorithmus, der auf einer graphentheoretischen Charakterisierung von Packmustern beruht, ist direkt möglich. Eine entsprechende Erweiterung der Packheuristiken wurde mit folgenden Arten der Kundenseparierung, so bezeichnen wir die räumliche Trennung von Waren, die für verschiedene Kunden bestimmt sind, realisiert.
Trennwände entlang einer festen Achse
In vielen Fällen werden in der Praxis innerhalb des Laderaums Trennwände eingesetzt, um verschiedene Ladepositionen abzutrennen. Somit sind zwei Dimensionen des Quaders, in den die Kisten eines Kunden gepackt werden, durch die entsprechenden La deraumdimensionen festgelegt. Nur noch die dritte, variable Dimension ist für das Stauraumproblem relevant. Die Berechnung der entsprechenden Größen kann im Preprocessing erfolgen. Für jeden Kunden ist hier folgendes dreidimensionale Packproblem zu lösen: Finde einen möglichst kurzen Quader mit vorgegebenem Querschnitt (Strip-Packing-Problem). Diese Werte können dann wieder als Kapazitäten für ein kapazitätsbeschränktes Vehicle-Routing-Problem (s.o.) verwendet werden.
Trennwände entlang variabler Achsen
In diesem allgemeineren Modell werden die Trennwände parallel zu einer ausgewählten Seitenfläche des alle bisher gepackten Kisten umgebenden Quaders gezogen. Diese Variante ist erheblich aufwendiger als die vorangegangene. Sie erfordert be i jeder Neuberechnung einer Laderaumbelegung im Vehicle-Routing-Algorithmus die Lösung dreier dreidimensionaler Strip-Packing-Probleme.
Rekombination ,,angebrochener" Layer
Fast alle dreidimensionalen Packverfahren basieren auf einer Dimensionsreduktion durch die Verwendung von Layern, die nur eine Kiste hoch sind. In dieser Art der Kundenseparierung werden die ,,angebrochenen" Layer zweier benachbarter Kunden kombiniert. Ob die Stauraumbedingung hier erhalten bleibt, hängt von den konkreten praktischen Einsatzbedingungen ab. Wie bei der Separierung durch Trennwände entlang einer festen Achse werden für jeden Kunden ,,volle" Layer im Preprocessing berechnet. Im Vehicle-Routing-Problem ist dann neben der Überprüfung der Kapazitätsrestriktion für jede Einfügeoperation ein zweidimensionales Knapsackproblem mit relativ wenigen Kisten zu lösen.