Vorsortieren von Containern verständlich erklärt

Stapel vorher so umzuschichten, dass später nichts mehr im Weg liegt, klingt vernünftig. Wenn man die Reihenfolge kennt, in der abgeholt wird, hat das aber zwei Haken. Die Seite erklärt sie erst im Alltagsbild und dann mit Messwerten aus kleinen Rechenfällen.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Das Bild: Kartons im Keller

Stellen Sie sich einen Keller vor, in dem Umzugskartons in drei Stapeln stehen. An einen Karton kommen Sie nur heran, wenn nichts auf ihm liegt. Sie wissen genau, in welcher Reihenfolge Sie die Kartons brauchen: erst den ersten, dann den zweiten, und so weiter. Liegt der gesuchte Karton nicht oben, setzen Sie die Kartons darüber auf einen anderen Stapel. Jedes Absetzen ist ein Handgriff.

Auf einem Containerlager ist es dasselbe, nur größer. Die Container stehen in Stapeln und werden in einer bekannten Reihenfolge abgeholt. Liegt der gesuchte nicht oben, müssen die darüber zuerst umgestapelt werden. Ein Stapel hat nur eine begrenzte Zahl von Stellplätzen übereinander; ein Stellplatz ist ein Platz für einen Container.

Daraus ergibt sich eine Frage. Soll man erst beim Abholen umstapeln, oder schichtet man die Stapel vorher so um, dass beim Abholen nichts mehr im Weg liegt? Das ist, als würden Sie am Vorabend die Kartons so umschichten, dass die, die Sie morgen zuerst brauchen, oben liegen. Das Umschichten vorab heißt Vorsortieren (Fachwort: Pre-Marshalling).

Warum Vorsortieren so sicher klingt

Sortiert heißt hier: In jedem Stapel liegt oben, was zuerst gebraucht wird, und unten, was zuletzt gebraucht wird. Dann ist beim Abholen nichts im Weg, und es fällt kein Handgriff mehr an. Das klingt sicher: einmal umschichten, danach Ruhe.

Einen Karton, der über einem früher gebrauchten liegt, nennen wir Störer. Ein Störer muss mindestens einmal angefasst werden, denn solange er liegt, kommt niemand an den Karton darunter. Die Zahl der Störer ist also eine einfache Mindestzahl für die Handgriffe (Fachwort: Untergrenze).

Wie hier gerechnet wird

Die Zahlen stammen aus einem vereinfachten Rechenbild. Ein Programm zum Ausprobieren im Browser, die Demo, erzeugt kleine Lager mit zufällig verteilten Containern. Jedes solche Lager ist eine Beispiel-Anordnung. Das Programm probiert für jede Beispiel-Anordnung alle möglichen Handgriffe systematisch durch. So findet es die kleinste Zahl von Handgriffen, mit der sortiert ist, oder es stellt fest, dass es gar nicht geht. Dasselbe rechnet es für das Umstapeln erst beim Abholen und vergleicht beides. Gezählt werden nur Handgriffe, keine Zeit.

Erster Haken: Es braucht freien Platz

Zum Umschichten muss man Kartons zwischenlagern. Ist kein Stellplatz frei, bleibt jeder Karton, wo er ist. Aber auch mit etwas Platz kann man sich festfahren. Dazu gibt es in der Demo ein kleines Beispiel: drei Stapel, auf jedem höchstens drei Kartons, acht Kartons stehen darin, ein einziger Stellplatz ist frei. Man kann immer nur den obersten Karton eines Stapels anfassen und ihn nur dorthin setzen, wo gerade der eine freie Stellplatz ist. Der Spielraum ist so klein, dass der Rechner alle erreichbaren Anordnungen durchprobieren konnte: In keiner ist sortiert, in allen liegen noch vier Störer.

Die Zählung der Störer hätte hier „mindestens vier Handgriffe“ gesagt, ohne zu merken, dass es gar nicht geht.

Wie viel Platz braucht man? Bei drei Stapeln mit höchstens drei Kartons und zwei freien Stellplätzen ließen sich von 60 durchgerechneten Beispiel-Anordnungen nur 23 sortieren. Gab es so viele freie Stellplätze, wie ein Stapel hoch ist, ließen sich alle 180 durchgerechneten Beispiel-Anordnungen sortieren. Das gilt für die drei Größen, die der Rechner bis zum Ende durchgerechnet hat. Es wurde an diesen Beispielen ausgezählt und nicht allgemein bewiesen.

Zweiter Haken: Es kostet mehr Handgriffe

Beim Umstapeln erst beim Abholen bewegt man nur, was gerade im Weg liegt. Beim Vorsortieren muss dagegen eine ganz geordnete Anordnung entstehen. In den durchgerechneten Beispiel-Anordnungen brauchte das im Mittel mehr Handgriffe. Nur in höchstens zwei von 60 Beispiel-Anordnungen je Größe war Vorsortieren billiger.

Die Arbeit verschwindet also nicht. Sie wandert vom Moment des Abholens in die Zeit davor. Das hilft nur, wenn es diese ruhige Zeit gibt. Ob es sie gibt, hat die Demo nicht gemessen.

Auch die Zählung der Störer täuscht bei wenig Platz. In der Demo war der wirkliche Aufwand bei wenigen freien Stellplätzen etwa zwei- bis dreimal so groß wie diese Mindestzahl, bei vielen freien Stellplätzen dagegen nahe daran.

Was hilft?

Drei Fragen vor dem Umschichten. Erstens: Ist genug Platz zum Ausweichen da, mindestens so viele freie Stellplätze, wie ein Stapel hoch ist? Zweitens: Wie viele Handgriffe kostet das Umschichten, verglichen mit dem Umstapeln erst beim Abholen? Drittens: Gibt es die ruhige Zeit vorher wirklich? Fallen die Antworten günstig aus, kann sich Vorsortieren lohnen. In den durchgerechneten Beispiel-Anordnungen brauchte es im Mittel mehr Handgriffe.

Häufige Missverständnisse

• „Wenn sortiert ist, habe ich Arbeit gespart.“ Danach fällt beim Abholen zwar kein Handgriff mehr an. Das Umschichten selbst kostete in der Demo aber im Mittel mehr Handgriffe als das Umstapeln beim Abholen.
• „Die Zahl der Störer sagt mir, wie aufwendig es wird.“ Sie nennt nur eine Mindestzahl. Ob es überhaupt geht, verrät sie nicht, wie das Beispiel mit dem einen freien Stellplatz zeigt.
• „Mit genug freien Stellplätzen geht es sicher.“ In den drei Größen, die der Rechner bis zum Ende durchgerechnet hat, stimmte das, aber nur als Auszählung. Bei größeren Lagern blieben einzelne Beispiel-Anordnungen offen, weil der Rechner in der vorgegebenen Rechenmenge nicht weiterkam. Als unmöglich bewiesen sind sie nicht.

Woran Sie das im Alltag erkennen

• Sie wollen am Vorabend Kartons umschichten, aber im Keller ist so wenig Platz, dass Sie nichts verschieben können.
• Sie wissen, in welcher Reihenfolge Sie Bücher aus dem Regal brauchen, und ordnen das Regal am Samstag danach. Dafür brauchen Sie womöglich mehr Handgriffe, als wenn Sie am Sonntag nur die Bücher vor dem gesuchten beiseiteschieben.
• Das Umschichten lohnt sich vor allem, wenn Sie am Samstag Zeit haben, die Sie sonst nicht nutzen.

Wie ernst ist das Rechenbild zu nehmen?

Das Rechenbild füllt kleine Lager zufällig, gibt jedem Container eine eigene Nummer, setzt eine im Voraus bekannte Abholreihenfolge voraus und zählt nur Handgriffe; Kranzeit, Fahrwege und Gewicht fehlen in der Messung. Echte Lager sind oft schon teilweise geordnet, darum zeigen die Zahlen Größenordnungen für kleine Fälle und keine Messung an echten Lagern.

Was Sie mitnehmen

• Fragen Sie vor dem Umschichten, ob genug Platz zum Ausweichen da ist.
• Rechnen Sie die Handgriffe des Umschichtens mit, nicht nur die, die danach wegfallen.
• Fragen Sie, ob die ruhige Zeit vorher wirklich frei ist, sonst verschiebt das Umschichten die Arbeit nur.

Die Demo erreichen Sie über den ersten Knopf unten. Zum Verstehen brauchen Sie sie nicht. Der zweite Knopf führt zum zweiten Teil für Fachleute.

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.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt das Vorsortieren (Pre-Marshalling) einer einzelnen Bucht, also eines Blocks nebeneinanderstehender Stapel, auf zufällig erzeugten kleinen Buchten und vergleicht es mit dem Umlagern beim Abruf (Relocation Problem, hier die Variante restricted).

• Bucht: \(S\) Stapel der Höchsthöhe \(H\) und \(N = S\,H - F\) Container mit den Nummern \(1,\dots,N\) (kleiner heißt früher abzurufen), \(F\) freie Plätze. Jeder Container liegt auf einem zufällig gewählten Stapel, der noch Platz hat; die Stapel sind darum ungleich hoch. Die Zelle \(S \times H\) bezeichnet Stapelzahl mal Höchsthöhe.
• Ziel: Eine Bucht ist sortiert, wenn in jedem Stapel die Nummern von unten nach oben fallen, also kein Blocker (Container über einem früher abzurufenden) existiert.
• Hub: Der oberste Container eines Stapels wandert auf einen anderen Stapel mit freiem Platz; Kosten 1. Erlaubt ist jeder solche Hub.
• Untergrenze: die Zahl der Blocker, denn jeder muss mindestens einmal bewegt werden.
• Exakte Suche: Breitensuche über Zustände bis auf Vertauschen der Stapel. Das erste sortierte Ziel ist optimal; erschöpft die Suche den Zustandsraum ohne Ziel, ist die Bucht bewiesen unlösbar. Live gilt ein Zustandslimit von 150 000 (bei Erreichen steht das Ergebnis auf „nicht entschieden“). Vorberechnet wurde die Lösbarkeit mit Zustandslimit 600 000 für 60 Buchten je Zelle; das Limit wurde dabei in keiner Zelle erreicht. Größere Zellen rechnet IDA* mit der Untergrenze und Zustandsmerken (Knotenlimit 300 000, 40 Buchten je Zelle); es findet das Optimum, wenn die Bucht lösbar ist.
• Vergleich: das Optimum des restricted Relocation derselben Bucht; bei jedem Abruf werden nur die Container über dem Ziel bewegt (Knotenlimit 50 000 in der Live-Rechnung).
• Messgrößen: Zählungen (Zustände, Knoten, Hübe) an festen Zufallsbuchten, keine Zeitmessung.

Die Formeln

Gegeben sind \(S\) Stapel der Höchsthöhe \(H\) und \(N\) Container mit den Nummern \(1, \dots, N\) (kleiner = früher abzurufen). Die Zahl der freien Plätze ist

\[F = S\,H - N\]

Ein Container \(c\) ist ein Blocker, wenn im selben Stapel unter ihm ein Container mit kleinerer Nummer liegt. Ein Blocker muss mindestens einmal bewegt werden: Der kleinere Container unter ihm kann sich erst bewegen, wenn \(c\) weg ist, und ein sortierter Zustand hat keinen Blocker. Für die kleinste Hubzahl \(\text{OPT}\) bis zu einer sortierten Bucht gilt also

\[\text{OPT} \ge \text{LB1} := |\text{Blocker}|\]

Die Breitensuche vom Anfangszustand über alle Hübe findet in Tiefe \(d\) den ersten sortierten Zustand; dann ist \(d = \text{OPT}\). Erschöpft sie den erreichbaren Zustandsraum ohne sortierten Zustand, ist die Bucht unlösbar. Mit \(F = 0\) ist kein Hub möglich; mit \(F = 1\) kann nur auf den einen Stapel mit Platz gesetzt werden. So entsteht der kleine Zustandsraum der Hand-Bucht (1, 4, 7), (5, 2, 6), (3, 8) mit Höchsthöhe 3 und einem freien Platz: nur sechs erreichbare Zustände (Stapel ohne Reihenfolge gezählt), in allen sechs bleiben vier Blocker. Die Untergrenze hätte 4 gesagt, ohne zu merken, dass es nicht geht.

Ist \(F\) kleiner als \(H\), war in den Messungen ein großer Teil der Buchten unlösbar; ab \(F = H\) waren in den drei vollständig durchgerechneten Zellen alle lösbar. Das ist eine Messung, kein Satz.

Zum Vergleich dient das Optimum des restricted Relocation derselben Bucht. Das Vorsortieren muss alle Blocker bewegen und dabei eine ganze sortierte Anordnung herstellen; das Umlagern bewegt nur, was beim Abruf im Weg liegt. Verglichen werden die Mittel der kleinsten Hubzahl über die Buchten, die beide Verfahren lösen. Ebenso ist das Verhältnis \(\text{OPT} / \text{LB1}\) das Verhältnis der Mittelwerte über die gelösten Buchten.

Befunde

Alle Zahlen sind Zählungen an festen Zufallsbuchten, keine Zeiten. In der Breitensuche sind es 60 Buchten je Zelle, in den IDA*-Zellen 40. Optimum und Untergrenze sind Mittel über die gelösten Buchten. Zuerst die Lösbarkeit: Zahl der Buchten von je 60, die sich sortieren ließen; der Rest ist bewiesen unlösbar.

Zelle	1 frei	2 frei	3 frei	4 frei	5 frei	6 frei
3 × 3	3	23	60	60	60	60
4 × 3	1	19	60	60	60	60
3 × 4	0	1	16	60	60	60

Die Lösbarkeit springt: Unterhalb von \(F = H\) (3 × 3: 3, 4 × 3: 3, 3 × 4: 4) ist ein großer Teil der Buchten unlösbar, ab \(F = H\) sind alle 180 Buchten der drei Zellen lösbar. Weitere Befunde:

Frage	Befund
Wann geht das Sortieren?	Nicht bei zu wenig Platz. Mit weniger freien Plätzen als eine Stapelhöhe sind die meisten Buchten unlösbar (bewiesen: der erreichbare Zustandsraum enthält keine sortierte Bucht), zum Beispiel 3 × 3 mit 2 freien Plätzen: 23 von 60 lösbar, mit 1 freien Platz 3 von 60. Ab einer Stapelhöhe freier Plätze waren alle 180 Buchten der drei durchgerechneten Zellen lösbar. In den größeren Zellen mit IDA* sind bei genug Platz einzelne Buchten ungelöst; sie sind nur am Limit.
Das kleinste Beispiel?	Die Hand-Bucht (1, 4, 7), (5, 2, 6), (3, 8) mit Höchsthöhe 3 und einem freien Platz: sechs erreichbare Zustände, in allen sechs vier Blocker.
Wie schwach ist die Untergrenze?	Bei wenigen freien Plätzen liegt das Optimum beim Zwei- bis Dreifachen: 4 × 3 mit 2 freien Plätzen 5,63 gegen 2,26 (Verhältnis 2,5), 3 × 4 mit 3 freien Plätzen 8 gegen 2,50 (Verhältnis 3,2). Bei vielen freien Plätzen liegt sie nahe: 4 × 3 mit 6 freien Plätzen 1,40 gegen 1,10. Das Verhältnis in 4 × 3 sinkt mit mehr Platz: 2,5 bei 2, 1,8 bei 3, 1,6 bei 4, 1,3 bei 6 freien Plätzen. Bei \(F = H\) trifft die Untergrenze das Optimum in 18 von 60 (3 × 3), 10 von 60 (4 × 3) und 4 von 60 (3 × 4) Buchten.
Und größere Zellen?	Mit IDA* gerechnet bis 6 × 3 und 5 × 4: Optimum / Untergrenze liegt zwischen 1,4 (5 × 3 mit 4 und 5 freien Plätzen) und 2,4 (3 × 5 mit 5 freien Plätzen). In 5 × 4 (4 und 5 frei) und 6 × 3 (3 frei) löst IDA* in der Knotengrenze nur 14, 21 und 34 von 40 Buchten. Die Verhältnisse sind nur über die gelösten Buchten gemittelt; die ungelösten sind eher schwerer.

Vorsortieren gegen Umlagern beim Abruf, auf denselben Buchten, die beide Verfahren lösen (60 Buchten je Zeile, Relocation restricted, Mittel der kleinsten Hubzahl). Das Verhältnis ist Pre-Marshalling durch Umlagern:

Zelle, freie Plätze	Pre-Marshalling	Umlagern beim Abruf	Untergrenze	Verhältnis	Vorsortieren billiger / gleich / teurer
3 × 3, 3 frei	3,38	2,05	1,65	1,7	0 / 22 / 38
3 × 3, 5 frei	0,95	0,82	0,77	1,2	0 / 52 / 8
4 × 3, 3 frei	5,03	3,25	2,78	1,5	1 / 10 / 49
4 × 3, 6 frei	1,40	1,17	1,10	1,2	1 / 46 / 13
3 × 4, 4 frei	7,12	4,27	3,02	1,7	2 / 7 / 51

Über alle gerechneten Zellen mit 3 bis 6 freien Plätzen ist das Optimum des Vorsortierens im Mittel 1,2- bis 1,7-fach so groß wie das des Umlagerns beim Abruf, und nur in 0 bis 2 von 60 Buchten kleiner. Vorsortieren spart in diesen Zellen im Mittel keine Hübe, es verschiebt sie vom Abruf in die Zeit davor, wenn es diese Ruhezeit gibt; im Modell ist sie nicht gemessen, und die Hubzahl bildet sie nicht ab.

Grenzen: was die Messung zeigt und was nicht

Das zeigt die Messung: Zählungen an festen Zufallsbuchten, die sich nachrechnen lassen. Optimum und Lösbarkeit der Breitensuche wurden in über 300 Buchten aus zehn Zellen gegen eine zweite Breitensuche über beschriftete Zustände (ohne Zusammenfassen der Stapel) geprüft, das Relocation in 150 Buchten gegen eine eigene vollständige Rekursion, IDA* gegen die Breitensuche. „Bewiesen unlösbar“ heißt: Der erreichbare Zustandsraum wurde erschöpft und enthält keine sortierte Bucht.

Das zeigt sie nicht:

• Messung, kein Satz: „Ab einer Stapelhöhe freier Plätze lösbar“ ist an drei Zellen gemessen (je 60 Buchten). Größere Zellen sind nur mit IDA* gerechnet; ungelöste Buchten sind dort am Limit, nicht bewiesen unlösbar.
• Zufallsbuchten: Jeder Container landet auf einem zufälligen Stapel mit Platz, die Stapel sind ungleich hoch. Echte Buchten sind oft teilweise sortiert.
• Eine Prioritätsordnung ohne Gruppen: Alle Nummern sind verschieden. Mit Gruppen gleicher Priorität, wie sie in der Literatur üblich sind, dürfte das Sortieren leichter sein (nicht gemessen).
• Nur die Hubzahl: Kranzeit, Fahrwege und Zeitfenster zählen nicht. Die ruhige Zeit vor dem Abruf ist nicht gemessen; ob das Vorsortieren dort billig ist, sagt die Hubzahl nicht.
• Relocation restricted: Im Vergleich dürfen nur Container über dem Ziel bewegt werden; im unrestricted Relocation wäre das Umlagern nicht teurer.
• Schwache Untergrenze heißt: die Blocker-Zählung ist schwach. Stärkere Untergrenzen für das Pre-Marshalling (Bortfeldt und Forster, Tierney u. a.) sind nicht gebaut; die Aussage gilt nur für die einfache Zählung der Blocker.

Quellen

• Quelltext, vorberechnete Messreihe und Tests der Demo: github.com/sebastian-hanisch/vorsortieren-umstauen-demo.
• Zum Pre-Marshalling: Bortfeldt und Forster; Tierney u. a. (Stand der Technik, in der README der Demo aus dem Gedächtnis genannt und nicht gelesen).
• Zum Branch and Price für das Pre-Marshalling: van Brink und van der Zwaan, in einer früheren Demo der Umstauen-Reihe gelesen, hier nur als Verweis.

Die Literaturangaben sind aus der README der Demo übernommen, ohne Titel und Jahr, und hier weder nachgeschlagen noch gelesen. Die Zahlen sind eigene Messungen der Demo an Zufallsbuchten; die Literatur wurde nicht nachgebaut.