Umstauen: Untergrenze und Suche erklärt
Stellen Sie sich vor: Auf einem Containerplatz stehen Container in Stapeln, und der Kran soll sie in einer festen Reihenfolge abholen. Der nächste liegt unter drei anderen. Die drei müssen erst auf andere Stapel, und dort stehen sie vielleicht schon dem übernächsten im Weg. Wie wenig Umstapeln genügt, und woher weiß man, dass es nicht noch weniger geht?
Das ist das Umstauen: Container, die einem gesuchten im Weg stehen, werden auf andere Stapel umgesetzt, und jedes einzelne Umsetzen heißt Hub. Eine Untergrenze ist eine Zahl von Hüben, die kein Plan unterschreiten kann. Die einfachste entsteht, indem man die blockierenden Container zählt. Die Leitfrage dieser Linie lautet: Wie nah kommt man dem besten Plan mit einer Regel, mit einer Suche und mit einer beweisbaren Untergrenze, und wann lohnt sich welches Verfahren?
Fünfzehn Stücke gehen dem nach, meist an kleinen Buchten, also Plätzen mit wenigen Stapeln nebeneinander und einigen Lagen (Containern übereinander); ein Stück geht bis 48 Stapel. Die ersten Stücke handeln von einer einfachen Regel, wohin ein Container kommt, und vom Zählen der Blockierer. Dann folgen Suchen, die alle Umsetzfolgen durchprobieren und mit der Zählung früh aufgeben, wo es nicht mehr besser wird, und ein mathematisches Modell, das ein Lösungsprogramm exakt löst. Die zweite Hälfte verändert die Aufgabe: Vorsortieren, bevor abgeholt wird, Einlagern mit geschätzter Abfahrtszeit und eine Abrufreihenfolge, die nur gruppenweise bekannt ist. Die Erklärseiten zur Untergrenze und zum Vorsortieren erzählen das zuerst im Alltagsbild, ganz ohne Formeln. Das Stauen von Schiffen behandelt die Erklärseite Schiffsstauplanung.
Was diese Linie ist und was nicht: Alle Befunde stammen von erfundenen Plätzen mit zufälligen Abrufreihenfolgen und kleinen Buchten, nicht von einem echten Terminal. Bei 4 Stapeln trifft die einfache Zählung den besten Plan bei zwei Lagen in 70 von 100 vollen Buchten, bei vier Lagen nur in 4 von 100. Bei niedrigen Stapeln stimmt das Zählen also meist, bei hohen braucht der beste Plan fast immer mehr Hübe als gezählt.
In short: Covers the container relocation problem (block relocation) in a yard: lower bounds, iterative-deepening A* search with state memoization, an integer programming model and column formulation, pre-marshalling, uncertain retrieval order, learned move ordering and choosing a method by measurement.
Hintergrund zum Thema: Hafenlogistik.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Die Untergrenze beim Umstauen verständlich erklärt
Wie viele Container muss man mindestens umsetzen, und warum reicht das oft nicht? Erst für Einsteiger im Bild einer Parkgasse, dann für Fachleute mit den Sätzen und den gemessenen Lücken.
Vorsortieren von Containern verständlich erklärt
Warum Aufräumen vor dem Abholen sicher klingt und doch zwei Haken hat: Es braucht freien Platz zum Ausweichen, und es kostet mehr Handgriffe als das Umstapeln erst beim Abruf. Erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell und Messwerten.
Von der einfachen Regel zur Verfahrenswahl: zählen, suchen, vergleichen
Die Wurzel ist das Umstauen bei bekannter Reihenfolge mit einer einfachen Regel für den Zielstapel. Aus ihrer Lücke folgt die Untergrenze, und von dort gehen mehrere Wege ab: die Freiheit, auch andere Container zu bewegen, die Knotenexplosion der vollständigen Suche, die iterative Vertiefung mit Zustandsmerken, das ganzzahlige Modell mit seiner Spaltenformulierung und die schärferen Untergrenzen, die bei vielen Stapeln auf ihre Asymptotik geprüft werden.
Die zweite Hälfte verändert die Aufgabe selbst: Vorsortieren statt Abrufen, Einlagern mit geschätzter Abfahrtszeit und eine nur gruppenweise bekannte Abrufreihenfolge. Ein gelernter Verzweiger fragt, ob die Suche ihre Reihenfolge lernen kann. Die Verfahrenswahl führt zuletzt die Wege zusammen und stellt Regel, Suche und Schranke nebeneinander.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelt umrandet sind Demos aus anderen Linien: IDA* aus der Heuristischen Baumsuche, Branch and Price aus der Exakten Suche, Isomorphieausschluss aus dem Abzählen und Vorhersagen nutzen aus den Online-Algorithmen. Doppelt umrandet ist die Verfahrenswahl, in der mehrere Wege zusammenlaufen. Die Stücke Spaltenformulierung und Gelernter Verzweiger sind optional.
Verwandt in anderen Linien
- Heuristische Baumsuche — Das Verfahren IDA* der Heuristischen Baumsuche geht tiefer statt breiter und braucht eine Schätzung des Restwegs. Die Demo IDA* beim Umstauen setzt die Untergrenze aus dieser Linie als Schätzung ein und misst, wie viele Knoten das spart.
- Exakte Suche — Der Suchbaum der Exakten Suche zeigt, wie Branch and Price Spalten im Baum erzeugt. Die Demo Spaltenformulierung beim Umstauen löst nur den Wurzelknoten dieser Idee und zeigt, wann dort das Optimum nicht bewiesen ist.
- Abzählen und erzeugende Funktionen — Der Isomorphieausschluss zählt gleiche Objekte nur einmal. Die Demo Gleiche Zustände wendet das auf die Stapel einer Bucht an und misst, was das Merken gleicher Zustände und das Vertauschen von Stapeln in der Suche bringen.
- Online-Algorithmen — Die Demo Vorhersagen nutzen fragt, was ein Rat über die Zukunft wert ist. Die Demo Unbekannte Reihenfolge stellt dieselbe Frage fürs Umstauen: Wie viel hilft eine Vorschau auf die nächsten Abrufe, wenn nur Gruppen bekannt sind?
Zielstapel wählen: Umstauen mit bekannter Abrufreihenfolge
Verfolgen Sie, wie eine einfache Regel, die engste Passung, beim Umstauen den Zielstapel wählt und wie nah sie dem besten Plan kommt. Bei 4 Stapeln trifft sie das Optimum bei zwei Lagen in 100 von 100 Buchten, bei vier Lagen in 52. Der Haken: Ohne Untergrenze oder exakte Suche weiß man nicht, wie weit es noch ist, und an einer kleinen Bucht scheitert sie.
Demo starten →Untergrenze: blockierende Container zählen
Verfolgen Sie, wie die Zahl der blockierenden Container eine Untergrenze für die Hübe ergibt und wie weit sie vom Optimum entfernt liegt. Bei 4 Stapeln trifft sie das Optimum bei zwei Lagen in 70 von 100 Buchten, bei vier Lagen in 4. Der Haken: Ein umgesetzter Container kann auf dem neuen Stapel wieder blockieren, das sieht die einfache Zählung nicht.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Restricted und unrestricted: Was bringt die Freiheit?
Verfolgen Sie, was sich beim Umstauen ändert, wenn auch Container bewegt werden dürfen, die nicht über dem gesuchten stehen. Bei vier Stapeln und vier Lagen hilft das in 38 von 100 Buchten, bei zwei Lagen in keiner. Der Haken: Von der Lücke zur Untergrenze schließt die Freiheit nur 6 bis 14 Prozent, und gemessen sind nur kleine Buchten.
Demo starten →Alle Hubfolgen durchgehen: die Knotenexplosion
Verfolgen Sie, wie die Zahl der Knoten einer vollständigen Suche mit jedem blockierenden Container wächst. Bei drei Lagen braucht die Aufzählung im Median mit drei Stapeln 230 Knoten, mit fünf schon 12 693. Der Haken: Gemessen wird mit einem Knotenlimit, nicht mit Zeit, und bei vier Stapeln bricht sie in 10 von 40 Buchten am Limit ab.
Demo starten →Die Untergrenze macht die Suche klein: IDA* beim Umstauen
Verfolgen Sie, wie die iterative Vertiefung mit der Untergrenze den Suchbaum klein hält. Bei drei Stapeln und vier Lagen braucht Branch and Bound ohne Untergrenze im Median 384 Knoten, mit Untergrenze 51. Der Haken: Die Knotenzahl wächst je Einheit Lücke trotzdem um das 1,5- bis 3-Fache, und die Vertiefung selbst bringt im Median höchstens das Dreifache.
Demo starten →Gleiche Zustände: Zustandsmerken und Symmetriebruch beim Umstauen
Verfolgen Sie, wie oft eine Suche beim Umstauen auf denselben Zustand trifft. Bei 4 × 3 hat der Baum im Median 39 414 Knoten, aber nur 88 verschiedene Zustände. Der Haken: Bei IDA* mit Untergrenze bringt das Merken im Median höchstens das 1,33-Fache, der Gewinn steckt im Schwanz, und Stapelvertauschen hilft kaum.
Demo starten →Das ILP-Modell: wo bricht es ein?
Verfolgen Sie, wie sich das Umstauen als ganzzahliges Modell schreiben lässt und wo ein Löser daran scheitert. Die LP-Schranke ist bis 12 Container gut, doch bei 16 Containern beweist das Modell in 60 Sekunden nur 5 von 6 Buchten. Der Haken: Die Suche löst dieselben Buchten in Millisekunden, und die Zeiten sind Einzelmessungen.
Demo starten →Die Spaltenformulierung: Stapelgraph und Spaltengenerierung
Verfolgen Sie, wie die Spaltenformulierung über einen Stapelgraphen eine stärkere LP-Schranke gewinnt. Bei drei Stapeln und drei Lagen beweist schon der Wurzelknoten das Optimum in 39 von 40 Buchten dieser Stichprobe, das kompakte Modell in 31. Der Haken: Der Stapelgraph ist ab etwa 10 Containern größer als das kompakte Modell, und ein Verzweigen gibt es nicht.
Demo starten →Schärfere Untergrenzen: die Lücke schließen
Verfolgen Sie, wie viel der Lücke zwischen Untergrenze und Optimum schärfere Zählungen schließen. Bei zwei Lagen trifft die Zählung ohne sicheren Stapel in 2 019 von 2 020 geprüften Buchten das Optimum, bei drei Lagen schließt sie rund 60 Prozent. Der Haken: Erschöpfend gerechnet gibt es auch bei zwei Lagen Ausnahmen, und mehr Schärfe spart Knoten, aber meist keine Zeit.
Demo starten →Viele Stapel: wird die Untergrenze scharf?
Verfolgen Sie, ob die einfache Untergrenze bei wachsender Stapelzahl das Optimum trifft. Bei drei Lagen schrumpft die relative Lücke von 3 Prozent bei 24 Stapeln auf 1,4 Prozent bei 48. Der Haken: Die absolute Lücke bleibt bei fünf Lagen bei rund 8 Hüben.
Demo starten →Vorsortieren: sortieren statt abrufen
Verfolgen Sie, ob sich Vorsortieren vor dem Abruf lohnt. Das Optimum des Vorsortierens ist 1,2- bis 1,7-fach so groß wie das des Umstauens beim Abruf. Der Haken: Mit weniger freien Plätzen als eine Stapelhöhe ist vieles unlösbar, bei drei Stapeln und drei Lagen mit zwei freien Plätzen sind nur 23 von 60 Buchten lösbar, und die ruhige Zeit davor ist nicht gemessen.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Einlagern: was ist eine Abfahrtsschätzung wert?
Verfolgen Sie, wie viel eine Schätzung der Abfahrtszeit beim Einlagern bringt. Bei einem Schätzfehler von 20 Prozent der Containerzahl schließt sie 54 bis 63 Prozent der Lücke zwischen dem niedrigsten Stapel und vollem Wissen. Der Haken: Ab einem Fehler von 2 ist kein Vorteil mehr nachweisbar, und das Rauschen ist hier unabhängig je Container, echte Fehler sind oft systematisch.
Demo starten →Unbekannte Abrufreihenfolge: was ist eine Vorschau wert?
Verfolgen Sie, was es kostet, wenn nur Gruppen von Abrufen bekannt sind und nicht die genaue Reihenfolge. In der Zelle mit vier Stapeln und vier Lagen braucht die Regel bei Gruppen aus 6 Nummern 13,11 statt 11,31 Hübe, mit Vorschau auf zwei Abrufe 11,89. Der Haken: Gemessen sind nur kleine Zellen mit gleichverteilter Reihenfolge innerhalb der Gruppen.
Demo starten →Gelernter Verzweiger: lernt die Suche, wohin zuerst?
Verfolgen Sie, ob ein gelernter Verzweiger die Suche beschleunigt. Die Regel wählt in 92 bis 99 Prozent der Zustände ein optimales Kind zuerst, das Orakel spart gegenüber ihr 4 bis 43 Prozent der Knoten. Der Haken: Der gelernte Verzweiger ist nicht besser als die Regel, und beim Beweis spart auch das Orakel nichts.
Demo starten →Verfahrenswahl: Regel, Suche oder Schranke?
Verfolgen Sie, welches Verfahren bei welcher Bucht funktioniert. Bei drei Lagen löst die exakte Suche bis 36 Container alle gemessenen Buchten, bei vier und fünf Lagen reicht sie nur bis etwa 24 beziehungsweise 20. Der Haken: Mit 40 Buchten je Zelle sind die Anteile grob, und gemessen sind nur volle Buchten.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle fünfzehn Stücke: Er fragt danach, ob eine Untergrenze oder die beste Planung gebraucht wird, wie die Suche aussehen soll und ob sich die Aufgabe ändert, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Der Baum ordnet nach der Frage, nicht nach Güte. Wo mehrere Stücke passen, hilft die Verfahrenswahl; ihre Grenzen gelten für volle Buchten bei Platz 2.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Konvexe und konische Optimierung
Wann ist ein Ergebnis beweisbar optimal, wie rechnet ein Löser mit Kegeln, und welcher Löser passt zu welcher Aufgabe? Sechzehn Stücke von der Lücke als Beweis bis zur Verfahrenswahl.
Anordnen: relaxieren und runden
Wie weit unter dem Besten liegt die beste Zahl, die man beweisen kann, und wie rundet man eine Lockerung zurück auf eine Anordnung? Fünfzehn Stücke von der Mini-Halle bis zur Verfahrenswahl.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Online-Algorithmen
Wie man entscheidet, bevor die Zukunft bekannt ist, und was die Garantie für den schlimmsten Fall im Betrieb kostet: sieben Stücke von Mieten oder Kaufen bis zu Vorhersagen.
Zielfunktionsdesign
Was ändert sich, wenn nur das Ziel wechselt? Vierzehn Stücke von der Wahl zwischen Summe und Maximum über Fairness und Ersatzziele bis zur Frage, wie man ein Ziel vor dem Einsatz testet.
Bestandspolitiken
Wie viel bestellen, wenn jede Periode zählt? Sieben Demos mit demselben Artikel: von der Rückwärtsrechnung über Fixkosten, Lieferzeit, Verderb und zwei Lager bis zur Frage, welche einfache Regel reicht.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.
SAT und Constraint Programming
Wie merkt sich ein Löser, warum eine Sackgasse eine war? Sechzehn Stücke vom Konfliktlernen über Beweise, Zähler und Symmetrie bis zu Mengen- und Maschinenschlüssen, lokaler Suche und der Wahl der Modellwelt.
Packen: Reihenfolge und Platzierungsregel
Wie packt man Pakete, Rechtecke und Quader in wenige Behälter, und wie nah am Besten liegt eine einfache Regel? Vierzehn Stücke von der Sortierung bis zur Verfahrenswahl.
Tourenbildung: eine Reihenfolge, optimal zerlegt
Wie bildet man Touren aus einer einzigen Reihenfolge aller Kunden, und wann schlagen Savings, Sweep oder Suche sie? Fünfzehn Demos von der Aufzählung bis zur Verfahrenswahl.
Ressourcenwege und Spaltenerzeugung
Wie findet man unter unüberschaubar vielen möglichen Touren die mit dem größten Nutzen, wenn jede Zeit- und Lastgrenzen einhalten muss? Dreizehn Demos vom Weg mit Grenze bis zur Wahl des Verfahrens.
Takt und Periodizität
Ein Fahrplan, der sich jede Stunde wiederholt: vier Stücke von den Zeitabständen über die Wartezeit der Umsteiger und die Kreisgleichungen bis zum Betriebstag.