Order Batching verständlich erklärt

Wer im Lager mehrere Bestellungen auf einer Tour einsammelt, spart Laufweg. Wie viel, hängt davon ab, welche Bestellungen man bündelt. Dieses Problem heißt Order Batching. Diese Seite erklärt es zuerst ohne Formeln und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

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

Eine Tour für mehrere Bestellungen

Im Lager holt ein Kommissionierer die Artikel zusammen, die Kundinnen und Kunden bestellt haben. Er läuft dazu die Regale ab, nimmt die Positionen einer Bestellung auf und bringt sie zur Packstation. Geht er für jede Bestellung einzeln los, läuft er viele ähnliche Wege mehrfach.

Beim Order Batching werden mehrere Bestellungen zu einem Batch (einem Bündel) zusammengefasst, den er in einer einzigen Tour abarbeitet. Begrenzt wird das durch eine Kapazität, etwa die Zahl der Fächer am Kommissionierwagen oder das Volumen, das hineinpasst. Das Greifen und Scannen der Artikel dauert immer gleich lang, denn jede Position wird genau einmal gepickt. Gespart wird nur Laufweg.

Warum ist das schwer?

Es sind zwei Entscheidungen, die zusammenhängen. Erstens: Welche Bestellungen kommen in denselben Batch? Zweitens: In welcher Reihenfolge läuft der Kommissionierer die Positionen eines Batches ab? Welche Zusammenstellung einen kurzen Weg erlaubt, hängt davon ab, wo die Artikel liegen.

Die erste Entscheidung gilt als besonders schwer. Sie ähnelt dem Verpacken von Gegenständen in möglichst wenige Behälter, und die Zahl der möglichen Aufteilungen wächst mit jeder Bestellung stark. Beide Entscheidungen zusammen exakt zu lösen ist bei realistischen Größen praktisch nicht mehr möglich. Die Demo verwendet deshalb Verfahren, die schnell eine gute, aber nicht beweisbar beste Lösung finden.

Wie geht die Demo vor?

Zuerst bilden zwei Verfahren eine Anfangsaufteilung. Das Seed-Verfahren (Seed heißt Keim) beginnt jeden Batch mit einer großen Bestellung und füllt ihn mit Bestellungen auf, deren Artikel in der Nähe liegen. Der Zonen-Sweep ordnet die Bestellungen nach ihrer Lage im Lager und bündelt benachbarte. Welches Verfahren besser abschneidet, hängt vom Szenario ab, deshalb zeigt die Demo beide.

Danach verbessert eine Suche die Anfangsaufteilung in kleinen Schritten: Sie verschiebt eine Bestellung in einen anderen Batch, tauscht zwei Bestellungen und verbessert die Reihenfolge der Stopps, solange der Weg kürzer wird. Zuteilung und Route werden dabei gemeinsam verbessert, nicht nacheinander. Am Ende steht ein Zustand, den kleine Schritte nicht mehr verbessern. Er muss nicht der beste überhaupt sein (ein sogenanntes lokales Optimum).

Um aus so einem Zustand herauszukommen, stört die Demo die Lösung gezielt: Sie verschiebt einige Bestellungen und optimiert erneut. Das wiederholt sie, solange ein Zeitbudget reicht, und behält die beste gefundene Lösung.

Was bringt welcher Schritt?

Den größten Teil der Verbesserung bringt die Suche nach der Anfangsaufteilung, vor allem das Umverteilen der Bestellungen zwischen den Batches. Das gezielte Stören mit Neustart bringt noch ein kleines Stück dazu. Weil die Suche fast jede vernünftige Anfangsaufteilung auf ein ähnliches Niveau hebt, spielt die Wahl des Startverfahrens nur noch eine kleine Rolle.

Viele Ideen, die vielversprechend klingen, haben in den Messungen der Demo nichts gebracht: Clustering-Verfahren aus dem maschinellen Lernen für die Anfangsaufteilung, Tabu Search, Simulated Annealing und weitere Verfahren zum Verlassen eines lokalen Optimums. In der Demo liegen die Artikel ziemlich gleichmäßig im Lager verteilt, echte Gruppen, die ein Clustering entdecken könnte, gibt es dann kaum. Übernommen wurde nur eine Idee aus der Forschung zu Entscheidungen unter Unsicherheit, mit der das Ziel einer verschobenen Bestellung gewählt wird.

Einzelne Fälle können vom Durchschnitt abweichen: Ein Verfahren, das im Mittel besser ist, kann in einem einzelnen Lager etwas schlechter ausfallen.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Modell: ein erzeugtes Lager mit parallelen Gängen und zwei Quergassen, erzeugte Bestellungen und immer nur eine Kapazitätsart zur Zeit. Wegekonflikte zwischen mehreren Kommissionierern kennt das Modell nicht, und es bewertet nur den Weg, nicht die Wartezeit der Bestellungen auf ihren Batch. Es zeigt, wie die Verfahren wirken, nicht wie viel Weg ein bestimmtes echtes Lager spart.

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 fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Gegeben: Bestellungen \(O\), jede mit einer Menge von Positionen \(P_o\) (\(I\) sind alle Lagerpositionen), eine Größe \(s_i \ge 0\) je Position (Positionen-Modus: \(s_i = 1\), Volumen-Modus: das tatsächliche Volumen), eine Batch-Kapazität \(Q\) und eine Distanzfunktion \(d(i, j)\) zwischen Lagerpositionen und zum Depot, abgeleitet aus dem Layout.
• Gesucht: eine Partition der Bestellungen in Batches \(B_1, \dots, B_k\), jede Bestellung in genau einem Batch, und je Batch eine Besuchsreihenfolge \(R_v\) seiner Positionen. Minimiert wird die gesamte Laufdistanz: je Batch der Weg vom Depot über die Positionen in der Reihenfolge \(R_v\) und zurück zum Depot.
• Layout: parallele Gänge zwischen vorderer und hinterer Quergasse (ein Block). Der Weg zwischen zwei Gängen führt über die kürzere der beiden Quergassen, die Packstation liegt vorne links. Das ist das Standardmodell der Kommissionier-Literatur.
• Kapazität: umschaltbar zwischen einer höchsten Zahl Positionen je Batch und einem höchsten Volumen je Batch, nie beides zugleich.
• Kennzahlen: Die reine Pickzeit ist für alle Strategien gleich, weil jede Position genau einmal gepickt wird; nur die Laufzeit unterscheidet sich. Aus der Distanz leitet die Demo Kommissionierzeit, Personalkosten und Durchsatz ab.

Die Formeln

Die Batch-Bildung ist eine Partitionierung unter einer Kapazitätsnebenbedingung, strukturell verwandt mit Bin Packing und NP-schwer (ohne bekanntes Verfahren, das jede Instanz in Polynomialzeit exakt löst). Die Items sind die Bestellungen, mit dem Gewicht der Summe ihrer Positionsgrößen. Die Kapazität gilt für jeden Batch \(v\):

\[\sum_{o \in B_v} \sum_{i \in P_o} s_i \leq Q\]

Die Größen aller Positionen aller Bestellungen im Batch \(B_v\) dürfen zusammen \(Q\) nicht überschreiten. Das Routing je Batch ist im Allgemeinen ein Traveling-Salesman-Problem; im Ein-Block-Layout gibt es einen polynomiellen exakten Algorithmus (Ratliff & Rosenthal 1983), den die Demo bewusst nicht nutzt. Sie verwendet Nearest-Neighbor mit 2-opt. Ein 2-opt-Zug kehrt ein Teilstück einer Route \(R\) um, es entsteht eine benachbarte Route \(R'\), und der Zug wird ausgeführt, wenn er die Batch-Distanz senkt:

\[\text{Kosten}(R') < \text{Kosten}(R)\]

Die Inter-Batch-Nachbarschaft verändert die Zuteilung selbst. Relocate verschiebt eine Bestellung \(o\) von Batch \(B_u\) nach \(B_v\), zulässig, wenn die Kapazität in \(B_v\) danach eingehalten wird:

\[\sum_{i \in P_o} s_i + \sum_{o' \in B_v} \sum_{i \in P_{o'}} s_i \leq Q\]

Swap tauscht je eine Bestellung zweier Batches und ist zulässig, wenn die Kapazität in beiden Batches eingehalten wird. Ein Zug wird ausgeführt, wenn er die Summe der beiden betroffenen Batch-Distanzen senkt. Bewertet wird per Cheapest-Insertion in die bestehende Route des Zielbatches statt per vollem Neu-Routing je Kandidat.

Das Verfahren

• Konstruktion: Greedy-Seed startet jeden Batch mit der größten noch unverteilten Bestellung und füllt ihn mit den Bestellungen, deren Positionen dem bisherigen Batch-Schwerpunkt am nächsten liegen. Zonen-Sweep sortiert die Bestellungen nach ihrem Gang-Schwerpunkt, startet einen Batch mit der nächsten unverteilten Bestellung dieser Sortierung und füllt ebenfalls mit den räumlich nächstgelegenen passenden Bestellungen.
• Verschachtelte Suche: Relocate und Swap zwischen Batches, verschachtelt mit 2-opt-Zügen auf den Einzelrouten. Eine Warteschlange „auffälliger“ Batches (Don't-Look-Bits) ersetzt den vollen Rescan je Iteration. Ein Batch gilt als fertig, wenn weder ein verbessernder Zuteilungszug noch ein verbessernder 2-opt-Zug gefunden wird. Das Ergebnis ist ein lokales Optimum der vereinigten Nachbarschaft ohne Garantie für das globale.
• Iterated Local Search: Nach dem lokalen Optimum stören einige zulässige Relocates die Lösung, das Ziel-Batch wählt UCB1 (Bandit-Strategie: Score aus bisheriger Erfolgsrate plus Unsicherheitsbonus für wenig ausprobierte Paare). Danach wird erneut optimiert, wiederholt bis zum Zeitbudget; die beste Lösung bleibt. Ein Neustart beginnt warm: unveränderte Batches behalten Route und Distanz.

Befunde

Alle Zahlen stammen aus den Messungen, die die README der Demo beschreibt. Sie gelten für die erzeugten Lager und Instanzen, die jede Zeile nennt, nicht für ein echtes Lager. Gemessen wird die gesamte Laufdistanz; „kürzer“ bezieht sich auf die jeweils genannte Vorstufe. Zeiten wurden auf einem Desktop-Entwicklungsrechner gemessen.

Frage	Befund
Abstand zum Optimum (kleine Instanzen)	12 Instanzen mit 7 Bestellungen und Kapazität 6, Optimum per Vollenumeration bestimmt: Greedy-Seed mit 2-opt liegt im Schnitt 8,7 % darüber, in Einzelfällen bis 25 %, nur 3 von 12 Instanzen treffen das Optimum. Mit dem frühen Prototyp der Inter-Batch-Lokalsuche sinkt der Abstand auf 0,12 %, 11 von 12 Instanzen treffen das Optimum.
Beitrag der Verfahrensstufen	Stufen-Benchmark mit 4 Szenarien (Standard 24 Bestellungen bei Kapazität 15, Mittel 40/15, knappe Kapazität 30/10, Worst Case 80/60), 3 Zufalls-Seeds und beiden Strategien, 24 Läufe je Stufe. Inter-Batch-Suche gegenüber 2-opt je Batch: 5 bis 20 % kürzere Distanz (Mittel 13,8 %). Verschachtelte Suche gegenüber reiner Konstruktion ohne 2-opt: 10 bis 25 % (Mittel 18,0 %). Iterated Local Search zusätzlich: 0 bis 6 % (Mittel 1,8 %).
Zonen-Sweep gegen Greedy-Seed	200 Zufallsinstanzen über 8 Szenarien, reine Batch-Distanz nach 2-opt: Die erste Fassung von Zonen-Sweep lag im Schnitt 3,9 % hinter Greedy-Seed, bei knapper Kapazität 9,7 % (Greedy gewann dort 24 von 25 Läufen). Nach der Nachbesserung (Auffüllen mit der nächstgelegenen passenden Bestellung) sind es 0,8 % im Schnitt, in mehreren Szenarien liegt Zonen-Sweep vorn.
Clustering für die Anfangsaufteilung	Je 15 Instanzen über 4 Szenarien, danach dieselbe Inter-Batch-Suche und 2-opt-Politur: Hierarchisches Clustering liegt innerhalb von ±1 bis 3 % von Greedy-Seed, balanciertes Graph-Partitioning innerhalb von ±1 %, kein konsistenter Gewinner. Bei HDBSCAN galten im Schnitt 15 bis 20 % der Bestellungen als Rauschen. Keine der drei Methoden wurde übernommen.
Metaheuristik-Varianten	14 Varianten geprüft (unter anderem Tabu Search, ALNS, Simulated Annealing), 13 schlagen die Konfiguration nicht. Übernommen wurde UCB1 für die Wahl des Ziel-Batches: Mittel über 3 unabhängige Instanzen je Größe +0,01 % (24 Bestellungen), +0,50 % (30) und +0,19 % (80 Bestellungen, Kapazität 60) gegenüber der Zufallswahl; positiv heißt kürzere Distanz.
Rechenzeit	Don't-Look-Bits: 1,2 bis 3,2fach schneller, der größte Gewinn bei 80 Bestellungen (1,32s → 0,41s), die Qualität schwankt dabei zwischen −2,0 % und +1,8 % je Szenario. Warmstart der Neustarts von Iterated Local Search: 1,6fach (24 Bestellungen), 2,1fach (30) und 1,7fach (80) schneller, bei durchweg besseren Lösungen.

Grenzen

• Stark stilisiert: synthetisches Ein-Block-Lager, erzeugte Bestellungen, immer nur eine Kapazitätsart zur Zeit. Keine Mehrfach-Kommissionierer-Koordination: Jeder Batch wird unabhängig bewertet, als gäbe es keine Wegekonflikte. Keine Zeitfenster oder Kommissionierwellen, bewertet wird nur die Distanz.
• Heuristik ohne Garantie: Das Ergebnis ist ein lokales Optimum der Nachbarschaft. Das echte Optimum ist nur auf kleinen Instanzen per Vollenumeration bekannt.
• Einzelinstanzen können täuschen: Bei kleinen und mittleren Instanzen beruhten frühere Prozentzahlen auf einer einzelnen Instanz und liegen im Rauschen; belastbar sind die Mittel über mehrere Instanzen. Auf dem Standardszenario war die verschachtelte Suche auf der einen Instanz leicht schlechter: 899m statt vorher 883m.
• Rechenzeit hängt von der Hardware ab: Die Zeiten stammen von einem Desktop-Entwicklungsrechner. Auf der Streamlit Community Cloud dürften sie spürbar länger ausfallen; das Zeitbudget der Iterated Local Search wurde für schwächere Hardware nicht nachgemessen.

Quellen

• Elsayed, E. A. (1981): Algorithms for Optimal Material Handling in Automatic Warehousing Systems, International Journal of Production Research 19(5): früheste in der README genannte Arbeit zum Order Batching.
• Gademann, N., van de Velde, S. (2005): das Modell mit parallelen Gängen, dem die Demo folgt, und die Einordnung der Batch-Bildung als schwer.
• Ratliff, H. D., Rosenthal, A. S. (1983): Order-Picking in a Rectangular Warehouse, Operations Research 31(3): exakte Routenplanung im Ein-Block-Lager.
• Roodbergen, K. J., de Koster, R. (2001): Routing-Verfahren im Lager (S-Shape, Return, Largest-Gap) und Lagerlayout als Standardmodell.
• Won, J., Olafsson, S. (2005): Joint order batching and order picking in warehouse operations, International Journal of Production Research 43(7): Batchbildung anhand der tatsächlichen Routenqualität.
• Bentley, J. L. (1992): Fast Algorithms for Geometric Traveling Salesman Problems (Don't-Look-Bits).
• Lourenço, H. R., Martin, O. C., Stützle, T. (2003): Iterated Local Search, in: Handbook of Metaheuristics.
• Auer, P., Cesa-Bianchi, N., Fischer, P. (2002): Finite-time Analysis of the Multiarmed Bandit Problem (UCB1).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/order-batch-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus der README der Demo.