Netzwerk-Optimierung

Netzwerkorientierte Optimierungsprobleme

Viele Optimierungsmodelle besitzen eine Graph- bzw. Netzwerkstruktur, z.B. Transport-, Fluss- und Distributionsmodelle sowie Modelle der Versorgungsnetz-, Touren- und Standortplanung. Andere Problemstellungen u.a. aus den Bereichen Physik, Medizin oder Ingenieurwesen lassen sich als Netzwerkoptimierungsprobleme formulieren [Ahuja et al., 1995]. Netzwerkmodelle können als lineare Programme dargestellt werden, lassen sich jedoch wegen ihrer speziellen Struktur meist mithilfe zugeschnittener Verfahren [Ahuja et al., 1993] effizienter als unter Benutzung allgemeiner LP-basiereter Optimierungssoftware lösen.

Formulierungen von Netzwerk-Optimierungsproblemen als mathematische Modelle sind dennoch sehr wichtig, nicht nur weil sie genaue Problemdefinitionen angeben, sondern auch weil viele Praxisoptimierungsaufgaben zwar eine Netzwerkstruktur aufweisen, aber dazu noch zusätzliche Restriktionen besitzen, die nicht direkt in ein Standardnetzwerkproblem zu integrieren sind. Durch Formulierung dieser zusätzlichen Restriktionen bekommt man mathematische lineare, aber oft auch gemischt-ganzzahlige Programme, die man mittels Optimierungssoftware lösen kann [Suhl/Mellouli, 2006]. In manchen Fällen lassen sich diese Probleme mittels Dekompositions- oder Lagrange-Relaxationstechniken in leichtere Teilprobleme aufteilen, die mit netzwerkbasierten Algorithmen gelöst werden können [Ahuja et al., 1993].

Typische Netzwerk-Optimierungsprobleme

Transportproblem - Umladeproblem - Flussprobleme

Beim klassischen Transportproblem sucht man nach einem kostenminimalen Transport- bzw. Distributionsplan von Anbietern zu Nachfragern, wobei nur direkte Verbindungen zwischen Anbietern und Nachfragern (bipartiter Graph) mit den entsprechenden Transportkosten pro Mengeneinheit berücksichtigt werden. Sind Anbieter (Quellen) und Nachfrager (Senken) in einem allgemeinen, nicht bipartiten, Netzwerk angegeben, die über Umladeknoten – strukturiert in Schichten oder auch nicht – verbunden sind, spricht man von mehrstufigen Transportproblemen bzw. von Umladeproblemen (transshipment problems). Letzteres stellt den allgemeinen Rahmen für kostenminimale Flussprobleme (Min-Cost-Flow-Problem) dar. Der Spezialfall der Bestimmung der maximalen Gütermenge von allen Anbietern zu allen Nachfragern (Max-Flow-Problem) tritt im Rahmen von Kapazitätsuntersuchungen für Transportnetze (z.B. Rohrleitungsnetze, Straßenverkehrsnetze) auf.

Kürzeste Wege – minmale Spannbäume

Die Bestimmung kürzester Wege in Transport- oder Kommunikationsnetzwerken ist meist eines der grundlegenden Probleme. In bestimmten Modellnetzwerken (z.B. Netzplänen) können auch verschiedene Sachverhalte, wie die Bestimmung der Durchlaufzeit eines Projektes, mit Hilfe kürzester/längster Wege gelöst werden. Da ein Versorgungsnetz (z.B. Wasser-, Gas- oder Telefonleitungen) auch eine Baumstruktur aufweist, ist das Problem der Bestimmung minimaler Spannbäume verwandt und wird sogar mit ähnlichen Verfahren gelöst (Dijkstra- vs. Prim-Algorithmus).

Briefträgerproblem

Ein Briefträger hat die Häuser eines Stadtteils mit Post zu beliefern. Für ihn soll ein geschlossener Weg minimaler Länge bestimmt werden, der jede zu bedienende Straße (oder Straßenseite) mindestens einmal enthält. Dabei soll die Länge der unproduktiven Strecken minimiert werden.

Tourenplanung – Traveling-Salesman-Problem

Eine Anzahl von Kunden, deren Bedarfe und Standorte bekannt sind, soll mit einer Anzahl von Fahrzeugen mit bestimmten Kapazitäten von einem Depot aus mit einem bestimmten Gut beliefert werden. Welche Fahrten sind durchzuführen, damit unter Einhaltung bestimmter Nebenbedingungen (z.B. Zeit- und Kapazitätsrestriktionen) die Gesamttransportkosten minimiert werden? Das Traveling-Salesman-Problem stellt einen Spezialfall der Tourenplanung mit einem Depot und ohne Kapazitätsrestriktionen dar.

Probleme der Standortplanung

Ein Unternehmen beliefert n Kunden, die pro Periode b1,...,bn ME der von ihm angebotenen Güter nachfragen, und möchte seine Vertriebskosten senken, indem es Auslieferungslager einrichtet und betreibt. Hierfür stehen m potentielle Standorte zur Verfügung. Wird am potentiellen Standort i ein Lager errichtet, so entstehen Fixkosten der Lagerhaltung in Höhe von fi GE pro Periode. Wie viele Lager sind vorzusehen und an welchen der potentiellen Standorte sind sie einzurichten, wenn bei voller Befriedigung der Kundennachfrage die Summe aus fixen Lagerhaltungskosten und variablen Transportkosten (Lager zu Kunden) minimiert werden soll? (Warehouse-Location-Problem)

Effiziente Lösung von Netzwerk-Optimierungsproblemen

Für Wirtschaftsinformatiker ist es wichtig, ein Gefühl für die Lösungskomplexität der vorgestellten Modelle zu entwickeln. Die zwei ersten vorgestellten Klassen von Problemen sind relativ einfach, sprich auch im schlechtesten Fall, mit einem polynomiellen Algorithmus lösbar, dagegen leiden Problemstellungen der zwei letzten Klassen unter der kombinatorischen Explosion und gehören der Klasse der NP-vollständigen Probleme an, wofür (für alle Datenkonstellationen) keine effiziente Algorithmen bekannt sind. Die Briefträgerprobleme sind nur für Graphen mit gemischten gerichteten (Einbahnstraßen) und ungerichteten Kanten schwierig zu lösen. Wie in diesem Fall ersichtlich, ist es nicht immer leicht, die Grenze zwischen effizient lösbaren und schwierigen Problemformulierungen zu ziehen und somit die passende netzwerkorientierte Modellierung zu wählen. Eine kombinatorische Explosion möglicher Lösungen bedeutet nicht unbedingt, dass es keine effizienten Lösungsalgorithmen geben kann (vgl. minimale Spannbäume).

In manchen praktischen Fällen können Problemstruktur-Eigenschaften aufgedeckt werden, mit deren Ausnutzung eine Problemstellung effizienter gelöst werden kann. Ein Beispiel dafür bildet die Ähnlichkeit des Tourenplanungsproblems (Vehicle Routing Problem) mit dem Umlaufplanungsproblem im öffentlichen Verkehr (Vehicle Scheduling Problem). Bei dem ersten Problem müssen alle Kunden in Touren und bei dem zweiten alle Planfahrten in Umläufen bedient werden. Da aber planmäßige Fahrten und deren Verknüpfungsmöglichkeit nicht nur eine örtliche, sondern auch eine zeitliche Abhängigkeit aufweisen, die zu einem azyklischen Modellnetzwerk führen, können reine Netzwerkflussmodelle herangezogen werden und somit Umlaufplanungsprobleme effizienter gelöst werden (vgl. [Suhl/Mellouli, 2009], Kapitel 7). Praxisinstanzen der Umlaufplanungsprobleme lassen sich mithilfe von Optimierungssoftware optimal lösen, aber solche der Tourenplanung meist nur mit Heuristiken suboptimal lösen.

Literatur

Ahuja, R.K., Magnanti, T.L.,.Orlin, J.B. and Reddy, M.R.: Applications of Network Optimization. In Network Models (Ball, M.O. et al. eds.). Handbooks in Operations Research and Management Science. Volume 7. Elsevier (1995).

Ahuja, R.K., Orlin, J.B. and Magnanti, T.L.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall 1993.

Suhl, Leena und Mellouli, Taïeb: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Berlin et al. : 2. Aufl. Springer 2009.