OR-Labor

Das Transportproblem in der Betriebswirtschaftslehre

Problemformulierung

Allgemein formuliert lautet das Transportproblem: Ein homogenes Gut, das an den Orten Ai (i=1,...,m) in den Mengen ai angeboten wird, soll zu den Orten Bj (j=1,...,n) transportiert werden, an denen eine Nachfrage von bj besteht. Die Kosten des Transportes einer Mengeneinheit (ME) von Ort Ai zum Ort Bj betragen cij. Wieviele ME sollen vom Ort Ai zum Ort Bj transportiert werden, so dass die Nachfrage erfüllt wird und die Gesamttransportkosten minimal sind ?

Ohne Einschränkung der Allgemeinheit kann man annehmen, dass eine Transportverbindung von jedem Ort Ai zu jedem Ort Bj existiert. Soll auf einer Verbindung auf keinen Fall ein Transport stattfinden (was gleichbedeutend mit dem Fehlen der Verbindung ist), so erreicht man dies durch die Definition unendlich hoher Transportkosten.

Das Problem der Transportkostenminimierung wird in dieser Form allgemein als das klassische Transportproblem bezeichnet. Das Adjektiv klassisch hat angesichts der historischen Bedeutung dieses Problems durchaus seine Berechtigung, denn die Formulierung als mathematisches Modell und seine Analyse mit Hilfe mathematischer Verfahren kann man als eine der ersten OR-Studien überhaupt ansehen. DANTZIG (1966), der selbst maßgeblich Anteil an der Behandlung der Transportprobleme hatte, skizziert die Meilensteine dieser Entwicklung.

Anwendungen

Verschiebung von Eisenbahnwaggons
Die Verteilung leerer Güterwaggons stellt ein aus betriebswirtschaftlicher Sicht interessantes Optimierungsproblem dar, nicht zuletzt weil jede Bahngesellschaft daran interessiert sein muss, die Anzahl der Leerfahrten zu minimieren.
Formuliert man die Aufgabe als Transportproblem mit m Ausgangs- und n Zielorten, wobei die »Anbieter« Ai am Abend eines Tages eine Anzahl von Waggons in ihren Bahnhöfen stehen habe, die am nachfolgenden Tag von den »Nachfragern« Bj benötigt werden. Die Waggons müssen im sogenannten Nachtsprung verschoben werden. Hauptziel ist die Deckung aller Bedarfe und damit die maximale Zufriedenheit der Kunden.
Für eine konkrete Fragestellung zu den Güterbahnhöfen von Darmstadt, Mainz, München, Saarbrücken, Essen, Bremen, Hamburg und Lübeck besteht die Möglichkeit mit einem Applet dieses Problem experimentell mit verschiedenen, im Kurs 000852-KE2 vorgestellten Algorithmen zu lösen.
Literatur

Applet-Seite

Es wurde von uns ein Applet programmiert, mit dem es möglich ist, das Transportproblem mit unterschiedlichen Algorithmen zu lösen. Implementiert sind die Eröffnungsverfahren »Zeilenfolge-Methode«, »Zeilen-Spalten-Minimum-Methode«, »Matrix-Minimum-Methode« und »Vogels-Approximations-Methode«.