Die Untergrenze beim Umstauen verständlich erklärt

In einer engen Parkgasse kann man ohne Planen sagen, wie viele Autos man mindestens wegfahren muss, damit jeder Gast sein Auto zur bekannten Zeit holen kann. Oft braucht man mehr, denn ein umgeparktes Auto steht am neuen Platz wieder im Weg. Die Seite zeigt, wie groß diese Lücke wird.

Zuletzt aktualisiert: 11. November 2026

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

Autos in einer engen Gasse

Stellen Sie sich einen Parkplatz mit mehreren schmalen Gassen vor. In jeder Gasse stehen die Autos hintereinander, und nur das vorderste kann herausfahren. Die Autos gehören Gästen, die nacheinander abgeholt werden. Die Reihenfolge steht fest und ist von Anfang an bekannt: Der Gast mit Nummer 1 kommt zuerst, dann Nummer 2 und so weiter.

Steht das Auto des nächsten Gastes weiter hinten, muss jedes Auto davor aus der Gasse. Draußen bleiben darf es nicht, es wird in eine andere Gasse gestellt. Jedes solche Umparken kostet Zeit. Gesucht ist ein Plan, der mit möglichst wenig Umparken auskommt.

Im Hafen stehen Container in Stapeln, und ein Kran greift nur den obersten. Es ist dasselbe Problem; diese Seite bleibt beim Parkplatz.

Was man ohne Planen sagen kann

Eine Mindestzahl lässt sich ohne jeden Plan ablesen. Gehen Sie jede Gasse durch und markieren Sie jedes Auto, das vor einem Auto mit früherer Nummer steht. Es versperrt diesem den Weg. Jedes markierte Auto muss mindestens einmal weg, sonst käme der Gast dahinter nicht hinaus. Die Zahl der markierten Autos ist darum die Mindestzahl (Fachwort: Untergrenze). Kein Plan kommt mit weniger Umparken aus.

Ein Auto ohne Markierung steht nur vor Autos, deren Gäste später kommen als sein eigener. Wer früher dran ist, steht also nicht hinter ihm. Darum muss es nicht angefasst werden. Die Zählung sagt nicht nur, wie viel mindestens zu tun ist, sondern auch, welche Autos überhaupt in Frage kommen.

Beispiel: Warum die Mindestzahl nicht reicht

Nehmen wir drei Gassen mit je zwei Autos. Die Ausfahrt ist vorn. Die Zahlen sind die Reihenfolge, in der die Gäste kommen:

• Gasse A: vorn die 4, dahinter die 1.
• Gasse B: vorn die 2, dahinter die 5.
• Gasse C: vorn die 3, dahinter die 6.

Zuerst kommt der Gast der 1, aber vor ihr steht die 4. Nur die 4 versperrt jemandem den Weg, die Mindestzahl ist also 1. Doch wohin mit der 4? Sie kann nur nach Gasse B oder C. Dort steht vorn die 2 oder die 3, und beide Gäste kommen vor dem der 4. Die 4 steht am neuen Platz also wieder im Weg. Kommt der Gast der 2 oder der 3 an die Reihe, muss sie noch einmal weg.

Ein Umparken reicht deshalb nicht, nötig sind 2. Das ist die Lücke: Die Zählung sieht nur, wer am Anfang im Weg steht, nicht, wer nach dem Umparken im Weg steht. Dasselbe Auto muss dann mehrmals umgeparkt werden.

Wie gerechnet wurde

Die Zahlen stammen aus einem Versuch am Computer. Ein Programm zum Ausprobieren im Browser, die Demo, erzeugt zufällige Parkplätze mit drei bis fünf Gassen und zwei bis vier Autos je Gasse. Die Reihenfolge der Gäste wird ausgelost. Für jede Größe rechnet sie 100 solche Plätze durch. Umgeparkt wird nur, was vor dem gesuchten Auto steht.

Für jeden Platz ermittelt sie auch die wirklich kleinste Zahl an Umparkvorgängen (Fachwort: Optimum). Dazu probiert der Rechner die Möglichkeiten systematisch durch, bei so kleinen Plätzen geht das. Der Abstand zwischen Untergrenze und Optimum ist die Lücke.

Wann die Zählung reicht und wann nicht

Bei vier Gassen mit je zwei Autos stimmt die Untergrenze in 70 von 100 Plätzen mit dem Optimum überein. Bei je drei Autos sind es nur noch 20 von 100, bei je vier nur 4 von 100. Je mehr Autos hintereinander stehen, desto öfter steht ein umgeparktes Auto wieder im Weg.

In der Demo gilt Ähnliches für den Füllgrad: Je voller der Platz, desto seltener stimmt die Zählung.

Wozu die Zählung trotzdem gut ist

Braucht ein Plan genau so viele Umparkvorgänge wie die Untergrenze, weiß man sofort, dass er bestmöglich ist, ohne alle anderen Pläne zu prüfen. Das spart Rechenarbeit.

In der Demo wurde eine Faustregel gemessen: das Auto, wenn möglich, dorthin stellen, wo es niemanden blockiert. Auf Plätzen mit gleich vielen Autos je Gasse traf sie die Untergrenze immer dann, wenn überhaupt ein Plan sie traf. Das ist ein Messergebnis, kein Beweis.

Häufige Missverständnisse

• „Die Mindestzahl ist die Zahl, die man braucht.“ Sie ist nur eine Untergrenze und kann zu niedrig sein, weil sie nicht sieht, wo umgeparkte Autos wieder im Weg stehen.
• „Wer mehr als die Mindestzahl braucht, hat schlecht geplant.“ Nicht unbedingt. In der Demo braucht schon der bestmögliche Plan bei drei oder mehr Autos je Gasse in den meisten Fällen mehr als die Untergrenze.
• „Ein einmal umgeparktes Auto hat es hinter sich.“ Es kann am neuen Platz wieder vor einem früheren Gast stehen und noch einmal bewegt werden.

Woran Sie das im Alltag erkennen

• Im Kleiderschrank liegt das gesuchte Hemd unter drei anderen. Sie legen sie auf einen Nachbarstapel, und dort liegen sie auf dem Pullover, den Sie morgen brauchen.
• Im Kofferraum oder im Lieferwagen steht vorn, was Sie erst am Ende brauchen. Wer nur zählt, was im Weg steht, übersieht, was beim Wegräumen neu im Weg landet.

Wie ernst sind die Zahlen zu nehmen?

Die Plätze sind klein und zufällig erzeugt. Die Reihenfolge der Gäste ist hier von Anfang an bekannt, in der Praxis oft nicht. Umgeparkt wird nur auf andere Gassen innerhalb des Platzes, und gezählt wird nur, wie oft umgesetzt wird. Wege des Krans und Zeit zählen nicht mit. Die Zahlen zeigen Größenordnungen und keine Messung an einem echten Terminal oder Lager.

Was Sie mitnehmen

• Fragen Sie bei einer Mindestzahl, was sie nicht sieht. Hier ist es das Auto, das nach dem Umparken wieder im Weg steht.
• Je mehr Autos hintereinander stehen und je voller der Platz, desto größer kann der Abstand zwischen Untergrenze und echter Zahl sein.

Zu dieser Seite gehört die Demo. Sie 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 Umstauen in einer Bucht (Block Relocation, Variante restricted) auf zufällig erzeugten Buchten und eine einfache Untergrenze für die Zahl der Hübe, nicht echte Terminaldaten.

• Bucht: \(s\) Stapel der Höchsthöhe \(H\) = Lagen + Platz (Platz 1 bis 4, Standard 2). Anfangs steht auf jedem Stapel dieselbe Zahl von Containern (Lagen). Die Abrufnummern \(1,\dots,N\) sind zufällig verteilt; 1 wird zuerst abgerufen, und die ganze Reihenfolge ist bekannt.
• Hub: Er setzt den obersten Container eines Stapels auf einen anderen Stapel mit Platz. Restricted: Es werden nur Container über dem gesuchten bewegt. Die nächste Nummer wird entnommen, sobald sie oben liegt.
• Blockierend: Ein Container ist blockierend, wenn im selben Stapel unter ihm ein Container mit kleinerer Nummer liegt. Die Untergrenze ist die Zahl der blockierenden Container.
• Optimum: exakte Suche mit iterativer Vertiefung über das Hub-Budget, beginnend bei der Untergrenze, Zustände bis auf Vertauschen der Stapel gemerkt. Die Suche läuft ohne Zeitgrenze, jedes Optimum ist bewiesen. Die optimale Folge wird aus den gemerkten Zuständen rekonstruiert.
• Engste Passung: eine einfache Regel für den Zielstapel eines Blockers: unter den Stapeln, auf denen er nichts blockiert, der mit dem kleinsten frühesten Abruf; ein leerer Stapel zuletzt; gibt es keinen solchen, der Stapel mit dem größten frühesten Abruf.
• Zwei Familien von Buchten: Volle Buchten mit gleich hohen Stapeln (Hauptbucht, Lagenkurve, Platz) und Zufallsbuchten mit ungleich hohen Stapeln (Füllgradkurve): 4 Stapel, Höchsthöhe 5 und 6, jeder Container auf einen zufällig gewählten Stapel mit Platz, höchstens (Stapelzahl minus 1) mal Höchsthöhe Container, damit die Container über einem Ziel immer einen Ausweichplatz finden. Der Füllgrad ist die Zahl der Container geteilt durch Stapelzahl mal Höchsthöhe.
• Stichprobe: Je Einstellung 100 feste Buchten (Bucht-Nummern 0 bis 99), erzeugt mit der Zufallsfolge von Python (random.shuffle). Alle Zahlen unten sind Messungen an diesen Buchten.

Die Formeln

Sei \(B\) die Menge der anfangs blockierenden Container. Die Untergrenze ist ihre Mächtigkeit:

\[L = \lvert B \rvert\]

Satz 1 (Gültigkeit): Jede Hubfolge, die die Bucht leert, hat mindestens \(L\) Hübe. Beweisidee: Der Container mit der kleineren Nummer unter einem blockierenden \(c\) wird vor \(c\) abgerufen. Er ist erst erreichbar, wenn \(c\) nicht mehr über ihm liegt, und \(c\) kann seinen Platz nur durch einen Hub verlassen. Jeder Blocker braucht also einen eigenen Hub.

Satz 2 (nur Blocker werden bewegt): Ein anfangs nicht blockierender Container wird nie bewegt. Beweisidee: Unter einem nicht blockierenden \(c\) liegen nur größere Nummern. Neue Container kommen nur oben auf einen Stapel, unter \(c\) ändert sich also nichts. Würde \(c\) bewegt, läge es über der nächsten abzurufenden Nummer, die kleiner als \(c\) ist und unter \(c\) liegt. Dann wäre \(c\) blockierend.

Folgerung (Zerlegung): Für jede Hubfolge gilt mit \(h_c \ge 1\) als Zahl der Hübe von \(c\)

\[\sum_{c \in B} h_c = L + \sum_{c \in B} (h_c - 1)\]

Die Summe links ist die Zahl der Hübe, die zweite Summe rechts die Zahl der Mehrfachhübe. Die Lücke \(\text{OPT} - L\) zwischen Optimum und Untergrenze ist daher die Zahl der Mehrfachhübe der optimalen Folge. Ein Mehrfachhub entsteht, wenn ein Blocker auf einem Stapel landet, auf dem er wieder blockiert. Die Untergrenze zählt jeden Blocker nur einmal und sieht das nicht.

Beweisquote: Hat eine Regel genau \(L\) Hübe, ist sie nach Satz 1 optimal, ohne dass gesucht werden muss. Dass die engste Passung die Untergrenze trifft, wenn das Optimum sie trifft, ist ein Messbefund, kein Satz.

Befunde

Die Zahlen sind Messungen an den festen Buchten 0 bis 99 je Einstellung, in der folgenden Tabelle volle Buchten mit Platz 2. Die letzte Spalte zählt die Buchten, in denen die engste Passung das Optimum verfehlt. In jeder Zeile ist die Zahl der Buchten, in denen die engste Passung durch die Untergrenze als optimal bewiesen ist, gleich der Zahl in der Spalte „Untergrenze = Optimum“. Die Differenz der Mittel ist die mittlere Lücke.

Stapel × Lagen	Optimum (Mittel)	Untergrenze (Mittel)	Lücke (Mittel / größte)	Untergrenze = Optimum (von 100)	engste Passung verfehlt (von 100)
3 × 2	1,74	1,41	0,33 / 1	67	2
4 × 2	2,25	1,95	0,30 / 1	70	0
5 × 2	2,83	2,51	0,32 / 1	68	0
3 × 3	5,05	3,53	1,52 / 4	19	13
4 × 3	5,81	4,53	1,28 / 4	20	9
5 × 3	6,94	5,69	1,25 / 4	25	5
3 × 4	8,92	5,68	3,24 / 8	1	39
4 × 4	10,44	7,44	3,00 / 7	4	48
5 × 4	12,52	9,49	3,03 / 7	3	40

Die engste Passung trifft das Optimum auch in Buchten, in denen die Untergrenze darunter liegt. Dort lässt sich ihre Optimalität nur mit Suche beweisen: bei 3 × 3 ist das in 68 von 100 Buchten so, bei 3 × 4 in 60 von 100.

Frage	Befund
Gilt die Untergrenze?	In allen 900 Buchten der neun Einstellungen liegt sie nicht über dem Optimum. In den optimalen Folgen und in den Folgen der engsten Passung wird kein anfangs nicht blockierender Container bewegt (Satz 2). Die Tests prüfen das zusätzlich an allen optimalen Folgen aller 120 Buchten mit 3 Stapeln × 2 Lagen.
Woraus besteht die Lücke?	Aus Mehrfachhüben (Folgerung). In der optimalen Folge kommen auf einen blockierenden Container im Mittel über die Buchten (Verhältnis Hübe zu Blockern je Bucht, gemittelt) 1,42 (3 × 3), 1,32 (4 × 3), 1,59 (3 × 4), 1,42 (4 × 4) und 1,32 Hübe (5 × 4). Rund 41, 30, 51, 40 und 31 % der Blocker werden mehr als einmal bewegt (Mittel der Anteile je Bucht). Diese Zahlen gehören zu der gewählten von mehreren optimalen Folgen; bei anderer Wahl liegen sie bis zu 1,4 Punkte darunter. Ein einzelner Container wird höchstens 3-mal bewegt (bei 3 × 4: 4-mal).
Wie hängt die Lücke von den Lagen ab?	Bei 4 Stapeln trifft die Untergrenze das Optimum bei 2, 3 und 4 Lagen in 70, 20 und 4 von 100 Buchten. Die mittlere Lücke wächst von 0,30 über 1,28 auf 3,00 Hübe, das Verhältnis Optimum zu Untergrenze von 1,16 über 1,32 auf 1,42. Bei 3 und 5 Stapeln fällt die Zahl der Treffer ebenfalls mit den Lagen.
Wie hängt sie vom Platz ab? (4 Stapel, Platz 1 / 2 / 3 / 4)	3 Lagen: Optimum 5,86 / 5,81 / 5,81 / 5,81, Lücke 1,33 / 1,28 / 1,28 / 1,28. 4 Lagen: Optimum 10,89 / 10,44 / 10,39 / 10,39, Lücke 3,45 / 3,00 / 2,95 / 2,95; die engste Passung ist optimal in 47 / 52 / 53 / 53 von 100 Buchten. Nur der knappste Platz (1) verändert das Bild, ab Platz 2 praktisch nichts.
Wie hängt sie vom Füllgrad ab? (Zufallsbuchten, 4 Stapel)	Höchsthöhe 5 mit 6 / 9 / 12 / 15 Containern (30, 45, 60, 75 %): Lücke 0,05 / 0,50 / 1,29 / 2,74, Untergrenze = Optimum in 95 / 61 / 25 / 4 von 100 Buchten. Höchsthöhe 6 mit 6 / 9 / 12 / 15 / 18 Containern (25, 38, 50, 62, 75 %): Lücke 0,05 / 0,51 / 1,28 / 2,61 / 4,55, Untergrenze = Optimum in 95 / 60 / 29 / 9 / 2. Alle Optima sind bewiesen.
Trifft die Regel, wenn die Untergrenze trifft? (Messbefund, kein Satz)	In den vollen Buchten ohne Ausnahme: in den 900 Buchten der neun Einstellungen, und in den Tests in allen 120 Buchten 3 × 2 und in 300 Buchten 3 × 3. In den Zufallsbuchten gibt es unter 900 Buchten eine Ausnahme (Höchsthöhe 5, 12 Container).
Der einzelne Blocker	3 Stapel × 2 Lagen mit den Stapeln (1, 4), (5, 2), (6, 3) von unten nach oben: Untergrenze 1, Optimum 2. Keine Hubfolge mit einem Hub leert die Bucht (die Tests zählen alle Folgen). Die kleinsten Nummern der drei Stapel sind 1, 2 und 3, auf jedem anderen Stapel liegt unten etwas Früheres als der Blocker 4.
Alle Buchten 3 × 2	Von 120 Buchten (bis auf Vertauschen der Stapel) haben (Untergrenze, Optimum) die Verteilung (0, 0) 15, (1, 1) 30, (1, 2) 15, (2, 2) 24, (2, 3) 20, (2, 4) 1, (3, 3) 7, (3, 4) 8. Untergrenze = Optimum in 76, Lücke 1 in 43, Lücke 2 in einer Bucht.

Was die Messung zeigt und wo ihre Grenzen liegen

Das zeigt die Messung:

• Die Zählung der blockierenden Container ist gegen eine Handrechnung an zwei Mini-Buchten und gegen eine eigene Zählung geprüft. Ein unabhängiger Prüfer spielt jede Spur der drei Regeln und der optimalen Folge nach. Untergrenze und Optimum ändern sich nicht beim Vertauschen der Stapel, die Untergrenze auch nicht beim ordnungserhaltenden Umnummerieren.
• Das Optimum ist gegen eine Breitensuche über alle Buchtzustände geprüft, und zwar auf kleinen Buchten:3 × 2 und 4 × 2 (Platz 2), 3 × 3 (Platz 1 und 2), 4 × 2 (Platz 4) und auf Zufallsbuchten. Satz 1, Satz 2 und die Zerlegung sind an jeder optimalen Hubfolge aller 120 Buchten 3 × 2 aufgezählt und geprüft.
• Die Breitensuche deckt nur die kleinen Fälle ab; für größere Buchten wie 4 × 4 gibt es keinen solchen unabhängigen Vergleich.

Das zeigt sie nicht:

• Restricted: Es werden nur Container über dem gesuchten bewegt. Wer auch andere bewegen darf, kann Hübe sparen. Die Untergrenze zählt dann weiter Mindestbewegungen, das Optimum kann aber kleiner werden. Das ist hier nicht gemessen.
• Bekannte Reihenfolge: Die ganze Abrufreihenfolge ist bekannt. Bei unbekannter Reihenfolge ist „blockierend“ nicht zu bestimmen.
• Zwei Familien, nicht vergleichbar belegt: Volle Buchten und Zufallsbuchten sind verschieden. Gleicher Füllgrad ergibt ähnliche Lücken (4 × 3 bei Platz 2 entspricht 60 % Füllgrad bei Höchsthöhe 5: 1,28 gegen 1,29), verglichen ist das aber nur an dieser Stelle.
• Kleiner Bereich: Gemessen sind nur 3 bis 5 Stapel und 2 bis 4 Lagen, die Füllgradkurve nur für 4 Stapel. Platz und Füllgrad sind nur bei den genannten Einstellungen gemessen.
• Der Messbefund „Untergrenze trifft ⇒ Regel trifft“ ist kein Satz. Ein Beweis liegt nicht vor, und in den Zufallsbuchten gibt es eine Ausnahme.
• Zufallsbuchten, nicht Terminal: Die Zahlen sind Größenordnungen aus 100 festen Buchten je Einstellung, keine Messung an einem echten Terminal oder Lager. Die Buchten hängen von der Zufallsfolge von Python ab. Die Tabellen geben Mittel und größte Lücke an, aber keine Streuungsmaße.
• Selbst hergeleitet: Die Untergrenze und die Zerlegung sind in der Demo selbst hergeleitet; ob sie in der Literatur unter einem Namen stehen, wurde nicht geprüft.

Erweiterungen und Verweise

Bewusst nicht gebaut sind der Beweis des Messbefunds, die Unrestricted-Variante, das Einlagern, eine unbekannte Abrufreihenfolge, Pre-Marshalling, lernbasierte Verfahren und größere Buchten. Wie das Optimum berechnet wird (Tiefensuche, IDA*, Symmetriebruch, ganzzahlige Modelle, Branch and Price), ist Thema späterer Teile der Reihe: Hier ist die Suche nur ein Maßstab. Dasselbe gilt für schärfere Untergrenzen, die Konflikte zwischen Stapeln berücksichtigen. Der einzelne Blocker ist ein erster Hinweis darauf. Nahe Fragen liegen in Nachbar-Demos:

• umstauen-regeln-demo: das erste Stück der Reihe. Es vergleicht drei Regeln für den Zielstapel mit dem bewiesenen Optimum und zeigt die Untergrenze nur als Zahl.

Quellen

• Quelltext, Messungen und Tests der Demo: github.com/sebastian-hanisch/untergrenze-umstauen-demo.
• Das Problem heißt in der Literatur Block Relocation Problem (auch Container Relocation Problem). Die Demo zitiert für die Untergrenze und die Zerlegung keine Veröffentlichung.

Alle Zahlen dieser Seite stammen aus den Messungen der Demo. Die Seite rechnet nichts selbst nach. Die Untergrenze und die Zerlegung sind in der Demo selbst hergeleitet; ob sie in der Literatur unter einem Namen stehen, wurde nicht geprüft.