Die Tor-Zuordnung verständlich erklärt

Am Flughafen müssen Umsteiger von Gate zu Gate laufen. Liegen die richtigen Gates nebeneinander, sind die Wege kurz. Dieselbe Frage gibt es in einer Halle, in der Ware umgeladen wird. Die Seite zeigt, welche Regeln gute Anordnungen finden und wo die schlaue Regel verliert.

Zuletzt aktualisiert: 11. November 2026

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

Wer soll neben wem stehen?

Stellen Sie sich einen großen Flughafen vor. Viele Fluggäste steigen um und laufen von Gate zu Gate. Zwischen manchen Gates sind es täglich viele, zwischen anderen nur wenige. Liegen zwei stark genutzte Gates nebeneinander, sind die Wege kurz. Am entgegengesetzten Ende laufen alle weit.

Dieselbe Frage stellt sich in einer Umschlaghalle (englisch Cross-Dock). Dort fahren Lastwagen an Tore und laden Ware aus. Stapler bringen sie zu einem anderen Tor, wo sie in den nächsten Lastwagen kommt. Gelagert wird nicht. Jedes Tor bedient eine Relation. Das ist eine feste Verbindung zwischen Herkunft und Ziel, etwa alle Sendungen eines Lieferpartners.

Zwischen zwei Relationen fährt der Stapler am Tag eine bestimmte Zahl von Fahrten. Die Aufgabe lautet: Welche Relation bekommt welches Tor? Es zählt die Summe des Tages, also Weglänge mal Zahl der Fahrten.

Nehmen wir als Beispiel zwei Relationen mit 100 Fahrten am Tag. Liegen ihre Tore 10 Meter auseinander, sind das 1.000 Meter Fahrt am Tag. Bei 30 Metern sind es 3.000 Meter.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Ganz unten in diesem Teil gibt es zwei Knöpfe: Der erste öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie es nicht.

Warum man nicht einfach alles ausprobiert

Man könnte jede mögliche Anordnung durchrechnen und die beste nehmen. Das geht nur bei wenigen Toren, denn jedes zusätzliche Tor vervielfacht die Zahl der Anordnungen. In der Messung dauerte die einfachste Aufzählung bei sieben Toren Bruchteile einer Sekunde. Bei zehn Toren dauerte sie knapp eine Minute, bei elf Toren wären es mehrere Minuten.

Schwer ist die Aufgabe, weil jede Entscheidung die anderen berührt. Wer ein Tor besetzt, nimmt es allen anderen weg. Darum braucht man Regeln, die schnell eine gute Anordnung finden, ohne zu beweisen, dass sie die beste ist.

Drei Regeln im Vergleich

Die Demo vergleicht drei Regeln am selben Maß: dem durchschnittlichen Weg je Fahrt.

• Ankunftsreihenfolge: Die erste Relation bekommt das erste Tor, die zweite das zweite und so weiter. Sie übersieht, wie viel Ware zwischen den Relationen wandert.
• Aufbauregel (in der Demo „fluss-optimiert“): Sie setzt die Relationen nacheinander. Zuerst kommt das Paar mit den meisten Fahrten auf zwei nahe Tore. Jede weitere Relation bekommt das freie Tor mit der kürzesten Gesamtstrecke zu ihren schon platzierten Partnern, jeweils mal Zahl der Fahrten. Sie übersieht, was später kommt, und nimmt nichts zurück.
• Tauschen (Fachwort 2-opt): Sie startet mit dem Ergebnis der Aufbauregel. Sie tauscht die Relationen zweier Tore, wenn der Gesamtweg kürzer wird, und wiederholt das, bis kein Tausch mehr hilft. Sie übersieht, was nur mehrere Tausche zugleich erreichen.

Die schlaue Regel, die verlor

Denken Sie an eine Tischordnung bei einer Feier. Sie setzen die Gäste nacheinander. Der nächste soll neben seinem besten Freund sitzen. Drei weitere Freunde sitzen aber schon an anderen Tischen. Wer nur auf den einen schaut, setzt den neuen Gast womöglich weit weg von den drei anderen.

So ging es beim Bauen der Demo. Die erste Fassung der Aufbauregel schaute bei jeder neuen Relation nur auf einen Partner. In einer von 40 geprüften Hallen war sie schlechter als die Ankunftsreihenfolge, um knapp ein Prozent. Heute zählt sie die Wege zu allen schon platzierten Partnern zusammen. Das beseitigte solche Verluste nicht ganz, wie der nächste Absatz zeigt.

Auch die verbesserte Aufbauregel gewinnt nicht jedes Mal. Nehmen wir 40 Zufallshallen mit 16 Toren und zwei besonders umschlagstarken Relationen. Dort lag der Weg im Mittel knapp sieben Prozent unter dem der Ankunftsreihenfolge. In einer Halle verlor die Regel, um gut ein Prozent. Der Grund: Die Regel entscheidet Schritt für Schritt. Eine frühe Wahl, die gut aussah, kann später fehlen.

Wie oft das geschieht, hängt von der Hallengröße ab. Eine Nachrechnung für diese Seite mit je 100 Hallen zeigt: Je nach Torzahl verlor die Aufbauregel in etwa jeder zehnten Halle bis zu zwei von fünf Hallen. Bei 28 Toren verlor sie in keiner. Einen klaren Zusammenhang mit der Hallengröße gibt es nicht.

Was das Tauschen bringt

Der Tauschschritt macht den größten Unterschied. In denselben 40 Hallen lag der Weg mit ihm im Mittel gut dreizehn Prozent unter dem der Ankunftsreihenfolge. Das ist doppelt so viel wie bei der Aufbauregel allein.

Der Tausch holt nach, was die schrittweise Wahl verpasst hat: Eine Relation, die früh am falschen Ort landete, darf wechseln. Er schadet nie, denn getauscht wird nur, wenn der Weg danach kürzer ist.

Mehr Aufwand brachte wenig

Die Entwicklung der Demo prüfte vier weitere Ideen. Erstens: die fertige Anordnung durchmischen wie einen Kartenstapel und neu tauschen. Zweitens: drei Relationen reihum tauschen. Drittens: zwischendurch auch Tausche zulassen, die den Weg verlängern, um aus einer Sackgasse zu kommen. Viertens: beim Aufbau mehrere Kandidaten zugleich durchspielen und den besten Start wählen.

Zusätzlich zum reinen Tauschen brachte in der Messung keine der ersten drei im Mittel mehr als gut ein Prozent. Der bessere Start lag bei 20 Toren im Mittel gut zehn Prozent unter dem Weg der einfachen Aufbauregel. Nach dem Tauschen blieb davon weniger als ein Prozent. Das ist ein Hinweis, dass nach dem Tauschen nicht mehr viel zu holen ist, aber kein Beweis.

Häufige Missverständnisse

• „Wenn kein Tausch mehr hilft, ist die Anordnung die beste.“ Das stimmt nicht. Denken Sie an einen Wanderer im Nebel, der immer bergab geht. Er endet in einer Mulde, doch hinter dem nächsten Hügel kann ein tieferes Tal liegen. Genauso kann eine bessere Anordnung nur mit mehreren Tauschen zugleich erreichbar sein. Den Abstand zum Besten hat die Demo nicht gemessen, bei größeren Hallen, weil das Durchrechnen zu lange dauert. Eine Nachrechnung für diese Seite: Bei sechs bis acht Toren lag das Tauschen im Mittel unter einem halben Prozent über dem Besten, bei neun Toren rund ein Prozent. Das Beste traf es seltener, je mehr Tore es gab. Bei neun Toren gelang es in höchstens einer von drei Hallen.
• „Kürzere Wege sparen sofort so viele Euro.“ Die Demo misst nur Meter und rechnet bewusst nicht in Euro um. Was ein Meter kostet, hängt von Personal, Schichtmodell und Staplertyp ab.

Woran Sie das im Alltag erkennen

• In Ihrer Küche laufen Sie ständig zwischen Herd und Kühlschrank, weil die Dinge dort gelandet sind, wo gerade Platz war.
• Sie räumen ein Regal ein und geben jedem Ding nacheinander den besten freien Platz. Der letzte Platz bleibt oft ungünstig. Das ist die Aufbauregel.

Wie ernst ist das Rechenbild zu nehmen?

Das Rechenbild nimmt zufällig erzeugte Hallen, Luftlinie zwischen den Toren statt echter Fahrwege und kennt weder Uhrzeiten noch Torarten. Es zeigt, wie sich die drei Regeln zueinander verhalten. Wie Sie Ihre Halle planen, zeigt es nicht.

Was Sie mitnehmen

• Rechnen Sie bei jeder Anordnung Zahl der Fahrten mal Weglänge, nicht nur den Weg.
• Prüfen Sie eine neue Regel an mehreren Beispielen. Ein einzelner Gewinn oder Verlust sagt wenig.
• Fragen Sie bei einer großen Halle zuerst, was Paare tauschen schon bringt. In den Beispielhallen lohnte Aufwendigeres kaum.

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

Gegeben sind \(n\) Relationen (feste Verbindungen zwischen Quelle und Ziel, etwa Partner oder Zielgebiete) und \(n\) Tore einer Umschlaghalle. Jede Relation bekommt genau ein Tor, jedes Tor genau eine Relation. Zwischen zwei Relationen \(i\) und \(j\) gibt es ein Umschlagvolumen \(f_{ij}\) in Bewegungen pro Tag, zwischen zwei Toren \(k\) und \(l\) eine Entfernung \(d_{kl}\). Gesucht ist die Zuordnung mit der kleinsten flussgewichteten Gesamtentfernung. Das ist das Dock Door Assignment Problem, ein Spezialfall des quadratischen Zuordnungsproblems (QAP).

• Halle: Die Tore stehen gleichmäßig verteilt auf zwei gegenüberliegenden Wänden, die eine Reihe mit der Hälfte der Tore (bei ungerader Zahl eines mehr), die andere mit dem Rest. Einstellbar sind die Zahl der Tore (4 bis 40, Voreinstellung 16), die Hallenlänge entlang der Reihen (30 bis 300 m, Voreinstellung 100 m) und die Hallentiefe, also der Abstand der Reihen (10 bis 100 m, Voreinstellung 30 m). Die Entfernung \(d_{kl}\) ist die Luftlinie (euklidisch). Gänge, Hindernisse und Fahrtrichtung gibt es nicht.
• Fluss: Die Matrix \(f\) ist symmetrisch, ihre Diagonale null, die Werte sind auf ganze Bewegungen gerundet. Die Grundwerte werden gleichverteilt zwischen 1 und 10 gezogen und dann symmetrisiert (Mittel aus Wert und Spiegelwert, also dreiecksverteilt). Eine Konzentration \(c\) (0 bis 1, Voreinstellung 0,5) hebt jedes Paar, an dem mindestens eine von \(h\) zufällig gewählten Vorzugsrelationen beteiligt ist (\(h\) von 1 bis 6, Voreinstellung 2), mit dem Faktor \(1 + 6c\) an, also höchstens auf das Siebenfache. Der Faktor wirkt je Paar genau einmal, auch wenn beide Relationen Vorzugsrelationen sind.
• Zielgröße: Die flussgewichtete Gesamtentfernung ist die Summe über alle Paare \(i < j\) von \(f_{ij}\) mal der Entfernung der beiden Tore (Meter mal Bewegungen pro Tag). Die durchschnittliche Entfernung je Bewegung teilt sie durch die Summe aller \(f_{ij}\) mit \(i < j\). Diese Summe hängt nicht von der Zuordnung ab, beide Kennzahlen ändern sich also um denselben Prozentsatz (Rechnung dieser Seite). Alle Prozentwerte unten werden so gebildet: Je Instanz wird die Verkürzung der durchschnittlichen Entfernung je Bewegung gegenüber der Ankunftsreihenfolge in Prozent von deren Wert berechnet; die Tabelle nennt den Mittelwert dieser Instanzwerte. Eine Nachrechnung dieser Seite reproduziert die Zahlen der Dokumentation auf diese Weise.

Die Formeln

Gesucht ist eine Permutation \(\pi \in S_n\), die jeder Relation \(i\) das Tor \(\pi(i)\) zuweist. Die Zielfunktion als Doppelsumme über alle geordneten Paare lautet (die Demo bewertet nur Paare \(i < j\), also die Hälfte; die beste Zuordnung ändert das nicht):

\[\min_{\pi \in S_n} \; \sum_{i=1}^{n} \sum_{j=1}^{n} f_{ij} \cdot d_{\pi(i)\pi(j)}\]

Gleichwertig als binäres quadratisches Programm mit \(x_{ik} = 1\), wenn Relation \(i\) an Tor \(k\) steht, sonst 0:

\[\min \; \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n} f_{ij}\, d_{kl}\, x_{ik}\, x_{jl}\]

Nebenbedingungen sind \(\sum_k x_{ik} = 1\) für jede Relation \(i\), \(\sum_i x_{ik} = 1\) für jedes Tor \(k\) und \(x_{ik} \in \{0,1\}\). Quadratisch heißt: Das Produkt \(x_{ik}\,x_{jl}\) koppelt zwei Entscheidungen im selben Term. Hinge der Preis jeder Kombination aus Relation und Tor nur von dieser Kombination ab, läge ein lineares Zuordnungsproblem vor, das die Ungarische Methode in polynomialer Zeit exakt löst. Das QAP ist NP-schwer. Für beliebige Fluss- und Entfernungsmatrizen ist nach Sahni und Gonzalez auch keine Näherung mit konstanter Gütegarantie in polynomialer Zeit möglich, sofern P ≠ NP; für die Hallengeometrie dieser Demo (Luftlinie auf zwei Reihen) folgt daraus keine solche Aussage.

Die drei Verfahren

Die Demo speichert eine Zuordnung als Liste „Tor → Relation“, also als Umkehrung \(\rho = \pi^{-1}\); \(\rho(a)\) ist die Relation an Tor \(a\).

• Ankunftsreihenfolge (Vergleichsmaßstab): Relation \(i\) erhält Tor \(i\), unabhängig vom Fluss. Sie steht für eine ungeplante, gewachsene Zuteilung.
• Fluss-optimierte Konstruktion: Die Relationspaare werden nach absteigendem \(f_{ij}\) abgearbeitet. Sei \(P\) die Menge der bereits fixierten Paare (Relation, Tor) und \(D_{\text{frei}}\) die Menge der freien Tore. Ist von einem Paar keine Relation platziert, kommt es auf das nächstgelegene freie Torpaar (Formel unten). Ist genau eine Relation \(j\) noch frei, wählt man das freie Tor \(k\), das \(\sum_{(m,l) \in P} f_{jm}\, d_{kl}\) minimiert, also die flussgewichtete Entfernung zu allen schon platzierten Relationen \(m\) mit ihren Toren \(l\) und nicht nur zum Partner des gerade bearbeiteten Paars. Sind beide Relationen platziert, geschieht nichts. Paare ohne Fluss werden übersprungen (in den erzeugten Instanzen kommen sie nicht vor, weil alle Flüsse positiv sind); Gleichstände beim Startpaar entscheiden die Torindizes.
• 2-opt-Verbesserung (Paartausch): Ausgehend von der Konstruktion wird wiederholt der beste verbessernde Tausch der Relationen zweier Tore \(a\) und \(b\) ausgeführt (steilster Abstieg), bis kein verbessernder Tausch mehr existiert. Die Kostenänderung eines Tauschs ist \(\Delta(a,b) = \sum_{k \neq a,b} \big(f_{\rho(b),\rho(k)} - f_{\rho(a),\rho(k)}\big)\big(d_{a,k} - d_{b,k}\big)\), bezogen auf die Halbsumme über \(i < j\); \(\Delta < 0\) heißt Verbesserung. Sie kostet \(O(n)\) je Tauschkandidat, die Prüfung aller \(\binom{n}{2}\) Kandidaten also \(O(n^3)\) je Durchlauf.

Start eines neuen Relationspaars: Beide Relationen kommen auf das freie Torpaar mit der kleinsten Entfernung zueinander,

\[(k^*, l^*) = \arg\min_{k,l \,\in\, D_{\text{frei}},\; k \neq l} d_{kl}\]

ohne Rücksicht auf die Lage schon platzierter Relationen (aus dem Verfahrensablauf abgeleitet, nicht gemessen). Das 2-opt-Verfahren verschlechtert sein Startergebnis nie: Ein Tausch wird nur ausgeführt, wenn die Kostenänderung unter einer kleinen negativen Toleranz liegt, die Kosten fallen also in jedem Schritt strikt. Da es nur endlich viele Zuordnungen gibt, endet das Verfahren in einem lokalen Optimum bezüglich aller Paartausche; eine feste Obergrenze der Durchläufe dient nur als Schutz vor Gleitkomma-Zyklen. Ein globales Optimum folgt daraus nicht.

Die Ankunftsreihenfolge als Zufallsvergleich

Rechnung dieser Seite, keine Messung der Demo. Voraussetzung: Die Instanzen sind so erzeugt, dass die Nummern der Relationen nichts über den Fluss verraten (gleichverteilte Grundwerte, zufällig gewählte Vorzugsrelationen). Dann hat die Flussmatrix bei jeder Umnummerierung der Relationen dieselbe Verteilung, und die feste Zuordnung „Relation \(i\) an Tor \(i\)“ ist verteilungsgleich einer zufälligen Permutation.

Für eine zufällige Permutation ist die erwartete Entfernung zweier verschiedener Relationen gleich der mittleren Entfernung \(\bar d\) aller Torpaare. Die erwartete durchschnittliche Entfernung je Bewegung der Ankunftsreihenfolge ist also \(\bar d\), unabhängig von Konzentration und Vorzugsrelationen. Eine Nachrechnung mit zweitausend Hallen (16 Tore, Voreinstellungen) stimmt damit bis auf Zufallsschwankung überein. Folge: Die Prozentwerte der Befunde messen den Abstand zu einer Zufallszuordnung, nicht zum Optimum. Die Aussage gilt im Erwartungswert über die Zufallsinstanzen, nicht für eine einzelne Halle.

Warum die Konstruktion verlieren kann und das Tauschen nicht

Die Konstruktion nutzt bei jeder Entscheidung nur den Zwischenstand und nimmt nichts zurück. Eine frühe Wahl, die lokal günstig ist, kann Tore besetzen, die später für Relationen mit hohem Fluss fehlen. Eine Optimalitätsgarantie gibt es nicht, im Einzelfall kann sie hinter die Ankunftsreihenfolge fallen. Eine erste Fassung, die nur den Partner des gerade bearbeiteten Paars berücksichtigte, verlor in einer Messung in einer Instanz gegen die Ankunftsreihenfolge; die Änderung auf alle platzierten Partner beseitigte den Effekt nicht (siehe Befunde). Ob der Start neuer Paare ohne Rücksicht auf platzierte Relationen die gemessenen Verluste erklärt, ist offen.

Das Tauschen hat eine lokale Garantie (Abschnitt oben) und kann die Konstruktion deshalb nur gleich lassen oder verbessern. Es sieht nur Zuordnungen, die ein einziger Tausch erreicht.

Befunde

Die Zahlen stammen aus der Dokumentation der Demo. Die Prozentwerte sind Verkürzungen der durchschnittlichen Entfernung je Bewegung gegenüber der Ankunftsreihenfolge, außer bei der Beam-Suche nach dem Tauschen, bei Iterated Local Search, 3-opt und Tabu-Suche: Dort bedeutet „zusätzlich“ die Verbesserung gegenüber dem reinen 2-opt; ob in Prozent der 2-opt-Kosten oder in Prozentpunkten, sagt die Dokumentation nicht. Sie nennt keine Streuungsmaße. Kurz gefasst: Keine der geprüften Erweiterungen brachte über das reine 2-opt hinaus im Mittel mehr als etwa 1,1 %.

Frage	Befund und Voraussetzung
Wie viel kürzer ist der Weg der Konstruktion?	Im Mittel 6,7 % kürzer (16 Tore, Halle 100 m mal 30 m, Konzentration 0,5, 2 Vorzugsrelationen, 40 Zufallsinstanzen). In einer der 40 Instanzen war er 1,3 % länger.
Und eine frühere Fassung, die nur einen Partner beachtete?	Im Mittel 8,6 % kürzer über 40 Zufallsinstanzen (16 Tore, Standardkonfiguration; Einmalmessung, mit dem heutigen Code nicht nachstellbar), in einer Instanz 0,8 % länger. Die 8,6 % und die 6,7 % stammen aus verschiedenen Messungen und sind kein sauberer Vorher-Nachher-Vergleich.
Was bringt das Tauschen, gegenüber der Ankunftsreihenfolge?	Mit anschließendem 2-opt im Mittel 13,4 % kürzer (gleiche 40 Instanzen). Nachrechnung dieser Seite: Der Standardfehler dieser Mittel (6,7 % und 13,4 %) beträgt weniger als ein Zehntel beziehungsweise weniger als ein Zwanzigstel des Mittelwerts.
Was bringt das Tauschen, gegenüber der Konstruktion allein?	Für Instanzen mit 20 Toren nennt die Dokumentation 13 bis 17 % unter der Konstruktion allein und in Summe oft 15 bis 20 % unter der Ankunftsreihenfolge, ohne Zufallszahlen, Einstellungen und Instanzzahl anzugeben.
Wie lange dauert das Tauschen?	Bei 40 Toren unter einer Sekunde je vollständigem Lauf (0,82 s im Benchmark), bei 16 bis 28 Toren 20 bis 140 ms.
Bringt ein besserer Start (Beam-Suche: statt der einen besten Teilzuordnung werden die besten 8 parallel weitergeführt, je Schritt um bis zu 3 Kandidaten erweitert)?	Vor dem Tauschen gegenüber der einfachen Konstruktion 5,7 % (16 Tore), 10,7 % (20), 1,8 % (28) und 0,8 % (40) kürzer, in 4 bis 42 ms. Nach angeschlossenem Tauschen auf beiden Startpunkten nur noch 0,14 % und 0,05 % sowie −0,04 % und −0,05 %; die Dokumentation ordnet −0,04 % und −0,05 % den Toren 28 und 40 zu, die ersten beiden Werte stehen ohne Torzahl (die Zuordnung zu 16 und 20 Toren ist aus der Reihenfolge abgeleitet). Einzelwerte lagen zwischen −0,45 % und +0,6 %. Instanzzahl nicht genannt. Nicht in die Demo übernommen.
Bringt Iterated Local Search (2-opt bis zum lokalen Optimum, dann einige zufällige Tausche als Störung, erneut 2-opt, über mehrere Neustarts das beste Ergebnis behalten)?	Zusätzlich zum reinen 2-opt: schwache Störung (2 bis 3 Tausche) 0,1 bis 0,2 %, auch mit 20 Neustarts; starke Störung (n/2 Tausche) rund 0,6 % bei 40 Toren für rund 9 s zusätzliche Laufzeit; bestes Verhältnis (mittlere Störung, 8 bis 12 Neustarts) 0,2 bis 1,1 %. Getestet bei 16 bis 40 Toren, Instanzzahl nicht genannt.
Bringt eine 3-opt-Nachbarschaft (Dreiertausch im Kreis, kombiniert mit 2-opt)?	Zusätzlich zum reinen 2-opt: Bei 20 Toren im Mittel 0,34 % (10 von 20 Testinstanzen verbessert, Spanne 0 bis 1,8 %). Bei 40 Toren 0 bis 0,01 % für 1,9 bis 3,4 s zusätzliche Laufzeit; das Tauschen allein braucht weniger als 1 s.
Bringt Tabu-Suche (Taillards Robust-Tabu-Search: je Iteration der beste nicht verbotene Tausch, auch verschlechternd; eine Tabu-Liste verbietet das sofortige Rückgängigmachen, eine Aspirationsregel erlaubt Ausnahmen bei neuer Bestleistung)?	Zusätzlich zum reinen 2-opt: Bei 20 Toren nach Abstimmung von Tabu-Länge (3 bis 40) und Iterationszahl (100 bis 500) ein Plateau bei 1,0 bis 1,1 %, 9 bis 10 von 10 Instanzen verbessert. Bei 40 Toren mit Standardparametern 0 bis 0,14 % in 2,8 bis 2,9 s.

Exaktes Lösen, gemessene Laufzeit je Instanz (identische Ergebnisse beider Verfahren):

Tore	Vollaufzählung aller Permutationen	Backtracking mit Abbruch
7	0,04 s	0,02 s
8	0,38 s	0,25 s
9	4,24 s	1,30 s
10	52,6 s	18,1 s

Das Backtracking baut die Zuordnung relationsweise auf und bricht einen Zweig ab, sobald seine fixierten Kosten das bisher beste Ergebnis erreichen; da Flüsse und Entfernungen nicht negativ sind, sind auch fehlende Kostenbeiträge nie negativ; bei Gleichstand wird abgebrochen, das kostet höchstens gleichwertige Lösungen. Das Optimum geht dabei nicht verloren. Beide Verfahren wachsen faktoriell; bei 11 Toren wären es laut Dokumentation mehrere Minuten.

Grenzen und was die Messung zeigt

• Instanzklasse: Die Befunde gelten für zwei gegenüberliegende Torreihen, Luftlinie, einen gleichverteilt erzeugten, symmetrischen Fluss mit wenigen Vorzugsrelationen und jeweils eine Relation je Tor. Echte Flussdaten, Fahrwege, Torarten, Zeitfenster und Fahrtrichtungen gibt es nicht. Entfernungen statt Euro sind Absicht: Die Kostenwirkung hängt von Personal, Schichtmodell und Flurförderzeug ab.
• Mittel über wenige Instanzen: Die Zahlen der Dokumentation sind Mittelwerte in je einer Einstellung: über 40 Instanzen bei 6,7 % und 13,4 %, über 20 bei 3-opt und über 10 bei Tabu-Suche; für die übrigen Zahlen nennt die Dokumentation keine Instanzzahl. Streuungsmaße fehlen. Dass die Beam-Suche nach dem Tauschen nicht mehr von Rauschen unterscheidbar ist, belegt die Dokumentation mit Einzelwerten zwischen −0,45 % und +0,6 %.
• Die Konstruktion verliert je nach Torzahl unterschiedlich oft: Nachrechnung dieser Seite, nicht Teil der Demo (Voreinstellungen außer der Torzahl, je hundert Zufallshallen, zwei Stichproben mit verschiedenen Zufallszahlen, Angaben als Spanne über beide): Der Anteil der Hallen, in denen die Konstruktion gegen die Ankunftsreihenfolge verlor, lag bei 16 Toren bei acht bis elf von hundert, bei 20 Toren zwischen gut einem Viertel und knapp einem Drittel, bei vierundzwanzig Toren zwischen gut einem Viertel und gut zwei Fünfteln, bei 28 Toren bei null. Ein Trend „größere Halle, weniger Verluste“ besteht nicht. Der mittlere Vorsprung war bei 20 und vierundzwanzig Toren klein, weniger als halb so groß wie bei 16 und 28 Toren; warum, ist nicht untersucht. Auch bei kleinen Hallen mit acht und zwölf Toren verlor die Konstruktion in einem Zehntel bis knapp einem Drittel der Hallen. Die Demo-Hilfe vermutet, dass der Vorteil der Konstruktion mit der Konzentration wächst. Die Dokumentation misst das nicht; die Nachrechnung zeigte ihn bei 8, 12, 16 und 28 Toren steigend, bei 20 Toren ungefähr gleichbleibend.
• „Das Tauschen liegt nah am Optimum“ ist eine Vermutung, keine Messung: Sie stützt sich darauf, dass vier Erweiterungen jeweils höchstens gut ein Prozent zusätzlich brachten. Das Plateau kann auch bedeuten, dass diese Verfahren allesamt in der Nähe der 2-opt-Lösung suchen (Deutung dieser Seite). Ein direkter Vergleich der 2-opt-Lösung mit dem Optimum fehlt in der Dokumentation; exaktes Lösen reicht dort nur bis etwa 10 Tore. Ein Korrektheitstest vergleicht die drei Verfahren auf Hallen mit höchstens sechs Toren mit der vollständigen Aufzählung (gültige Zuordnung, Kosten nie unter dem Optimum, 2-opt nie schlechter als der Start und tauschoptimal); er misst keinen Abstand.
• Nachrechnung dieser Seite zum Abstand vom Optimum (Voreinstellungen außer der Torzahl; bei sechs bis acht Toren je hundert Zufallshallen, bei neun Toren dreimal dreißig Hallen mit verschiedenen Zufallszahlen): Das 2-opt-Ergebnis lag bei sechs bis acht Toren im Mittel unter einem halben Prozent über dem Optimum und traf es bei sechs Toren in gut vier von fünf Hallen. Bei neun Toren lag der Abstand je nach Stichprobe zwischen knapp unter und gut einem Prozent, und das Optimum wurde in fünf bis neun von dreißig Hallen getroffen. Der Trefferanteil sinkt mit der Torzahl und ist nicht auf 16 und mehr Tore übertragbar.
• Die Aussagen über das QAP (NP-Schwere, fehlende Näherung mit konstanter Gütegarantie) gelten für allgemeine Instanzen. Welche Güte die Verfahren in der Hallengeometrie dieser Demo allgemein erreichen, folgt daraus nicht.

Erweiterungen und Verweise

Bewusst nicht gebaut sind eine Torkompatibilität (nicht jedes Tor für jede Ladung), eine Zeitkomponente (Truck-Appointment-Scheduling mit Zeitfenstern), eine Sendungsebene unterhalb der Relationen (Cross-Dock-Routing) und eine bedingte Anzeige des exakten Optimums bei kleinen Hallen, die den Abstand der 2-opt-Lösung direkt messen würde. Verwandte Fragen:

• Die korrelationsbasierte Lagerplatzzuweisung (Artikel, die oft zusammen bestellt werden, nah lagern) ist dasselbe QAP mit Regalplätzen statt Toren; siehe Lagerlogistik optimieren.
• Hängen die Kosten nur von der Entfernung jedes Objekts zu einem festen Punkt ab, ist es kein QAP, sondern ein lineares Zuordnungsproblem; die Ungarische Methode dazu zeigen die Matching-Demos.

Quellen

• Quelltext, Dokumentation und Tests der Demo: github.com/sebastian-hanisch/dock_door-demo.
• Tsui und Chang (1990): formale Aufstellung des Dock Door Assignment Problems.
• Koopmans und Beckmann (1957): Einführung des quadratischen Zuordnungsproblems für ein Standortproblem.
• Sahni und Gonzalez (1976): Nichtapproximierbarkeit des allgemeinen QAP unter P ≠ NP.
• Taillard (1991): Robust-Tabu-Search für das QAP (Nachbarschaft und Tabu-Liste wie in der Dokumentation der Demo beschrieben).

Die Angaben stammen aus dem Quelltext der Demo und sind nicht nachgeschlagen; Koopmans und Beckmann sowie Sahni und Gonzalez sind zusätzlich aus dem Gedächtnis bestätigt, nicht geprüft. Die Rechnungen und Nachrechnungen dieser Seite sind keine Messungen der Demo.