Transportproblem

Das Transportproblem ist eine Fragestellung aus dem Operations Research: Zum Transport einheitlicher Objekte von mehreren Angebots- zu mehreren Nachfrageorten ist ein optimaler, d.h. kostenminimaler Plan zu finden, wobei die vorhandenen und zu liefernden Mengen an den einzelnen Standorten gegeben sowie die jeweiligen Transportkosten pro Einheit zwischen allen Standorten bekannt sind.

Bereits 1781 formulierte Monge ein allgemeines Transportproblem mathematisch.^[1] Beim Standardfall einer bezüglich der Transportmengen linearen Kostenfunktion handelt es sich um ein Problem der linearen Optimierung, für das neben den Standardmethoden wie Simplex-Verfahren spezielle Lösungsalgorithmen existieren. Als eines der ersten Themengebiete des Operation Research wurde das Problem schon 1939 von Kantorowitsch als mathematisches Modell formuliert. In den 1950er entwickelten Dantzig, Charnes und Cooper sowie Ford und Fulkerson verschiedene Lösungsalgorithmen.

Das klassische Transportproblem ohne Kapazitätsbeschränkungen auf den Transportwegen ist ein Spezialfall des kapazitierten Transportproblems, das für Wege Mindest- oder Höchsttransportmengen festlegt. Klassisches und kapazitiertes Transportproblem sind wiederum Spezialfälle des (kapazitierten) Umladeproblems, bei dem es neben Angebots- und Nachfrageorten noch reine Umladeorte gibt. Ein Sonderfall des Transportproblems ist das Zuordnungsproblem, bei dem an jedem Ort nur eine Einheit angeboten bzw. nachgefragt wird.

Mathematische Formulierung des klassischen Transportproblems

Das klassische Transportproblem ohne Kapazitätsbeschränkungen wird durch folgende Daten beschrieben: m Angebotsorte A_i stellen Mengen von a_i des Gutes (i = 1,...,m) bereit, n Nachfrageorte B_j fragen das Gut in den Mengen b_j nach (j = 1,...,n). Die Mengen müssen größer oder gleich null sein, zudem muss das Gesamtangebot gleich der Gesamtnachfrage sein. Ist dies im ursprünglichen Problem nicht der Fall, ist ein fiktiver Angebots-, bzw. Nachfrageort einzuführen, der die Überschussnachfrage bereitstellt, bzw. die Überschussnachfrage aufnimmt. Des Weiteren sind – zum Beispiel in einer Matrix C – die nicht-negativen Kosten c_ij für den Transport einer Mengeneinheit von Angebotsort A_i zum Nachfrageort B_j gegeben. Transportkosten von bzw. zu einem fiktiven Ort werden auf Null gesetzt. Kann zwischen zwei Orten nichts transportiert werden, so sind die entsprechenden Transportkosten unendlich.

Formulierung als lineares Programm

Im Transportplan bezeichnet x_ij die Transportmenge, die von A_i nach B_j transportiert wird. Die Gesamtkosten ergeben sich, indem man für jeden Transportweg die ermittelte Transportmenge mit den Kosten für den Transport auf dem jeweiligen Transportweg multipliziert und diese Produkte summiert. Gesucht ist ein Transportplan mit minimalen Kosten, der die Beschränkungen hinsichtlich der lieferbaren Mengen einhält und die Nachfrage an allen Nachfrageorten erfüllt. Mit den eingeführten Bezeichnern ergibt sich dann das mathematische Modell des Transportproblems:

Minimiere die Zielfunktion $z = \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}$

unter den Nebenbedingungen

1. $\sum_{j=1}^n x_{ij} = a_i \quad \forall i$
2. $\sum_{i=1}^m x_{ij} = b_j \quad \forall j$
3. $x_{ij} \geq 0 \quad \forall i\forall j$

Die erste Nebenbedingung beschreibt, dass das Angebot an jedem Angebotsort komplett abgerufen werden soll, während die zweite für jeden Nachfrageort festlegt, dass die Nachfrage vollständig erfüllt werden soll. Alle Transportmengen müssen nichtnegativ sein. Oftmals wird auch die Ganzzahligkeit der Transportmengen gefordert, d.h. $x_{ij} \in \mathbb{N}_0$.

Falls die zu Beginn aufgeführten Bedingungen ($a_i \geq 0,\ b_j \geq 0,\ c_{ij} \geq 0 {\rm \ und\ } \sum a_i = \sum b_j$) erfüllt und alle Wege benutzbar sind ($c_{ij} \neq \infty \ \forall i\forall j$), so existiert mindestens eine Lösung für das Transportproblem. Kann zwischen einigen Orten nichts transportiert werden, so ist die Existenz einer Lösung nicht gesichert.

Formulierung als Min-Cost-Flow-Problem

Mit Hilfe von Graphen kann das Problem auch als Min-Cost-Flow-Problem formuliert werden. Dabei geht es darum, in einem Graphen mit Kantenkosten zwischen zwei Knoten einen kostenminimalen Fluss mit gegebenem Flusswert zu finden. Jeder Ort wird hierbei durch einen Knoten repräsentiert, und von jedem Angebotsort zu jedem Nachfrageort wird eine Kante gezogen, deren Kosten den Transportkosten entsprechen. Zusätzlich werden zwei besondere Knoten s und t eingeführt. Knoten s wird mit allen Angebotsorten verbunden und t mit allen Nachfrageorten, wobei diese Kanten den Kostenwert 0 haben. Anschließend wird ein kostenminimaler Fluss mit der Gesamtnachfrage als Flusswert von s nach t bestimmt. Der ermittelte Fluss auf der Kante zwischen A_i und B_j gibt an, wie viel zwischen diesen beiden Orten transportiert wird.

Beispiel

Ein Getränkeproduzent hat einen einmaligen Auftrag zur Lieferung von 30 Tankladungen eines speziellen Getränks erhalten, das an den Produktionsstätten Hamburg (16 Ladungen) und Paris (14 Ladungen) auf Lager liegt. Laut Auftrag sollen 15 Ladungen nach Lissabon, 5 nach Barcelona und 10 nach Florenz geliefert werden. In der Kalkulation wurden daraufhin überschlägig die Transportkosten je Tankladung ermittelt. Folgende Tabelle fasst die Datensituation zusammen:

Entfernung und Transportkosten je Tankladung (TL)

von \ nach	Lissabon (B1)	Barcelona (B2)	Florenz (B3)	Angebot
Hamburg (A1)	2800 km	1800 km	1400 km	16 TL
	6 T€	4 T€	3 T€
Paris (A2)	1900 km	1100 km	1100 km	14 TL
	3 T€	2 T€	2 T€
Nachfrage	15 TL	5 TL	10 TL	30 TL

Da die hinreichenden Bedingungen für die Existenz einer Lösung gegeben sind, existiert mindestens ein Transportplan für dieses Transportproblem. Gesucht ist nun eine optimale Lösung zu folgendem linearen Optimierungsproblem:

Minimiere

z = 6x₁₁ + 4x₁₂ + 3x₁₃ + 3x₂₁ + 2x₂₂ + 2x₂₃

unter den Nebenbedingungen

1. Angebot
   • x₁₁ + x₁₂ + x₁₃ = 16
   • x₂₁ + x₂₂ + x₂₃ = 14
2. Nachfrage
   • x₁₁ + x₂₁ = 15
   • x₁₂ + x₂₂ = 5
   • x₁₃ + x₂₃ = 10
3. Keine negativen Transporte
   • $x_{ij} \geq 0$

Hier bezeichnet beispielsweise x₂₁ die Menge, die von Paris (A₂) nach Lissabon (B₁) transportiert werden soll.

Lösungsverfahren

Exakte Verfahren

In der oben vorgestellten Formulierung als lineares Programm lässt sich das Problem beispielsweise mit dem Simplex-Verfahren optimal lösen. Sofern die Angebots- und Nachfragemengen ganzzahlig sind und eine zulässige Lösung existiert, liefert das Simplex-Verfahren für dieses spezielle Problem immer eine ganzzahlige Lösung, da aufgrund der vollständigen Unimodularität der Nebenbedingungsmatrix jede Ecke des zugehörigen Polyeders ganzzahlig ist. Für dieses Problem kann statt des allgemeinen Simplex-Verfahrens auch die Netzwerk-Simplexmethode verwendet werden, eine schnellere Variante, die speziell für Min-Cost-Flow-Probleme geeignet ist.

Alternativ kann das Problem auch mit einem beliebigen kombinatorischen, also nicht auf linearer Optimierung beruhenden Algorithmus zum Finden kostenminimaler Flüsse gelöst werden.

Eröffnungsheuristiken

Mehrere iterative Verfahren suchen erst mit Hilfe einer einfachen Eröffnungsheuristik eine zulässige Ausgangslösung (auch Basislösung genannt) und versuchen dann, diese durch eine Verbesserungsheuristik zu verbessern. Folgende Verfahren werden hierbei üblicherweise als Eröffnungsheuristik verwendet (nach Aufwand geordnet):

• Nord-West-Ecken-Verfahren
• Matrixminimumverfahren (auch Rangfolgeverfahren, aufsteigende Indexmethode oder Spaltenminimum-Methode^[2])
• Vogelsche Approximationsmethode (VAM, VAV)

In den meisten Fällen führt die relativ aufwändige Vogelsche Approximationsmethode relativ schnell eine optimale Lösung herbei. In der Datenverarbeitung wird häufig die Nord-West-Ecken-Methode bevorzugt, weil sie einfacher zu programmieren ist und die Zahl der benötigten Iterationen nicht ins Gewicht fällt.

Verbesserungsverfahren

Aus einer zulässigen Startlösung kann iterativ eine Optimallösung konstruiert werden. Als Verfahren kommen beispielsweise in Frage

• die Stepping-Stone-Methode (Sprungbrettmethode)
• die MODI-Methode, auch Potentialverfahren genannt.

Bei beiden Methoden werden einzelne Zellen der Tabelle überprüft, inwieweit ihre Änderung eine Verbesserung der Kostensituation herbeiführt. Dabei pflanzt sich die Änderung in andere Zellen fort. Diese Änderungen können als geschlossener Kreis beschrieben werden. Es werden so oft Zellen geändert, bis keine Verbesserung mehr möglich ist und das Optimum erreicht worden ist. Die MODI-Methode führt in endlich vielen Schritten zu einer Optimallösung, wenn die oben genannten Bedingungen erfüllt sind. Mit ihr wird die optimale Lösung im allgemeinen schneller gefunden als mit der Stepping-Stone-Methode.

Quellen

1. ↑ G. Monge. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. 1781, S. 666–704.
2. ↑ W. Domschke. Transport: Grundlagen, lineare Transport- und Umladeprobleme 2007, S. 106-108.

Weblinks

• Fernuni Hagen: Das Transportproblem in der Betriebswirtschaftslehre
• Transportproblem: Transportproblem in Javascript