Das Hauptlauf-Netz verständlich erklärt

Ein Paketdienst hat mehrere Lager. Zwischen vielen Paaren sollen täglich Sendungen fahren. Bekommt jedes Paar einen eigenen Lkw, oder laufen manche Sendungen über ein Lager dazwischen? Diese Seite zeigt, wann sich das Umladen lohnt und wann es mehr kostet.

Zuletzt aktualisiert: 11. November 2026

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

Ein Paketdienst mit mehreren Lagern

Stellen Sie sich einen Paketdienst mit mehreren Lagern vor. Jeden Tag sollen Sendungen von manchen Lagern zu anderen fahren. Wir rechnen mit einem vereinfachten Rechenbild (Fachwort: Modell): erfundene Lager, Mengen und Kosten. Mengen zählen wir in Paletten.

Pakete werden zuerst abgeholt, dann zwischen den Lagern gefahren und zuletzt zugestellt. Das mittlere Stück heißt Hauptlauf. Nur darum geht es hier.

Auf dem Hauptlauf fahren große Lkw nach festem Fahrplan. Eine feste Verbindung zwischen zwei Lagern heißt hier Linie. Das Bild dazu ist eine Buslinie: Sie fährt auch, wenn nur zwei Fahrgäste sitzen. So kostet auch ein Lkw die Fahrt, ob er voll ist oder fast leer. Diese Kosten heißen Fixkosten. Je länger die Linie, desto höher sind sie. Dazu kommt ein kleiner Betrag je Palette und Kilometer.

Direkt oder mit Umweg?

Jedes Lagerpaar mit Sendungen könnte eine eigene Linie bekommen. Das ist einfach, aber viele Lkw fahren dann nur zum Teil gefüllt: Die Menge je Sendung ist im Rechenbild zufällig, in der Ausgangslage höchstens eine volle Ladung.

Es geht auch anders. Eine Sendung fährt über ein drittes Lager, das Zwischenlager. Dort wird sie umgeladen und fährt auf einer Linie weiter, die ohnehin fährt. Das kennen Sie vom Umsteigen: Wer von Dorf zu Dorf will, fährt oft über die Kreisstadt, weil dorthin viele Busse fahren.

Das hat zwei Preise: Ein Umweg kostet Strecke, und Umladen kostet eine Gebühr je Palette.

Drei Regeln im Vergleich

Wir vergleichen drei Regeln, nach denen der Paketdienst planen kann:

• Alles direkt. Jedes Lagerpaar mit Sendungen bekommt eine eigene Linie. Vorteil: kein Umweg, kein Umladen. Preis: viele nur teilweise gefüllte Lkw.
• Alles über ein Zwischenlager. Alle Sendungen laufen über dasselbe Lager, und zwar über das günstigste von allen. Nur Sendungen, die dort beginnen oder enden, fahren direkt. Vorteil: wenige, volle Linien. Preis: Umweg und Umladen.
• Mischung. Jede Sendung fährt direkt oder über ein Zwischenlager, je nachdem, was billiger ist. Vorteil: Der Umweg kommt nur vor, wo er sich lohnt. Preis: Sie ist schwer zu finden, denn jede Entscheidung ändert, welche Linien sich lohnen.

Die Mischung entsteht schrittweise. Man startet mit einfachen Plänen, etwa alles direkt, und prüft Sendung für Sendung, ob ein anderer Weg billiger ist. Zuletzt probiert man Paare von Sendungen. Denn ein Lkw ist ganz da oder gar nicht: Manchmal wird erst dann ein ganzer Lkw überflüssig, wenn zwei Sendungen gemeinsam eine Linie verlassen. Weil man bei den einfachen Regeln anfängt und nur Billigeres übernimmt, ist die Mischung nie teurer als alles direkt oder alles über ein Zwischenlager. Sie ist aber nicht immer so billig wie der bestmögliche Plan.

Ein Beispiel mit drei Lagern

Ein Beispiel mit angenommenen Zahlen: Drei Lager A, B und C liegen auf einer Geraden, B in der Mitte, je 10 Kilometer auseinander. Von A nach C sollen 5 Paletten fahren, von B nach C 50. Ein Lkw fasst 60. Eine Linie kostet 10 Euro je Kilometer plus 10 Cent je Palette und Kilometer. Umladen kostet 1 Euro je Palette.

Alles direkt braucht zwei Linien, eine kurze von B nach C und eine lange von A nach C, die nur 5 Paletten trägt. Das kostet 360 Euro am Tag.

Über B fahren die 5 Paletten zuerst auf einer kurzen Linie von A nach B. In B werden sie auf den Lkw nach C umgeladen, der dort ohnehin fährt. Die lange Linie von A nach C entfällt, und B liegt auf dem Weg, einen Umweg gibt es nicht. Zusammen mit der Umladegebühr kostet das 265 Euro am Tag.

Der Vorteil hängt an der Ladung. Wären es 56 statt 50 Paletten von B nach C, bräuchte die Linie von B nach C einen zweiten Lkw. Dessen Kosten fressen die Ersparnis auf, und die Umladegebühr kommt obendrauf.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser. Der erste Knopf unten öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie es nicht.

Es startet mit sieben zufällig verteilten Lagern, Linien zu 15 Euro je Kilometer und einer kleinen Umladegebühr, dem Ausgangsfall. Die Aussagen in diesem Teil beschreiben das Rechenbild, nicht die Wirklichkeit. Alle Kostenzahlen unten stammen aus einem einzigen, zufällig erzeugten Gebiet. In einem anderen Gebiet können sie anders ausfallen.

Was die Messung zeigt

Im Ausgangsfall ist die Mischung am billigsten. Sie spart gegenüber alles direkt gut ein Drittel der Kosten, weil sich Sendungen Linien teilen. Ob das Teilen sich lohnt, hängt von den Preisen ab. Wir ändern sie einzeln:

• Billige Linien (2 statt 15 Euro je Kilometer): Alles über ein Zwischenlager wird teurer als alles direkt, denn es spart wenig Linienkosten, während Umweg und Umladen weiter kosten. Die Mischung spart knapp ein Fünftel, weil sie nur umlädt, wo es sich lohnt.
• Teure Linien (25 Euro je Kilometer): Jede gesparte Linie spart jetzt mehr. Auch alles über ein Zwischenlager ist billiger als alles direkt. Die Mischung spart gut zwei Fünftel.
• Teures Umladen (12 Euro je Palette, im Ausgangsfall viel weniger): Alles über ein Zwischenlager wird teurer als alles direkt, denn jede Sendung wird umgeladen, die nicht am Zwischenlager beginnt oder endet. Die Mischung spart knapp ein Drittel, weil sie auf direkte Linien ausweicht.

Wie nah am bestmöglichen Plan?

Für zwanzig zufällige Gebiete mit je sieben Lagern und Linien zu 15 Euro je Kilometer berechnete ein anderes Rechenprogramm den bestmöglichen Plan. Die Mischung lag im Mittel unter 2 Prozent darüber, im schlechtesten Gebiet knapp acht Prozent. Die Suche wurde aber an genau diesen Gebieten verbessert, wie bei einer Prüfung, deren Fragen man vorher kannte. Der Abstand kann daher zu günstig ausfallen.

Häufige Missverständnisse

• „Mehr Linien bedeuten höhere Kosten.“ Im Ausgangsfall nutzt die Mischung mehr Linien als die Regel mit einem Zwischenlager und ist trotzdem billiger. Das Programm zeigt beide Zahlen an. Die Kosten hängen an der Zahl der Lkw und an ihren Strecken. Wie viele Linien es gibt, sagt darüber wenig.
• „Je teurer die Linien, desto größer die Ersparnis.“ Wir rechneten sieben Linienpreise durch. Die Ersparnis stieg bis zum zweitteuersten und lag beim teuersten wieder etwas niedriger. Das liegt laut Nachrechnung im zweiten Teil nicht an den Kosten, sondern daran, dass die Suche dort weiter vom bestmöglichen Plan lag.

Woran Sie das im Alltag erkennen

• Ein Bus fährt nach Fahrplan fast leer. Die Fahrt kostet dasselbe, ob zwei oder zwanzig Menschen sitzen.
• Sie reisen über einen großen Bahnhof statt direkt. Dorthin fahren viele Züge, aber das Umsteigen kostet Zeit.
• Mehrere Kollegen fahren in einem Auto zur Arbeit, und einer holt die anderen unterwegs ab. Das spart Autos und kostet einen kleinen Umweg.

Wie ernst ist das Rechenbild zu nehmen?

Das Rechenbild ist stark vereinfacht: Jede Sendung wird höchstens einmal umgeladen, die Mengen sind täglich gleich, alle Kosten erfunden. Ob die Abstände zwischen den Regeln in echten Netzen ähnlich sind, zeigt das Programm nicht.

Was Sie mitnehmen:

• Fragen Sie bei einer festen Verbindung zuerst, was sie kostet, wenn sie nur halb voll fährt.
• Prüfen Sie bei jedem Sammelpunkt, ob die gesparte Fahrt mehr wert ist als Umweg und Umladen zusammen.
• Legen Sie sich nicht auf „alles direkt“ oder „alles über einen Punkt“ fest, bevor Sie auch eine Mischung geprüft haben.

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. Gegenstand ist das Hauptlauf-Netzwerkdesign: Zwischen Depot-Paaren fallen täglich Sendungen an. Zu entscheiden ist, welche Depot-Paare eine feste, tägliche Hauptlauf-Linie bekommen (Lkw nach Fahrplan) und welche Sendungen stattdessen über ein Zwischendepot umgeschlagen werden, um sich eine ohnehin fahrende Linie zu teilen. Das ist ein Fixed-Charge-Netzwerkdesign mit mehreren Gütern (Fixed-Charge Multicommodity Network Design): Eine Linie kostet pro Lkw fest, ob er voll ist oder nicht, dazu kommen Kosten je Einheit. Die allgemeine Aufgabe gilt als NP-schwer (Magnanti, Wong 1984; Crainic 2000).

• Instanz: Die Depots liegen zufällig in einer Ebene, die Entfernung \(\ell_{ij}\) ist euklidisch. Zwischen zwei Depots besteht höchstens eine Sendung \(k\) mit der Menge \(q_k\), gerichtet vom Depot mit der kleineren zu dem mit der größeren Nummer. Ein Paar hat mit der Wahrscheinlichkeit \(\rho\) (Nachfragedichte) eine Sendung. Die Menge \(q_k\) ist unabhängig von der Lkw-Kapazität gleichverteilt zwischen einem festen kleinen und einem festen größeren Wert, multipliziert mit einem Skalierungsfaktor. In der Voreinstellung (Skalierung 1) ist der größere Wert gleich der Kapazität, eine Sendung füllt also höchstens einen Lkw. Wird die Kapazität gesenkt oder die Skalierung erhöht, kann eine Sendung mehrere Lkw brauchen. Die Demo erlaubt 4 bis 9 Depots (Voreinstellung 7) und eine Dichte \(\rho\) von 0,2 bis 1,0 (Voreinstellung 0,5).
• Kosten: Ein Lkw auf der Linie zwischen den Depots \(i\) und \(j\) kostet \(F_{ij} = a + b\,\ell_{ij}\) (Grundbetrag \(a\), Betrag \(b\) je Kilometer, Voreinstellung für \(b\): 15 € je Kilometer). Je Einheit auf dieser Linie fallen \(c_{ij} = v\,\ell_{ij}\) an (\(v\): variable Kosten je Einheit und Kilometer). Grundbetrag \(a\), \(v\), Kapazität und Skalierung sind in der Demo einstellbar und stehen auf festen Voreinstellungen. Wird eine Sendung umgeschlagen, kommen \(h\) je Einheit hinzu (Voreinstellung 1,5 € je Einheit). Ein Lkw hat die Kapazität \(\mathrm{cap}\) und bedient beide Richtungen einer Linie mit je voller Kapazität.
• Routen und Lkw: Jede Sendung nutzt genau eine Route aus einem festen Kandidatensatz: direkt oder über genau ein Zwischendepot \(m\), das weder Ursprung noch Ziel ist. Bei \(n\) Depots hat jede Sendung also \(n-1\) Routen, und mehr als ein Umschlag ist ausgeschlossen. Mehrere Sendungen teilen sich eine Linie. Mit den Mengen \(\phi^{+}_{ij}\) und \(\phi^{-}_{ij}\) je Richtung braucht die Linie \(y_{ij} = \max\bigl(\lceil \phi^{+}_{ij}/\mathrm{cap} \rceil,\, \lceil \phi^{-}_{ij}/\mathrm{cap} \rceil\bigr)\) Lkw. Fixkosten fallen je Lkw an, auch wenn ein Lkw nur teilweise gefüllt ist.

Verglichen werden vier Verfahren:

• Alles direkt: Jede Sendung fährt direkt, es gibt keine Bündelung. Das ist der Bezugspunkt.
• Hub-and-Spoke: Alle Sendungen laufen über ein einziges Depot, das beste von allen (Best-of-\(n\) über alle Depots als Hub). Sendungen, die am Hub beginnen oder enden, fahren direkt.
• Greedy-Verbesserung (im Folgenden Greedy; trotz des Namens kein einfacher Ein-Schritt-Greedy, sondern ein Mehrfachstart mit Tauschzügen): Eine lokale Suche (Koordinatenabstieg über einzelne Sendungen) wechselt je Sendung zur billigsten anderen Route, solange die Gesamtkosten sinken. Startpunkte sind Alles direkt, jede Einzel-Hub-Konfiguration und eine sequenzielle Grenzkosten-Konstruktion in aufsteigender und absteigender Reihenfolge der Mengen. Diese Konstruktion wählt je Sendung die Route mit den geringsten Grenzkosten bei Wiederverwendung bereits eröffneter Linien. Das beste Endergebnis gewinnt. Darauf folgt ein Politurschritt mit paarweisen Tauschzügen: Zwei Sendungen wechseln gleichzeitig ihre Route, bewertet wird nur die Änderung an den betroffenen Linien. Weil Alles direkt und jede Einzel-Hub-Konfiguration Startpunkte sind und nur Verbesserungen übernommen werden, ist das Ergebnis nie teurer als Alles direkt oder Hub-and-Spoke.
• Exakt: das vollständige gemischt-ganzzahlige Modell (Formeln unten), gelöst mit SCIP über Google OR-Tools. Die Rechenzeit der Demo ist auf 4 Sekunden begrenzt (die Laufzeitmessung in Befund 6 stammt aus einer anderen Messung, siehe dort). Läuft sie ab, liefert der Löser die beste gefundene Lösung ohne Optimalitätsbeweis, und die Demo kennzeichnet das.

Die Hauptansicht der Demo zeigt jeweils die billigste der drei Heuristiken. Kein Verfahren wird bevorzugt.

Die Formeln

Gegeben sind die Depots \(V\), die Sendungen \(k \in K\) mit Ursprung \(o_k\), Ziel \(d_k\) und Menge \(q_k\), die Kandidatenlinien \(\{i,j\}\) mit Fixkosten \(F_{ij}\) je Lkw und Kosten \(c_{ij}\) je Einheit, die Kapazität \(\mathrm{cap}\) je Lkw und die Umschlagkosten \(h\) je Einheit. Die binäre Variable \(z_{k,r}\) ist 1, wenn Sendung \(k\) die Route \(r\) nutzt, die ganzzahlige Variable \(y_{ij} \ge 0\) zählt die Lkw auf der Linie \(\{i,j\}\). Hub bezeichnet das Zwischendepot einer Route. Zu minimieren sind die Fixkosten der Lkw, die Kosten je Einheit entlang der Route und die Umschlagkosten:

\[\min \sum_{\{i,j\}} F_{ij}\, y_{ij} \;+\; \sum_{k}\sum_{r} \Big(q_k \sum_{(i,j)\in r} c_{ij} \;+\; \mathbb{1}[r \text{ nutzt Hub}]\, q_k h\Big)\, z_{k,r}\]

Jede Sendung nimmt genau eine Route (\(\sum_r z_{k,r} = 1\) für alle \(k\)). Je Linie und Richtung darf die Menge die Kapazität der Lkw nicht übersteigen:

\[\sum_{k,r:\, (i,j) \in r} q_k\, z_{k,r} \;\le\; \mathrm{cap} \cdot y_{ij}.\]

Die Lücke eines Verfahrens zum Optimum ist \((J_H - J^{*})/J^{*}\), die Ersparnis gegenüber Alles direkt ist \((J_D - J_H)/J_D\), jeweils in Prozent. Dabei sind \(J_H\), \(J_D\) und \(J^{*}\) die Gesamtkosten des Verfahrens, von Alles direkt und des Optimums.

Rechnungen dieser Seite

Die folgenden Rechnungen stammen von dieser Seite, nicht aus der Demo. Sie erklären, warum die gemessenen Werte so aussehen.

Durchgerechnetes Beispiel: drei Depots auf einer Geraden. Die Depots A, B, C liegen in dieser Reihenfolge mit gleichen Abständen auf einer Geraden. Von A nach C geht die kleine Menge \(q_A\), von B nach C die größere \(q_B\), und es gilt \(q_A + q_B \le \mathrm{cap}\) sowie \(a = 0\).

• Schritt 1, direkt: Zwei Linien mit je einem Lkw. Die Kosten sind \(F_{AC} + F_{BC} + q_A c_{AC} + q_B c_{BC}\).
• Schritt 2, über B: Die Linie B-C trägt \(q_A + q_B \le \mathrm{cap}\), die Linie A-B nur \(q_A\), also je ein Lkw. Die Kosten sind \(F_{AB} + F_{BC} + q_A c_{AB} + (q_A + q_B)\,c_{BC} + h\,q_A\).
• Schritt 3, Differenz: B liegt auf dem Weg, also gilt \(c_{AC} = c_{AB} + c_{BC}\), und die Kosten je Einheit sind gleich. Wegen \(a = 0\) und gleicher Abstände gilt \(F_{AC} - F_{AB} = F_{BC}\). Die Ersparnis über B ist \(F_{BC} - h\,q_A\). Sie ist positiv, solange die Umschlaggebühr für die kleine Menge kleiner ist als die Fixkosten der eingesparten Teilstrecke.
• Schritt 4, Schwelle: Gilt \(q_A + q_B > \mathrm{cap}\), aber weiter \(q_B \le \mathrm{cap}\), braucht die Linie B-C über B zwei Lkw. Die Fixkosten über B sind dann \(F_{AB} + 2F_{BC} = F_{AC} + F_{BC}\), also so hoch wie direkt. Der Weg über B kostet dann \(h\,q_A\) mehr als direkt. Die Ersparnis kippt sprunghaft ins Negative, weil die Lkw-Zahl eine Treppenfunktion der Menge ist.

Wann lohnt es, eine einzelne Sendung umzulegen? Sendung \(k\) fährt bisher direkt von \(o_k\) nach \(d_k\). Angenommen, die Direktlinie trägt nur diese Sendung und entfällt, wenn \(k\) über ein Zwischendepot \(m\) fährt, und die Linien \(\{o_k, m\}\) und \(\{m, d_k\}\) fahren ohnehin mit freier Kapazität. Dann lohnt das Umlegen bei \(q_k \le \mathrm{cap}\) genau dann, wenn \(F_{o_k d_k} > q_k\,\bigl(c_{o_k m} + c_{m d_k} - c_{o_k d_k} + h\bigr)\) gilt. Für \(q_k > \mathrm{cap}\) steht links \(\lceil q_k/\mathrm{cap} \rceil\,F_{o_k d_k}\), und die Zwischenlinien brauchen entsprechend mehr freie Kapazität.

Der Klammerausdruck ist nicht negativ, weil \(c\) proportional zur euklidischen Entfernung ist und die Dreiecksungleichung gilt. Die linke Seite wächst mit dem Betrag \(b\) je Kilometer (\(F = a + b\,\ell\)), die rechte hängt nicht von \(b\) ab. Die rechte Seite wächst mit \(h\). Das erklärt die Richtung der gemessenen Kipppunkte: Hub-and-Spoke verliert bei billigen Linien und bei teurem Umschlag gegen Alles direkt. Die Lage der Schwellen erklärt die Ungleichung nicht, denn Hub-and-Spoke legt alle Sendungen gleichzeitig um, auch solche ohne freie Kapazität auf den Linien.

Warum Einzelschritte nicht reichen. Die Lkw-Zahl ist eine Treppenfunktion der Menge. Trägt eine Linie in einer Richtung die Menge \(r\) anderer Sendungen und zwei weitere Sendungen \(a\) und \(b\), und gilt \(r \le \mathrm{cap}\), \(r + q_a > \mathrm{cap}\), \(r + q_b > \mathrm{cap}\) sowie \(r + q_a + q_b \le 2\,\mathrm{cap}\), braucht sie zwei Lkw. Legt man \(a\) allein oder \(b\) allein auf Routen um, die diese Linie nicht nutzen, bleibt es bei zwei Lkw. Erst beide zusammen senken die Lkw-Zahl der Linie auf eins. Eine Suche, die nur einzelne Sendungen umlegt, sieht diese Verbesserung nicht. Das ist der Mechanismus, für den der paarweise Politurschritt gebaut wurde. Dass die gemessenen Verbesserungen auf ihm beruhen, ist nicht einzeln geprüft.

Was die beiden Kipp-Tabellen zusätzlich verraten. Eine Lösung, die bei höheren Umschlagkosten gefunden wurde, kostet bei niedrigeren Umschlagkosten nicht mehr als dort. Die Greedy-Kosten bei 5 € je Einheit (9.693 €) liegen aber über denen bei 8 € je Einheit (9.578 €). Das Optimum bei 5 € ist deshalb höchstens 9.578 €, und Greedy liegt in dieser Zeile mindestens gut ein Prozent darüber. Auch der Rückgang der Ersparnis von 25 auf 30 € je Kilometer (41,9 % auf 40,1 %) ist kein wirtschaftlicher Effekt: Eine Nachrechnung dieser Seite mit einem anderen exakten Löser (HiGHS über SciPy, nicht Teil der Demo) liefert für alle sieben Zeilen das Optimum. Die Ersparnis des Optimums gegenüber Alles direkt steigt über alle sieben Zeilen weiter. Die Lücke von Greedy ist bei 30 € je Kilometer mit gut viereinhalb Prozent die größte der sieben Zeilen. In vier der sieben Zeilen (2, 5, 20 und 25 € je Kilometer) trifft Greedy das Optimum.

Befunde

Die Kostenzeilen stammen aus einer einzigen Zufallsinstanz mit 7 Depots und der Dichte 0,5 (Instanz Nr. 7 der Erzeugung), nicht aus einem Mittel. Kosten sind Gesamtkosten in Euro für das tägliche Netz. Nur die Lückenwerte beziehen sich auf 20 Instanzen mit 7 Depots und Fixkosten von 15 € je Kilometer; bei anderen Fixkosten ergeben sich andere Lücken.

Frage	Befund
1 · Wo kippt Hub-and-Spoke gegen Alles direkt? Fixkosten 2 / 5 / 10 / 15 / 20 / 25 / 30 € je Linie und Kilometer, Umschlag 1,5 € je Einheit	Alles direkt: 3.558 / 6.080 / 10.283 / 14.487 / 18.690 / 22.893 / 27.097 €. Hub-and-Spoke: 4.356 / 6.167 / 9.186 / 12.204 / 15.223 / 18.242 / 21.260 €. Greedy: 2.929 / 4.345 / 6.883 / 9.200 / 11.102 / 13.312 / 16.239 €. Hub-and-Spoke ist bei 2 und 5 € je Kilometer teurer als Alles direkt, ab 10 € je Kilometer billiger.
2 · Wie viel spart Greedy gegenüber Alles direkt? (dieselben Zeilen)	17,7 / 28,5 / 33,1 / 36,5 / 40,6 / 41,9 / 40,1 %. Bei 2 € je Kilometer trifft Greedy mit 2.929 € das Optimum.
3 · Wirkt der Umschlag? Umschlagkosten 0,5 / 1 / 2 / 5 / 8 / 12 € je Einheit, Fixkosten 15 € je Kilometer	Hub-and-Spoke: 11.964 / 12.084 / 12.324 / 13.045 / 13.766 / 14.728 €. Greedy: 8.752 / 9.140 / 9.247 / 9.693 / 9.578 / 9.894 €. Ersparnis von Greedy gegenüber Alles direkt (14.487 €): 39,6 / 36,9 / 36,2 / 33,1 / 33,9 / 31,7 %. Bei 12 € je Einheit ist Hub-and-Spoke teurer als Alles direkt (14.728 gegen 14.487 €), bei 8 € je Einheit noch billiger (13.766 €).
4 · Wie weit liegt Greedy vom Optimum? 20 Instanzen mit 7 Depots, Fixkosten 15 € je Kilometer, 4 Entwicklungsstufen der Suche	Mittlere Lücke: 4,4 % (Suche nur vom besten Einzel-Hub) → 3,5 % (alle Einzel-Hubs als Start) → 3,0 % (zusätzlich Grenzkosten-Konstruktion als Start) → 1,6 % (zusätzlich paarweiser Politurschritt). Größte Lücke: 13,4 % → 10,8 % → 9,8 % → 7,7 %. Der Politurschritt verbessert 9 von 20 Instanzen.
5 · Einzelne Instanzen	Instanz 2: 6.767 € bei Suche nur vom besten Hub, 6.425 € von allen Hubs aus (5,1 % weniger). Instanz 1: 6.913 € ohne Grenzkosten-Konstruktion, 6.508 € mit ihr, das ist das Optimum. Instanz 7: 9.765 € → 9.200 € durch den Politurschritt, die Lücke sinkt von 9,8 % auf 3,5 %. Die reine Grenzkosten-Konstruktion verliert in 18 von 20 Instanzen gegen das mehrfach gestartete Greedy.
6 · Wie lange rechnet der exakte Löser? 3 Instanzen je Zelle, Messbedingungen der Quelle unklar	6 Depots: 0,06 bis 0,30 s je nach Dichte (0,5 bis 1,0). 8 Depots: 0,52 bis 2,23 s. 9 Depots: 0,73 s (Dichte 0,5) und 1,54 s (0,7), dann 14,08 s (0,9) und 19,75 s (1,0). Die Quelle nennt die Messung zugleich „ohne Zeitlimit“ und bei einer Instanz der letzten Zelle „nicht bewiesen optimal“; beides passt nicht zusammen, die Zeiten sind daher nur als Größenordnung zu lesen. Bei 9 Depots brauchte eine Instanz mit 26 Sendungen 5,0 s, eine mit 32 Sendungen 2,4 s: Die Schwierigkeit hängt nicht sauber an der Größe.
7 · Wie oft beweist der exakte Löser das Optimum in 4 s? 6 bis 9 Depots, 4 Dichten, 80 Instanzen	In 70 von 80 Instanzen. Die übrigen 10 liegen alle bei 9 Depots und Dichte 0,9 oder mehr; dort liefert der Löser die beste gefundene Lösung ohne Beweis.
8 · Rechenzeit der paarweisen Suche (9 Depots, höchste Dichte)	Mit vollständiger Neubewertung je Paar bis 7,5 s, mit inkrementeller Bewertung höchstens 1,8 s. Das sind Zeiten der Entwicklung auf einem nicht genannten Rechner; auf anderer Hardware kann es mehr sein, eine Nachmessung ergab etwa das Doppelte, und die Demo testet gegen 4 s. Die inkrementelle Änderung stimmt auf 300 zufälligen Kandidatenpaaren mit der vollständigen Neubewertung überein.

Was die Messung zeigt und was nicht

Was sie belegt:

• Die Umsetzung hält ihre Konstruktionsgarantie: In allen Zeilen der beiden Kipp-Tabellen ist Greedy nicht teurer als die beiden einfachen Regeln. Das ist kein Messbefund über die Wirklichkeit, sondern folgt aus den Startpunkten.
• Die Richtung der Kipppunkte: Billige Linien und teurer Umschlag machen Hub-and-Spoke gegenüber Alles direkt schlechter. Das stützen die Rechnung weiter oben und die Messzeilen. In der Einzelinstanz liegt der Kipppunkt in den Fixkosten zwischen 5 und 10 € je Kilometer, im Umschlag zwischen 8 und 12 € je Einheit.
• Die Größenordnung des Abstands zum Optimum: im Mittel 1,6 % über 20 Instanzen, größte Lücke 7,7 %. Das gilt für Fixkosten von 15 € je Kilometer; bei anderen Fixkosten sind die Werte anders. Eine Nachrechnung dieser Seite mit einem anderen exakten Löser (HiGHS) auf den Instanzen 1 bis 20 bestätigt die Optimalwerte und damit beide Lückenwerte. Sie prüft die Optima, nicht die Suche selbst, und ersetzt keine frischen Testinstanzen.

Was sie nicht belegt, und Grenzen:

• Eine einzige Instanz: Die Kostenzeilen (Fixkosten, Umschlag) gehören zu einem einzigen Zufallsnetz. Auf anderen Netzen können die Kipppunkte anderswo liegen, und der Verlust von Hub-and-Spoke bei billigen Linien ist dort nicht gemessen. Ein Mittel über viele Instanzen gibt es nur für die Lücke zum Optimum.
• Die Lücke ist nicht außerhalb der Stichprobe geprüft: Die Suche wurde schrittweise an denselben 20 Instanzen verbessert, an denen die Lücke gemessen wurde. Der Wert von 1,6 % kann deshalb zu günstig sein (Deutung dieser Seite, nicht gemessen). Eine Streuung ist nicht angegeben.
• Greedy ist eine Heuristik: Die Nicht-Monotonie in der Umschlag-Tabelle und der Rückgang bei 30 € je Kilometer zeigen Zeilen, in denen Greedy das Optimum verfehlt. Dreier- oder größere Tauschzüge und die paarweise Suche als zusätzlicher Startpunkt wurden bewusst nicht gebaut, ihr Nutzen ist ungeprüft.
• Das Optimum gilt für das Modell: Es erlaubt höchstens einen Umschlag je Sendung. Ob zwei Umschläge billiger wären, zeigt die Demo nicht. Ob die auf einen Umschlag beschränkte Fassung ebenfalls NP-schwer ist, behauptet diese Seite nicht. Bei Zeitablauf ist die angezeigte Lösung des exakten Lösers nur die beste gefundene, die Lücke zu ihr ist dann keine Lücke zum bewiesenen Optimum.
• Modellannahmen: Die Nachfrage ist bekannt und jeden Tag gleich, je Paar gibt es nur eine Nachfragerichtung. Auf Linien, die Umwegrouten tragen, fahren dennoch Mengen in beide Richtungen, und ein Lkw deckt beide ab. Die Rückrichtung einer Linie, die nur ein Direktpaar bedient, bleibt ungenutzt. Es gibt keine Zeitfenster, keine Umlaufplanung der Lkw, keine Hub-Kapazität und keine Kosten für den Betrieb eines Zwischendepots. Die Fixkosten wachsen linear mit der Entfernung. Kostenparameter und Gebiete sind erfunden und nicht an einem echten Netz kalibriert.
• Kennzahlen der Demo: Die Auslastung in der Vergleichstabelle summiert die Mengen beider Richtungen und teilt durch die Kapazität einer Richtung. Sie kann deshalb über der vollen Auslastung liegen (Rechnung dieser Seite am Ausgangsfall bei Hub-and-Spoke). Die Hauptansicht zeigt zwar die billigste Heuristik, rechnet die Ersparnis aber gegen die teuerste der drei Heuristiken, nicht immer gegen Alles direkt. Bei 2 € je Kilometer ist das Hub-and-Spoke, und die Ersparnis dort beträgt etwa ein Drittel statt der 17,7 % der Tabelle gegenüber Alles direkt (Rechnung dieser Seite).
• Kostenanteile: Im Ausgangsfall machen die Fixkosten der Linien bei allen drei Regeln mehr als zwei Drittel der Gesamtkosten aus (Rechnung dieser Seite aus der Kostenaufschlüsselung der Demo). Bei anderen Reglerwerten für die Kosten je Einheit kann sich das ändern.

Erweiterungen und Verweise

Nicht modelliert sind unter anderem mehrere Umschläge je Sendung (allgemeiner Mehrgüterfluss mit beliebig langen Pfaden), Nachfrage in beide Richtungen eines Paares, Fahrpläne mit Takt und Zeitfenstern, begrenzte Umschlagkapazität und schwankende Nachfrage. Zur Frage, was passiert, wenn die Nachfrage nicht bekannt ist:

• Schwankende Nachfrage: Die Seite Netzdesign bei Unsicherheit vergleicht die Planung für eine Punktschätzung mit der Planung für mehrere Nachfrage-Szenarien. Hier ist die Nachfrage bekannt.

Quellen

• Magnanti, Wong (1984): Network design and transportation planning: Models and algorithms. Transportation Science 18(1), 1–55.
• Crainic (2000): Service Network Design in Freight Transportation. European Journal of Operational Research 122(2), 272–288.
• Lemons et al. (2022): Beam Search: Faster and Monotonic. ICAPS 2022. Beam Search (Strahlsuche mit festem Kandidatenpool) wurde als Vorbild für eine sequenzielle Konstruktion erwogen; getestet wurde nur die einfachere Grenzkosten-Konstruktion (Befund 4 und 5), der Beam-Apparat selbst wurde nicht gebaut.
• Exakter Löser: SCIP über Google OR-Tools. Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/linehaul-demo.

Autoren, Jahr und Titel der ersten drei Quellen stammen aus der Dokumentation der Demo. Zeitschrift, Band und Seitenzahlen der ersten beiden Quellen stammen aus dem Gedächtnis und wurden für diese Seite nicht nachgeschlagen. Die Lager und der Paketdienst im ersten Teil sind erdacht, ebenso das Beispiel mit drei Lagern. Die Rechnungen im zweiten Teil sind Rechnungen dieser Seite und keine Messungen der Demo.