Die Vogelsche Approximationsmethode ist ein heuristisches Verfahren, das vor allem in der Distributionslogistik Anwendung findet, beispielsweise um ein Transportproblem zu lösen. Es gehört zum Bereich der mathematisch orientierten Statistik, engl. Operations Research. Die Methode kommt dem gewünschten Optimum sehr nahe, allerdings ist der Aufwand im Vergleich zu anderen mathematischen Verfahren wesentlich höher.

Die zentrale Problemstellung in der Distributionslogistik ist, möglichst günstig ein Gut von A nach B zu transportieren. Dabei geht es nicht nur um die reine Strecken- beziehungsweise Routenplanung, sondern hinsichtlich der operativen Planung auch um Kriterien, die die Einrichtung von Distributionszentren und Produktionsstandorten betreffen. Wenn beispielsweise ein Unternehmen in mehreren Werken ein bestimmtes Produkt herstellt, das an verschiedene Standort geliefert wird, dann lässt sich mit der Vogelschen Approximationsmethode herausfinden, welche Transportwege unter welchen Bedingungen nahezu optimal wären.

Vogelsche Approximationsmethode in der Praxis

Beim Lösen eines Transportproblems fungiert die Vogelsche Approximationsmethode als Basislösung, die dann mit weiteren Optimierungsverfahren eine kostenoptimierte Näherungslösung findet. Das Transportproblem ist, wie oben erwähnt, eine Fragestellung aus dem Operations Research. Sie befasst sich damit, einen kostenminimalen (optimalen) Weg zu finden, der den Transport einheitlicher Objekte von mehreren Angebotsorten zu mehreren Nachfrageorten vorgibt. Gegeben sind dabei die vorhandenen und zu liefernden Mengen an den jeweiligen Standorten. Die entsprechenden Transportkosten pro Einheit zwischen allen Standorten sind ebenso bekannt. Weitere heuristische Verfahren, die im Operations Research die Lösung des Transportproblems behandeln, sind das Nord-West-Ecken-Verfahren und das Matrixminimumverfahren.

Vogelsche Approximationsmethode: der Algorithmus Schritt für Schritt

Die feststehenden Daten sind die Angebots- und Nachfragestandorte und deren entsprechende Kapazitäten beziehungsweise Bedarfe. Eingetragen werden die zu liefernden Einheiten (siehe dazu auch die Videos).

1. Zuerst wird eine Hilfsmatrix mit den Opportunitätskosten erstellt. Diese ergeben sich aus der Differenz der beiden kleinsten Werte der jeweiligen Zeile und Spalte.

2. Anschließend wird daraus die Zeile oder Spalte mit den höchsten Opportunitätskosten herausgesucht.

3. Dann sucht man den niedrigsten Wert aus dieser Zeile oder Spalte heraus. In der Ursprungsmatrix werden nun diesem Feld die maximal möglichen Kapazitäten zugeordnet.

4. In der Ursprungsmatrix wird die betreffende Spalte oder Zeile mit Nullen aufgefüllt und in der Hilfsmatrix gestrichen, sobald die Angebots- oder Bedarfsmenge erschöpft ist.

5. Die Opportunitätskosten werden nach jedem Durchgang neu berechnet und das Zuordnen beginnt von vorne.

6. Wenn alle Kapazitäten zugeordnet sind, ist das Verfahren abgeschlossen

Prinzipiell steckt die Idee dahinter, dass zuerst der Weg gegangen wird, der im Falle des Verzichts die größten Kosten verursachen würde. Diese werden durch die Opportunitätskosten in der Hilfsmatrix dargestellt. Anstatt mit dem absoluten Preis zu arbeiten, wird hier also die relative Verteuerung betrachtet.

Probleme und Einschränkungen

Wenn gleichhohe aber höchste Differenzbeträge auftreten, dann gibt der Algorithmus nicht vor, wie weiter vorzugehen ist. Dieses Problem lässt sich in Bezug auf die beste Lösung auch nicht trivial lösen. Des Weiteren ist es bei dieser Methode nicht möglich, vorhandene Fixkosten einzubeziehen.

Operations Research: Anwendung der Lösung

Das Verfahren stammt aus Zeiten, als die Rechenleistung noch ziemlich begrenzt war. Wenn man heutzutage bei einer großen Anzahl von Orten ganzzahlige Lösungen sucht, dann benötigt man, dank der Komplexität in der Fragestellung, mittlerweile sehr viel Rechenleistung. In der Regel mieten sich Unternehmen dazu die benötigte Leistung von einem Rechenzentrum (HPC). Mit der Vogelschen Approximationsmethode lässt sich allerdings schon eine gute Referenz finden, die die eigentliche Optimierung unter Umständen enorm beschleunigen kann. Will man beispielsweise in der Produktionslogistik Routenzüge einführen, so kann man diese Methode heranziehen, um die Herausforderung des entsprechenden Transportproblems zu lösen.

Vor- und Nachteile

Vorteile

• Die Lösung ist nahe am Optimum
• Die Rechenzeit ist gering, da es keine aufwendigen Matrixoperationen gibt
• Zulässige ganzzahlige Lösungen werden schnell gefunden
• Per Hand zügig durchführbar – wenn die Komplexität es zulässt

Nachteile

• Die Lösung ist nicht das Optimum
• Der Algorithmus kann Fixkosten und Mehr-Produkte-Fälle kaum miteinbeziehen
• Für komplexe Fragestellungen wird heutzutage zusätzliche Rechenleistung benötigt

Zusammenfassung

Das Transportproblem ist ein logistisches Grundproblem, das durch die Vogelsche Approximationsmethode gelöst werden kann. Dabei handelt es sich um ein heuristisches Verfahren, das die Basis bildet für eine Näherungslösung, die dem Optimum sehr nahekommt. Der sich daraus ergebende Transportmix hält die Transportkosten minimal. Da sich logistische Anforderungen ständig ändern, muss auch diese Berechnung kontinuierlich durchgeführt werden, um eine permanente Kostenoptimierung sicherzustellen.

Teaserbild: Daniel Schwen / CC BY-SA 3.0

Sie interessieren sich für Themen rund um die Heuristik; dann lesen sie auch den Artikel Block-Heuristik.