Der Ablaufberg verständlich erklärt

Ein Güterzug mit Wagen für viele Ziele muss zerlegt und neu zusammengestellt werden. Dazu rollen die Wagen einzeln einen kleinen Hügel hinab. Reicht ein Lauf, oder muss der Zug mehrmals über den Hügel? Diese Seite zeigt, was das kostet und wann welches Vorgehen gewinnt.

Zuletzt aktualisiert: 11. November 2026

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

Ein Zug, der auseinandergenommen wird

Ein langer Güterzug kommt im Rangierbahnhof an, wo Güterzüge zerlegt und neu zusammengestellt werden. Er hat 40 Wagen, und sie wollen nicht alle zum selben Ort. Jeder Wagen gehört zu einem von 8 Zügen, die später in verschiedene Richtungen abfahren. Alle Wagen für denselben Abfahrtszug nennen wir eine Gruppe. Am Ende sollen die Wagen jeder Gruppe zusammenhängend hintereinander stehen.

Dazu dient der Ablaufberg, ein kleiner künstlicher Hügel. Die Lok schiebt den Zug langsam hinauf. Oben wird ein Wagen nach dem anderen losgelassen. Jeder rollt allein hinunter und über eine Weiche auf eines von 4 Auffanggleisen, kurz Gleisen.

Auf einem Gleis stehen die Wagen hintereinander, und wer zuerst herunterrollt, steht vorn. Das ist wie eine Schlange vor einem Schalter. Danach zieht die Lok die Gleise ab. Fertige Wagen bilden einen Abfahrtszug. Die übrigen gehen als neuer Zug erneut über den Berg, Gleis 1 zuerst, dann Gleis 2 und so weiter. Einen Lauf aller noch nicht fertigen Wagen über den Berg nennen wir Durchgang.

Um nachzurechnen, was das kostet, nutzt diese Seite ein vereinfachtes Rechenbild (Fachwort: Modell) mit zufällig erzeugten Zügen. Die Aussagen in diesem Teil beschreiben dieses Rechenbild, nicht einen echten Bahnhof.

Warum ein Durchgang oft nicht reicht

Bekäme jede Gruppe ein eigenes Gleis, wäre der Zug nach einem Durchgang sortiert. Im Beispiel gibt es aber 8 Gruppen und nur 4 Gleise. Dann stehen Wagen verschiedener Gruppen gemischt auf demselben Gleis. Der Zug muss erneut über den Berg, vielleicht mehrmals.

Erstes Vorgehen: Gruppe für Gruppe

Im ersten Durchgang bekommen 3 Gruppen je ein eigenes Gleis. Sie sind danach fertig und bleiben liegen. Alle anderen Wagen sammeln sich auf dem vierten Gleis und gehen erneut über den Berg. So werden in jedem Durchgang 3 weitere Gruppen fertig. Im letzten Durchgang genügt ein Gleis je übriger Gruppe. Im Beispiel sind das 3 Durchgänge.

Wir nennen das gruppenweise Abarbeiten. Sein Vorteil: Fertige Wagen werden nicht mehr bewegt. Das spart am meisten, wenn die großen Gruppen zuerst fertig werden.

Zweites Vorgehen: alle Gruppen zugleich

Das zweite Vorgehen erinnert an das Ordnen von Eintrittskarten nach Reihe und Platz. Dazu sortieren Sie erst alle Karten nach dem Platz. Dann sortieren Sie nach der Reihe, ohne die Plätze innerhalb einer Reihe wieder durcheinanderzubringen. Danach liegt alles in der richtigen Ordnung.

Genauso gehen die Wagen vor: Jede Gruppe bekommt ein Feld in einem Raster aus 4 Reihen mit je 4 Plätzen. Das sind 16 Felder, 8 davon bleiben leer. Jedes Gleis steht im ersten Durchgang für einen Platz, im zweiten für eine Reihe. Im ersten Durchgang rollt jeder Wagen auf das Gleis seines Platzes, im zweiten auf das Gleis seiner Reihe. Fachleute nennen dieses Vorgehen Radix, nach der Zahl, mit der man hier zählt: 4, wie die Gleise.

Dass die Ordnung des ersten Durchgangs im zweiten nicht verloren geht, liegt an den Gleisen. Sie sind Schlangen, und die Wagen behalten auf einem Gleis ihre Reihenfolge. Darum bleibt die Platzordnung innerhalb jeder Reihe erhalten.

Ein Durchgang unterscheidet 4 Gruppen, zwei Durchgänge schon 16. Deshalb braucht Radix im Beispiel nur 2 Durchgänge. In jedem davon läuft aber jeder Wagen über den Berg.

Was ein Durchgang kostet

Zwei Dinge kosten Zeit. Jedes Mal, wenn ein Wagen über den Berg rollt, zählt das als Wagenbewegung. Sie dauert eine halbe Minute. Dazu kommt der Aufwand je Durchgang: Lok umsetzen, Gleise abziehen. Er fällt an, egal wie viele Wagen laufen.

Im Beispiel spart Radix einen Durchgang, bewegt aber jeden Wagen in jedem Durchgang. Gruppenweise braucht einen Durchgang mehr, bewegt aber im Mittel weniger Wagen, weil fertige Wagen liegen bleiben. Ist ein Durchgang teuer, lohnt es sich also, Durchgänge zu sparen. Ist er billig, lohnt es sich, Wagenbewegungen zu sparen.

Im Beispielzug mit 40 Wagen, 8 Gruppen und 4 Gleisen liegt die Grenze bei knapp 8 Minuten Aufwand je Durchgang. Darunter ist gruppenweise schneller, darüber Radix. Das gilt laut Messung im Mittel über 20 zufällige Züge, wenn die größten Gruppen zuerst fertig werden.

Wenn Radix immer gewinnt

Bei vielen Gruppen oder wenigen Gleisen gibt es keine Wahl mehr. Mit 16 Gruppen auf 4 Gleisen braucht Radix 2 Durchgänge, gruppenweise im Mittel fast fünf. Mit 8 Gruppen auf 2 Gleisen sind es 3 gegen sieben. Außerdem bewegt gruppenweise dann auch mehr Wagen. Radix gewinnt in diesen beiden Fällen bei jedem Aufwand je Durchgang.

Der Grund: Gruppenweise macht je Durchgang nur wenige Gruppen fertig, und die übrigen Wagen laufen immer wieder.

Gruppen aufteilen: Was ein Rechenprogramm findet

Beide Vorgehen geben jeder Gruppe ein eigenes Gleis oder Feld. Ein Programm, das die kleinste mögliche Zahl von Durchgängen sucht, darf mehr. Es darf eine Gruppe auf zwei Gleise verteilen, wenn die Wagen nach dem Abziehen wieder zusammenstehen.

Stellen Sie sich ein Bücherregal nach dem Alphabet vor. Die Bücher mit B beginnen am Ende des ersten Fachs und enden am Anfang des zweiten. Liest man die Fächer der Reihe nach, stehen alle B zusammen. So können zwei Gleise gemeinsam eine Gruppe tragen.

So spart das Programm manchmal einen Durchgang. In allen gemessenen Fällen konnte das Programm auch zeigen, dass weniger Durchgänge unmöglich sind. Bei 12 Gruppen auf 3 Gleisen gelang das Sparen in allen 20 Zügen: 2 statt 3 Durchgänge. Wann es sich lohnt, ließ sich nicht auf ein einfaches Muster bringen.

Häufige Missverständnisse

• „Ein Rechenprogramm findet immer einen besseren Plan als Radix.“ Beim Beispielzug mit 8 Gruppen auf 4 Gleisen war Radix in allen 20 Zügen schon das Minimum.
• „Mehr Gleise sparen Durchgänge.“ Für Radix nicht überall. Bei 8 Gruppen braucht es mit 3, 4 oder 6 Gleisen jeweils 2 Durchgänge. Zwei Durchgänge mit je 3 Gleisen ergeben 3 mal 3, also neun Felder, und das genügt. Erst der Sprung von 2 auf 3 Gleise spart einen Durchgang.
• „Am Ende muss der Zug in einer festen Reihenfolge stehen.“ Nein, nur jede Gruppe muss zusammenhängend stehen. Genau diese Freiheit nutzt das Aufteilen von Gruppen.

Woran Sie das im Alltag erkennen

• Sie haben mehr Sorten als Ablageplätze, etwa Post für viele Straßen und wenige Fächer. Dann sortieren Sie in mehreren Runden, denn eine Runde trennt nur so viele Sorten, wie Fächer da sind.
• Jede Runde hat einen festen Anlauf, etwa den Tisch freiräumen. Ist er groß, sortiert man lieber in wenigen Runden.

Wie ernst ist das Rechenbild zu nehmen?

Die Züge sind zufällig erzeugt, und jedes Gleis fasst beliebig viele Wagen. Es gibt nur einen Zug und keinen Fahrplan. Die Zahlen zeigen Größenordnungen, keine Minutenwerte eines echten Bahnhofs.

Was Sie mitnehmen

• Fragen Sie beim Sortieren in Runden nach zwei Preisen: einer Runde und einem einzelnen Stück.
• Prüfen Sie, wo sich die Wahl umdreht, bevor Sie ein Vorgehen festlegen.
• Fragen Sie, ob wirklich jede Gruppe ein eigenes Fach braucht. Oft ist die Bedingung lockerer.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie erreichen es über den ersten Knopf unten. Zum Verstehen brauchen Sie es 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 ein Rechenmodell der Zugbildung am Ablaufberg: wie viele Durchgänge über den Berg nötig sind, um einen gemischten Güterzug nach Zielgruppen zu ordnen, und was ein Durchgang kosten darf, bevor sich die Wahl zwischen zwei Verfahren umdreht. Alle Zahlen gelten nur für dieses Modell mit zufällig erzeugten Zügen.

• Anlage und Durchgang: ein Berg mit \(k\) Richtungsgleisen (2, 3, 4 oder 6). Ein Zug mit \(n\) Wagen (20, 30, 40 oder 60 einstellbar) wird Wagen für Wagen abgedrückt. Ein Gleis ist eine Warteschlange: Der zuerst gerollte Wagen steht vorn. In einem Durchgang erhält jeder Wagen \(c\) des Zuges ein Gleis \(\kappa(c) \in \{1, \dots, k\}\). Danach werden die Gleise abgezogen, entweder als fertiger Teil eines Abfahrtszuges oder, in Gleisreihenfolge hintereinander, als neuer Zug für den nächsten Durchgang.
• Zug: Jeder Wagen gehört zu einer von 4, 8, 12 oder 16 Zielgruppen (einstellbar). Mit \(m\) ist im Folgenden die Zahl der tatsächlich vorkommenden Gruppen bezeichnet, die bei zufälliger Erzeugung unter dem eingestellten Wert liegen kann. Gleichverteilte Gruppen: Jeder Wagen gehört unabhängig und mit gleicher Wahrscheinlichkeit zu jeder Gruppe, die Gruppengrößen schwanken also zufällig. Ungleiche Gruppen: Das Gewicht der Gruppe \(i = 0, 1, \dots\) ist \(\lfloor 2520/(i+1) \rfloor\); die Gruppennummern werden zufällig vertauscht. Die Erzeugung ist ganzzahlig (Generator SplitMix64).
• Ziel: Nach \(P\) Durchgängen steht jede Gruppe zusammenhängend. Die Reihenfolge der Gruppen und der Wagen innerhalb einer Gruppe ist egal. Ein schon zusammenhängender Zug braucht keinen Durchgang.
• Kosten: Gezählt werden die Durchgänge \(P\) und die Wagenbewegungen \(W\) (ein Wagen rollt einmal über den Berg). Die Bergzeit ist Durchgänge mal Aufwand je Durchgang plus Wagenbewegungen mal Abdrückzeit je Wagen (Formel unten). Der Aufwand je Durchgang ist einstellbar von 0 bis 60 min in Schritten von 5 min, die Abdrückzeit mit 0,5 min je Wagen eine feste Annahme.
• Verfahren: gruppenweise (Gruppen in fester Reihenfolge, nach Nummer oder größte zuerst), Radix und eine exakte Rechnung mit dem CP-SAT-Löser von OR-Tools. Jeder Plan, auch der exakte, wird von einem unabhängigen Prüfer abgespielt, der die Gleise als Warteschlangen simuliert.
• Messreihe: 18 Varianten (Zuglänge von 8 bis 60 Wagen, Gruppenzahl, Gleise, Gruppengrößen) mit je 20 zufällig erzeugten Zügen (Startwerte 100 bis 119 des Generators), alle Verfahren plus die exakte Lösung. Der Standardfall hat 40 Wagen, 8 Gruppen, 4 Gleise und gleichverteilte Gruppen. In allen 360 Läufen ist die exakte Mindestzahl bewiesen.

Die Verfahren und die Formeln

Gruppenweise. In jedem Durchgang erhalten \(k-1\) Gruppen ein eigenes Gleis und sind fertig. Alle anderen Wagen sammeln sich auf dem letzten Gleis und laufen im nächsten Durchgang wieder. Im letzten Durchgang erhält jede übrige Gruppe ein Gleis. Mit \(m\) Gruppen braucht das Verfahren

\[\lceil (m-1)/(k-1) \rceil\]

Durchgänge. Fertige Wagen werden nicht mehr bewegt. Die Reihenfolge der Gruppen ist frei: nach Nummer oder „größte zuerst“. Die zweite Reihenfolge minimiert die Summe der Restlängen und damit die Wagenbewegungen (Begründung unten).

Radix. Die Gruppen werden mit \(0, \dots, m-1\) nummeriert. Durchgang \(j\) sortiert nach der \(j\)-ten Ziffer der Nummer zur Basis \(k\), die niedrigste Ziffer zuerst. Das braucht \(\lceil \log_k m \rceil\) Durchgänge. In jedem werden alle \(n\) Wagen bewegt, also sind es

\[n \lceil \log_k m \rceil\]

Wagenbewegungen.

Bergzeit und Kipppunkt. Mit \(P\) Durchgängen, \(W\) Wagenbewegungen, dem Aufwand \(s\) je Durchgang und der Abdrückzeit \(t_w\) je Wagen ist die Bergzeit

\[T = P \cdot s + W \cdot t_w\]

Zwei Verfahren \(a, b\) mit \(P_a > P_b\) und \(W_a < W_b\) brauchen gleich lang bei dem Aufwand

\[s^* = (W_b - W_a)\, t_w / (P_a - P_b)\]

Darunter ist \(a\) schneller, darüber \(b\). Ist ein Verfahren in beiden Größen mindestens so gut wie das andere, gibt es keinen Kipppunkt, und es gewinnt bei jedem \(s\).

Exakte Rechnung. Die Frage lautet: Geht das Gruppieren in \(P\) Durchgängen? Sie wird für \(P = 1, \dots, \lceil \log_k m \rceil - 1\) gestellt, denn Radix liefert die Obergrenze. Die Variable \(v^p_{ab}\) ist wahr, wenn Wagen \(a\) nach Durchgang \(p\) vor Wagen \(b\) steht, und \(\kappa_p(c)\) ist das Gleis von Wagen \(c\) im Durchgang \(p\):

\[v^p_{ab} \Leftrightarrow \kappa_p(a) < \kappa_p(b) \lor (\kappa_p(a) = \kappa_p(b) \land v^{p-1}_{ab})\]

Die Folge nach Durchgang \(p\) ordnet also zuerst nach Gleis und auf gleichem Gleis nach der alten Folge. Die Gruppe von \(a\) und \(b\) bleibt zusammenhängend, wenn kein Wagen \(x\) einer anderen Gruppe mit \(a\) vor \(x\) vor \(b\) steht. Die kleinste zulässige Zahl \(P\) ist die Mindestzahl. Sie gilt als bewiesen, wenn alle kleineren Zahlen als unzulässig bewiesen sind. In diesem Modell werden in jedem Durchgang alle Wagen bewegt. Die Wagenbewegungen der exakten Lösung sind deshalb nur eine Obergrenze und werden nicht mit den anderen Verfahren verglichen. Ob die exakte Lösung in der Bergzeit gegen gruppenweise gewinnt, ist damit offen; in der Durchgangszahl braucht sie nie mehr als Radix. Je Durchgang gibt es \(n(n-1)/2\) Relationsvariablen \(v\), und die Zahl der Verbotsklauseln wächst höchstens kubisch in \(n\) (Rechnung dieser Seite aus dem Aufbau des Modells).

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen.

Radix sortiert nach \(\lceil \log_k m \rceil\) Durchgängen.

• Schritt 1: Ein Durchgang ist stabil. Zwei Wagen auf demselben Gleis behalten ihre Reihenfolge, weil das Gleis eine Warteschlange ist.
• Schritt 2: Nach Durchgang \(j\) sind die Wagen nach den \(j\) niedrigsten Ziffern der Gruppennummer geordnet, die \(j\)-te Ziffer ist das stärkste Kriterium. Für \(j = 1\) ist das die Verteilung selbst. Im Schritt zu \(j+1\) trennt die neue Ziffer die Wagen nach Gleis, und wegen Schritt 1 bleibt auf jedem Gleis die Ordnung nach den niedrigeren Ziffern.
• Schritt 3: Mit \(d\) Durchgängen lassen sich \(k^d\) Nummern unterscheiden, gebraucht werden \(m\). Gesucht ist das kleinste \(d\) mit \(k^d \ge m\), also \(d = \lceil \log_k m \rceil\). Da jeder Wagen in jedem Durchgang läuft, sind es \(n \lceil \log_k m \rceil\) Wagenbewegungen.

Gruppenweise: Zahl der Durchgänge. Die Herleitung gilt für \(k \ge 2\) und \(m \ge 2\).

• Schritt 1: Jeder Durchgang vor dem letzten macht \(k-1\) Gruppen fertig, solange vorher mehr als \(k\) Gruppen übrig sind. Nach \(j\) solchen Durchgängen sind es \(j(k-1)\) Gruppen.
• Schritt 2: Im letzten Durchgang genügen \(k\) Gleise für höchstens \(k\) übrige Gruppen. Mit \(P\) Durchgängen geht das, wenn \(m - (P-1)(k-1) \le k\) ist.
• Schritt 3: Umgestellt heißt das \(P \ge (m-1)/(k-1)\). Das kleinste ganze \(P\) ist \(\lceil (m-1)/(k-1) \rceil\).

Gruppenweise: warum „größte zuerst“ die Wagenbewegungen unter den gruppenweisen Reihenfolgen minimiert. Bedingung: Die Reihenfolge der Gruppen ist fest, und je Durchgang werden \(k-1\) Gruppen fertig.

• Schritt 1: Vor Durchgang \(j\) laufen noch \(r_j\) Wagen, mit \(r_1 = n\), und es gilt \(W = \sum_j r_j\). Die Zahl \(r_j\) ist \(n\) minus die Wagen der bis dahin fertigen \((j-1)(k-1)\) Gruppen.
• Schritt 2: Die ersten \((j-1)(k-1)\) Gruppen in der Reihenfolge „größte zuerst“ haben unter allen Auswahlen gleich vieler Gruppen die größte Wagensumme.
• Schritt 3: Also ist jedes \(r_j\) und damit \(W\) bei dieser Reihenfolge am kleinsten, bei gleicher Durchgangszahl.

Kipppunkt. Es gilt \(T_a \le T_b\) genau dann, wenn \(s\,(P_a - P_b) \le (W_b - W_a)\, t_w\). Wegen \(P_a - P_b > 0\) ist das gleichwertig zu \(s \le s^*\) mit der Formel oben.

Zwei Züge von Hand

Beide Beispiele sind ausgedacht und von Hand gerechnet (Rechnung dieser Seite, keine Messung).

Beispiel 1: Fünf Wagen, drei Gruppen a, b, c, zwei Gleise. Die Wagen 1 bis 5 gehören der Reihe nach zu a, b, a, c, b.

• Gruppenweise (\(k-1 = 1\) Gruppe je Durchgang). Durchgang 1: Gruppe a auf Gleis 1 (Wagen 1, 3), alle anderen auf Gleis 2 (Wagen 2, 4, 5). Gruppe a ist fertig. Durchgang 2 mit den drei Resten: b auf Gleis 1 (Wagen 2, 5), c auf Gleis 2 (Wagen 4). Endfolge 1, 3, 2, 5, 4. Das sind 2 Durchgänge und 5 + 3 = 8 Wagenbewegungen.
• Radix (Nummern a = 0, b = 1, c = 2, Basis 2). Durchgang 1 nach der niedrigsten Ziffer (a: 0, b: 1, c: 0): Gleis 1 mit den Wagen 1, 3, 4, Gleis 2 mit den Wagen 2, 5; neue Folge 1, 3, 4, 2, 5. Durchgang 2 nach der höheren Ziffer (a: 0, b: 0, c: 1): Gleis 1 mit 1, 3, 2, 5, Gleis 2 mit Wagen 4. Endfolge wieder 1, 3, 2, 5, 4. Das sind 2 Durchgänge und 5 + 5 = 10 Wagenbewegungen.
• Vergleich: Die Formeln liefern \(\lceil (3-1)/(2-1) \rceil = 2\) und \(\lceil \log_2 3 \rceil = 2\). Bei gleicher Durchgangszahl und weniger Wagenbewegungen gewinnt gruppenweise hier bei jedem Aufwand je Durchgang.

Beispiel 2: Eine Gruppe teilen. Acht Wagen mit den Gruppen a, b, c, d, a, b, c, d der Reihe nach, drei Gleise. Radix braucht \(\lceil \log_3 4 \rceil = 2\) Durchgänge, gruppenweise \(\lceil 3/2 \rceil = 2\).

• Ein Durchgang genügt trotzdem: Gleis 1 nimmt die Wagen 1, 5, 6 (a, a, b), Gleis 2 die Wagen 2, 3, 7 (b, c, c), Gleis 3 die Wagen 4, 8 (d, d). Werden die Gleise in der Reihenfolge 1, 2, 3 abgezogen, steht die Folge a, a, b, b, c, c, d, d. Gruppe b liegt auf zwei benachbarten Gleisen und steht doch zusammenhängend.
• Kosten: 8 Wagenbewegungen gegen 12 bei gruppenweise und 16 bei Radix. Weniger als ein Durchgang ist nicht möglich, weil die Wagenfolge nicht gruppiert ist.
• Bedingung: Ob das Teilen hilft, hängt von der Wagenfolge ab. Bei 5 Gruppen auf 2 Gleisen braucht Radix 3 Durchgänge. Von zwei ausprobierten Folgen mit 8 Wagen kam die Folge a, e, a, d, c, e, b, b mit einem Durchgang aus, die Folge a, d, e, d, a, c, b, c brauchte 2 (Breitensuche über alle Pläne, ebenfalls Rechnung dieser Seite).

Befunde

Jede Zeile gilt für 20 zufällig erzeugte Züge je Variante (Startwerte 100 bis 119); angegeben sind Mittelwerte. Wo nichts anderes steht, haben die Züge 40 Wagen. Wagenbewegungen werden je Wagen gezählt, das gruppenweise Verfahren mit „größte zuerst“. Der Kipppunkt ist der Wert der Kipppunkt-Formel, gerechnet mit den Mittelwerten von Durchgängen und Wagenbewegungen beider Verfahren.

Frage	Befund
Standardfall (40 Wagen, 8 Gruppen, 4 Gleise): Wie viele Durchgänge?	Gruppenweise 3,0, Radix 2,0, exakt 2,0. Die exakte Lösung schlägt Radix in 0 von 20 Zügen.
Standardfall: Wagenbewegungen und Kipppunkt?	Gruppenweise 1,61 statt 2,00 Bewegungen je Wagen. Kipppunkt 7,9 min Aufwand je Durchgang: Darunter ist gruppenweise schneller, darüber Radix. Bei 60 Wagen 10,4 min, bei ungleichen Gruppen 27,8 min.
Wann gibt es keine Wahl? (16 Gruppen auf 4 Gleisen; 8 Gruppen auf 2 Gleisen)	Bei 16 Gruppen braucht gruppenweise 4,9 Durchgänge gegen 2,0 und 2,32 Bewegungen je Wagen gegen 2,00. Bei 2 Gleisen sind es 7,0 Durchgänge gegen 3,0 und 3,60 Bewegungen gegen 3,00. Radix gewinnt dann bei jedem Aufwand je Durchgang.
Hilft „größte zuerst“? (ungleiche Gruppen)	1,31 statt 1,70 Bewegungen je Wagen (−23 %) bei gleicher Durchgangszahl.
Wann schlägt die exakte Lösung Radix?	Nicht im Standardfall (0 von 20) und nicht bei 4 Gleisen mit 12 oder 16 Gruppen. Bei 12 Gruppen auf 3 Gleisen: 2,0 statt 3,0 Durchgänge (20 von 20), bei 16 Gruppen auf 3 Gleisen ebenso. Bei 12 Gruppen auf 2 Gleisen 3,0 statt 4,0, bei 8 Gruppen auf 6 Gleisen 1,0 statt 2,0.
Und die Zuglänge? (6 Gruppen auf 3 Gleisen, Züge mit 8 bis 40 Wagen)	Die exakte Lösung schlägt Radix in 95 % der 8-Wagen-Züge, 100 % der 12-Wagen-Züge, 30 % der 20-Wagen-Züge und in 0 % der 30- und 40-Wagen-Züge.
Wie lange rechnet die exakte Lösung?	Median 2,3 s je Zug im Standardfall (40 Wagen), 6,3 s bei 60 Wagen (alle Fragen \(P = 1, \dots, \lceil \log_k m \rceil - 1\) zusammen); längste Rechnung 13,8 s.

Nachrechnung (Rechnung dieser Seite): Die Durchgangszahlen des Standardfalls folgen aus den Formeln mit \(m = 8\) und \(k = 4\), nämlich \(\lceil 7/3 \rceil = 3\) und \(\lceil \log_4 8 \rceil = 2\). Mit \(k = 2\) ergeben sie 7 und 3. Der Kipppunkt des Standardfalls folgt bis auf die Rundung der Bewegungen je Wagen aus \((2{,}00 - 1{,}61) \cdot 40 \cdot 0{,}5 / (3 - 2)\).

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Durchgangszahlen der drei Verfahren in den 18 Varianten und die Rangfolge im Standardfall, jeweils für diese 20 Züge je Variante. Die exakte Mindestzahl ist in allen Läufen bewiesen: Die Aussagen „spart einen Durchgang“ sind Aussagen über das Minimum im Modell, keine Suchergebnisse.
• Die Fälle, in denen Radix bei jedem Aufwand je Durchgang gewinnt: Dort ist Radix in beiden Größen besser, der Kipppunkt entfällt.

Was sie nicht belegt:

• Kein Muster: Wann die exakte Lösung Radix schlägt, ließ sich nicht auf ein einfaches Muster über Gruppen und Gleise bringen. 18 Varianten mit je 20 Zügen belegen das nicht. Für die hohen Anteile bei den kurzen Zügen liegt eine Deutung nahe: Dort bestehen die Gruppen aus ein oder zwei Wagen. Gemessen ist sie nicht; warum die Zuglänge den Vorsprung abbaut, ist nicht untersucht.
• Kipppunkt aus Mittelwerten: Durchgänge und Wagenbewegungen streuen von Zug zu Zug, und angegeben ist nur der Wert aus den Mittelwerten. Im Standardfall und bei 60 Wagen liegen die Kipppunkte der Einzelzüge in der Nähe dieses Wertes. Bei ungleichen Gruppen kommt der Mittelwert-Wert in keinem einzelnen Zug vor: Er entsteht, weil gruppenweise dort im Mittel einen halben Durchgang mehr braucht als Radix. In der Hälfte der 20 Züge ist gruppenweise in beiden Größen mindestens so gut wie Radix und gewinnt bei jedem Aufwand je Durchgang. Bei den übrigen liegt der Kipppunkt grob zwischen einem Drittel und der Hälfte des Mittelwert-Wertes (Rechnung dieser Seite aus den Einzelzügen, nicht in der Demo gezeigt). Bei 12 Gruppen auf 4 Gleisen liegt der Kipppunkt nur bei einem Bruchteil einer Minute, dort entscheidet praktisch Radix, aber nicht in jedem Einzelzug.
• Aufwand je Durchgang: Er ist ein Regler, die Messung kennt keinen realen Wert. Die Lage des Kipppunkts sagt etwas über das Verhältnis zur festen Abdrückzeit, nicht über echte Bahnhöfe.
• Synthetische Züge: ein Zug, feste Abdrückzeit je Wagen, keine Gleislängen (jedes Gleis fasst beliebig viele Wagen), keine Ankunftszeiten mehrerer Züge, keine Bergkapazität über den Tag, Wagen innerhalb einer Gruppe unsortiert.
• Obergrenze statt Untergrenze: \(\lceil \log_k m \rceil\) ist nur die Zahl der Durchgänge von Radix, also eine Obergrenze für die Mindestzahl. Dass sie auch allgemein nötig wäre, folgt nicht, und die exakte Rechnung findet Gegenfälle. Die Messung gibt nur Mittelwerte an, keine Streuung.
• Rechenzeit: Sie wächst mit der Zuglänge (Zahlen in der Tabelle) und hängt vom Rechner ab; die Werte sind keine Garantie.
• Schwierigkeit: Das verwandte Train-Marshalling-Problem ist laut Literatur NP-vollständig. Wie schwer die hier gestellte Frage ist, ist nicht untersucht.

Erweiterungen und Verweise

• Nicht umgesetzt: Gleislängen und Überläufe, mehrere ankommende Züge mit Abfahrtsfristen, Bergkapazität und Schichten, Sortieren innerhalb der Gruppen (volle Reihenfolge nach Wagennummer), Gleise als Stapel (LIFO), Störungen und Rangierlok-Planung.
• Anderes Gleismodell: Das Abstellen auf LIFO-Gleisen ist ein anderes Modell und eine Platzwahl statt einer Sortieraufgabe; es steckt in der hofstellplatz-demo und der stapelplanung-demo.
• Gleiche Themenreihe: Dasselbe Thema Schienenverkehr behandeln der Taktfahrplan (Umsteigen im Takt) und das Crew Pairing (Besatzungseinsatz), mit anderen Fragen.

Quellen

• Jacob, Márton, Maue, Nunkesser (2011): Multistage Methods for Freight Train Classification. Networks 57(1) (Radix-Verfahren und die Fragestellung der Zugbildung mit mehreren Durchgängen).
• Dahlhaus, Horák, Miller, Ryan (2000): The train marshalling problem. Discrete Applied Mathematics 103 (verwandte, aber andere Frage; NP-vollständig).
• OR-Tools, CP-SAT-Löser (für die exakte Rechnung).

Die Angaben zu Jacob et al. und Dahlhaus et al. wurden an bibliografischen Einträgen geprüft; die Volltexte sind nicht gelesen, die Zuordnung von Radix und Fragestellung zum erstgenannten Aufsatz folgt der Dokumentation der Demo. Die Befundtabelle gibt die Messreihe der Demo wieder. Herleitungen, Handbeispiele und Nachrechnungen sind Rechnungen dieser Seite.