Mehrere Werke, mehrere Kunden — Wie viel liefert jedes Werk an jeden Kunden, damit die Gesamtfracht minimal wird?

Anmerkung der Redaktion

Auf der operativen Ebene heißt dieses Problem “Flussplan”, “Sendungsaufteilung” oder “Werk-Kunden-Matrix”. Der akademische Name lautet Transportproblem, in manchen Quellen auch Hitchcock-Problem oder Hitchcock-Koopmans-Problem. Frank Hitchcock definierte das Problem 1941 in numerischer Form an seinem MIT-Papier; Tjalling Koopmans formulierte 1947 unabhängig eine ökonomische Fassung (zitiert beim Nobelpreis Wirtschaft 1975); George Dantzig entwickelte 1951 die Simplex-Methode speziell an diesem Problem. Es ist das Gründungsproblem der linearen Programmierung und Vorfahre der nächsten Generation — TSP, VRP, Fahrzeugrouting — die darauf aufbauten.

Unterschied zu VRP (#002, #069) ist entscheidend: VRP ist Fahrzeugrouting — eine Depot-Kunde-Kunde-Depot-Tour, in welcher Reihenfolge welches Fahrzeug welche Kunden besucht. Das Transportproblem ist Flussallokation: wie viele Einheiten jedes Werk an jeden Kunden liefert; keine Route, nur Menge. Beide sind komplementär — zuerst entscheidet das Transportproblem den wöchentlichen Fluss, dann VRP das Tagesrouting. Sie laufen in derselben Kette nacheinander. Unterschied zur Standortplanung (#010): Standortplanung ist die Entscheidung über die Eröffnung eines neuen Werks/Lagers (mit festen Eröffnungskosten); Transportproblem ist Flussallokation über bestehende Standorte (keine Eröffnungskosten). Unterschied zu p-Median (#074): p-Median wählt eine feste Anzahl von Standorten, das Transportproblem nimmt bestehende Standorte als gegeben.

Am häufigsten übersehener Punkt: Dual-Variablen und Schattenpreise. Die primalen Flüsse (wie viele Tonnen jedes Werk an jeden Kunden liefert) sind die Ausgabe, die der Praktiker sieht; die Dual-Variablen weisen jeder Quelle und jedem Ziel einen Schattenpreis zu — “wenn die Kapazität von Werk i um 1 Tonne steigt, wie viel sinken die Gesamtfrachtkosten”, “wenn der Bedarf von Kunde j um 1 Tonne steigt, wie viel steigen die Gesamtkosten”. Direkter Input für Investitionsentscheidungen: welches Werk profitiert am meisten von einer Kapazitätserweiterung, welcher Kunde hat marginale Frachtkosten höher als andere. Praktiker nutzen meist nur primale Flüsse und lesen die Duale nicht — ein kritischer Verlust für Kapazitätsinvestitionspriorisierung. Zweiter übersehener Punkt: das unbalancierte Problem. In Wirklichkeit ist die Gesamtkapazität selten exakt gleich der Gesamtnachfrage (Überkapazität oder Unterproduktion). Der Solver fügt eine Dummy-Quelle oder ein Dummy-Ziel hinzu — diese Zeile/Spalte ist der Leerkapazitäts-Report; wenn übersehen, bleibt unklar, wofür die Leerkapazität steht.

Schritt-für-Schritt für ein KMU

Phase 1 — Erst messen, dann planen. Mindestens 6-12 Monate Daten: monatliche Liefermenge pro Werk-Kunde-Paar, Stückfrachtkosten (Entfernung + Fahrzeugtyp + Vertrag), wöchentliche Werkskapazität, wöchentlicher Kundenbedarf. Kostenmatrix als separate Tabelle aufbauen — Zeilen Werke, Spalten Kunden, Zellen TRY/Tonne. Kritisch: Hat sich der Treibstoffpreis in den letzten 12 Monaten geändert — wurde die Kostenmatrix aktualisiert? Wenn nein, zeigt schon der erste LP-Lauf 5-10 % Ersparnis.

Phase 2 — Wissenskapital extrahieren. Listen Sie auf, welche Werke physisch-unmöglich für welche Kunden sind (Entfernung, Produktpassung, Vertragsklausel) — diese Restriktionen gehen als ‘verbotene Zellen’ (große Kosten) ins Modell. Werkskapazität: reale Dauerkapazität oder mit Wartungsfenstern? Kundenbedarf: stabil oder saisonal?

Phase 3 — Pilot. 8-12 Wochen. LP-Modell für eine Subregion (z. B. eine Produktlinie oder ein regionales Kundenset) aufbauen, Solver laufen lassen und Ergebnis parallel zur aktuellen manuellen Zuteilung vergleichen. Entscheidung bleibt beim Planer; LP gibt Empfehlung. Erfolgskriterium schriftlich vor Pilotbeginn: Gesamtfrachtkosten mindestens 10 % runter, Leerkapazitäts- oder unbefriedigter-Nachfrage-Report klar. Dual-Variablen-Tabelle als separate Ausgabe einfordern — Gold für Kapazitätsinvestitionen.

Phase 4 — Rollout. Über 6-12 Monate auf alle Produktlinien und Regionen ausweiten. Zu monatlichem Neulösen übergehen — Treibstoffwechsel, neuer Kunde, Kapazitätswartung als Trigger. Vierteljährliches Planungskomitee: realisierte Flüsse vs. Plan, Dual-Variablen-Report (Schattenpreis), Datum der Kostenmatrix-Auffrischung.

Risiken — was schiefgehen kann

1. Werkskapazität schwankt in Echtzeit. Statisches LP-Modell nimmt Wochen- oder Monatskapazität fest; Wartung, Schichtausfall, Rohstoffunterbrechung verschieben sie täglich. Lösung: kürzere (wöchentliche) Neulös-Frequenz plus Sicherheitsmarge unter der Durchschnittskapazität.
2. Kostenmatrix wird nicht aktualisiert. Treibstoff +20 % aber Matrix auf 2 Jahre alten Zahlen — LP optimiert eine veraltete Matrix und verliert real Geld. Lösung: Kostenmatrix alle 3 Monate auffrischen (Treibstoff + Frachtvertrag + Fahrzeugkosten).
3. Kunden-Sonderwünsche nicht modelliert. Manche Kunden haben Lieferzeitfenster, Paketgrößen-Restriktion oder Produktmischregel — reines Transportproblem trägt das nicht; muss an VRP- oder Planungs-Schicht weitergegeben werden. Technisch korrekter LP-Fluss kann operativ unmöglich sein.
4. Anbieterabhängigkeit (WMS/TMS-Lock-in). Wenn die Software Quelle-Ziel-Definitionen, Kostenmatrix und Lösungshistorie in proprietärem Format hält, bedeutet Wechsel den Verlust des Fluss-Gedächtnisses. Vertragsklausel: ‘jährlicher Export der Flussmatrix-Historie und Kostenmatrix im Standardformat’."

Technischer Blick auf die Lösungsmethode

Wahl der Zielfunktion:

• Ziel 1 — Gesamtfrachtkosten minimal: Klassisch. FMCG, Rohstoff-Lohnnäher-Ketten.
• Ziel 2 — Gesamtstrecke oder Treibstoff minimal: Bei CO₂-Fokus oder treibstoffintensiven Operationen.
• Ziel 3 — Servicezeit gewichtet minimal: Schnellverteilung (Lebensmittel, Kühlkette).
• Ziel 4 — Gewichteter Mix: Fracht + Service + Strafe: Kundenbasis mit Vertragsstrafen bei verspäteter Lieferung.

Das Zuordnungsproblem ist ein Spezialfall des Transportproblems: Quelle = Ziel, jede Quelle zu genau einem Ziel (Kapazität = Bedarf = 1, x_ij binär). Personal-Aufgabe-Zuordnung, Maschine-Auftrag-Zuordnung, Schiff-Liegeplatz-Zuordnung (Unter-Schicht des BAP in #026), Knoten-Matching-Probleme haben diese Form. Die ungarische Methode (Kuhn 1955) löst das Zuordnungsproblem in O(n³) — viel schneller als der allgemeinere Simplex auf denselben Daten, aber nur für den Spezialfall Zuordnung.

Mehrperioden-Erweiterung: x_ijt — Menge von Werk i an Kunde j in Periode t; pro Periode eigene Kapazität und Bedarf, mit Zwischenperioden-Bestandskosten. Wächst zum Mehrperioden-Produktions-Distributions-Planungs-Problem — behält das Transportproblem im Kern, fügt Lot-Sizing- und Bestands-Schichten hinzu.

Stochastische Erweiterung: d_j ist Zufallsvariable; die Lösung liefert eine Allokation, die in keinem Szenario die Kapazität sprengt und die erwarteten Kosten minimiert — stochastisches LP oder szenariobasiertes MIP.

Akademische Quellen

Im sources-Block dieses Dokuments aufgelistet. Hitchcock (1941) und Koopmans (1947) sind die beiden Gründungspapiere; Dantzig (1951) entwickelte die Simplex-Methode an genau diesem Problem. Bazaraa-Jarvis-Sherali (2010) und Murty (1992) sind moderne Lehrbuchreferenzen. INFORMS und das Archiv des European Journal of Operational Research tragen viele Einsatzfälle in Lieferketten und Produktions-Distributions-Netzwerken.