Wir modellieren das Zuordnungsproblem der Einzelwagen-Disposition als Netzwerkflussproblem mit Kantenmultiplikatoren, um spezielle Subsitutionsbedingungen abzubilden. Trotz der restriktiven Struktur der in der Anwendung betrachteten generalisierten Netzwerke ist die Komplexität der Berechnung einer ganzzahligen Lösung beweisbar hoch (NP-schwer), so dass eine Optimallösung in der Praxis aufgrund der Online-Anforderung nicht effizient genug zu berechnen ist. Wir stellen weiterhin eine additive 1-Approximation vor. Diese garantiert optimale Kosten unter der Einschränkung, dass einzelne Kunden einen einzelnen Wagen mehr erhalten als bestellt. Solche Wagen können in der Praxis umdisponiert werden, so dass eine zulässige Disposition entsteht.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

Im Rahmen der Einzelwagen-Disposition muss gegenwärtig einmal pro Tag (und in Zukunft mehrfach bzw. 'online') eine Zuordnung zwischen bis zu 10.000 Leerwagen verschiedener Typen im Bestand zu entsprechenden Bedarfen gefunden werden.

Die Zuordnung soll kostenoptimal bezüglich des Transports im ganzen (europäischen) Produktionsgebiet unter einer Vielzahl von Nebenbedingungen sowie weichen Kriterien zur Berücksichtigung von Marktstrategien oder Kundenzufriedenheit sein.

Die in einer Projekt-Zusammenarbeit mit der DB Schenker Rail und der Technischen Universität Kaiserslautern entwickelte mathematische Modellierung berücksichtigt dabei sowohl die Verwaltung von Abstellkapazitäten und die aktive 'Disposition' abzustellender Wagen als auch die Online-Natur des Problems. Zusätzlich werden Regelungen bezüglich des Einzelwagenverkehrs zwischen verschiedenen Unternehmen und über Landesgrenzen hinweg berücksichtigt, die im Zuge der Internationalisierung verstärkt Bedeutung erlangen.

Letztere können im Rahmen eines klassischen Flussmodells umgesetzt werden. Hier soll jedoch auf die Anwendung der generalisierten Flüsse zur Modellierung gemischtzahliger Substitution von Wagentypen, in der konkreten Anwendung 1:1und 2:1-Substitution, eingegangen werden.

Im folgenden Abschnitt definieren wir das Dispositionsproblem formal (in gegenüber der Praxis vereinfachter Version). In Abschnitt 3 wird die Modellierung als generalisiertes Netzwerkmodell vorgestellt und die Komplexität des Problems theoretisch untersucht. Letztere verbietet eine ganzzahlige und damit zulässige Lösung des Problems in praktisch annehmbarem Zeitrahmen.
Abschnitt 4 befasst sich mit der Frage, wie fraktional (bzw. wie unzulässig) effizient berechenbare fraktionale Dispositionen sein können. Wir zeigen, dass für Anwendungsinstanzen halbzahlige Lösungen polynomiell, also effizient, berechnet werden können. Solche Lösungen mit minimalen Kosten dienen als Basis einer in Abschnitt 5 vorgestellten Rundungsstrategie für die wir approximative Gütegarantien zeigen.

Die resultierende 1-additive Approximation ist nicht vollständig zulässig, da Bedarfe einzelne überzählige Wagen erhalten können. In der Praxis können diese überzähligen Wagen iterativ umverfügt werden. In Abschnitt 6 stellen wir dazu exemplarisch einige Ergebnisse auf realen Datensätzen vor.

2 Disposition

Vereinfacht können wir das hier betrachtete Dispositionsproblem (DP) wie folgt formalisieren: Eine Instanz I=(S, D, S, T) des Dispositionsproblems ist gegeben durch die Menge S={i=(l(i),t(i),c(i),n(i))} von Beständen und die Menge D={j=(l(j),t(j),c(j),n(j))} von Bedarfen. Hierbei charakterisieren die Attribute l, t, c, und n in dieser Reihenfolge den Bestandsbzw. Bedarfsort, den Bestandsbzw. Bedarfstyp, den Verfügungszeitpunkt bzw. Bestellzeitpunkt sowie die Anzahl der zur Verfügung stehenden bzw. bestellten Wagen. (Wir nehmen damit an, dass Bestandsund Bedarfsdaten nach Ort, Typ und Zeit aggregiert sind oder wenden zuvor ein entsprechendes Clustering an.)

Die Menge S umfasst Substitutionsregeln der Gestalt (n(s)t(s),n(d)t(d)), die besagen, dass n(s) Wagen des Typs t(s) eine Bestellung von n(d) Wagen des Typs t(d) decken können. In den meisten (Anwendungs-)Fällen gilt n(s)=n(d)=1 bzw 1:1Substitution. In der betrachteten Anwendung bei DB Schenker Rail treten außer diesen Regeln nur solche mit n(s)=2 und n(d)=1 bzw. 2:1-Substitution auf.
Ein Bestand i ist für einen Bedarf j erlaubt (erl(i,j)), falls S eine Regel s=(n(s)t(s),n(d)t(d)) mit t(s)=t(i) und t(d)=t(j) enthält. Letztere ist eindeutig in den Stammdaten hinterlegt und definiert somit eine relative Wertigkeit v(t(s),t(d))=n(d)/n(s) eines Bestandswagentyps zu einem Bedarfswagentyp, sofern dieser durch t(s) substituierbar ist. (Die relative Wertigkeit eines Bedarfstyps zu einem Bestandstyp ist entsprechend reziprok.)

Falls alle definierten relativen Wertigkeiten für einen Bestandstyp übereinstimmen existiert eine totale Wertigkeit v(t(s)) für diesen Bestandstyp. Eine Instanz des DP, die totale Wertigkeiten v : S -> |R für alle Bestandstypen besitzt, nennen wir totale Instanz.

Die Menge T stellt den (vorab unabhängig von der aktuellen Disposition festgelegten) Güterzugfahrplan im Einzelwagenverkehr (für beladene und leere Güterwagen) auf Basis von Ort-zu-Ort-Verbindungen t(k,m)=(l(k), c(k), l(m), c(m), r(k,m)) dar. Hierbei bezeichnen l(k) und l(m) Bestandsund Bedarfsort, c(k) die Zugbildungszeit des ersten Zuges der (zusammengesetzten) Verbindung zwischen l(k) und l(m) am Bestandsort und c(m) die Zugauflösezeit des letzten Zuges der Verbindung am Bedarfsort. Die Kosten des Transports eines Leerwagens mittels dieser Zugverbindung sind (unabhängig von Wagentypen) als r(k,m) hinterlegt.

Ein Bestand ist für einen Bedarf rechtzeitig (rec(i,j)), falls T eine Verbindung t(k,m) enthält, so dass l(k)=l(i), l(m)=l(j), die Zugbildungszeit nach dem Verfügungszeitpunkt liegt (c(i)≤c(k)) und die Zugauflösezeit vor dem Bestellzeitpunkt liegt (c(m)≤c(j)). Bestands und Bedarfsorte sind auf Dispostellen mit Rangiermöglichkeiten vergröbert. Da in den Zubringfahrten zu solchen Dispostellen fixe Nahbereichszuordnungen gelten und nicht rangiert werden kann, ist hier kein Optimierungspotential vorhanden und das Dispositionsergebnis verschlechtert sich durch die Vergröberung nicht.
Jede Verbindung kann aus mehreren Zügen und Umstellungen an Zwischenstationen bestehen, wobei auch die Umstellungen (inklusive Bestandsort, exklusive Bedarfsort) in die Kosten einbezogen werden. Ein Kapazitätsmanagment der beteiligten Güterzüge ist nicht vorgesehen, so dass eventuell Wartezeiten an Zwischenstationen anfallen, da der zeitnächste Folgezug bereits seine zulässige Gesamtlänge bzw. Gesamtgewicht überschritten hat. Um diese Verspätungen auszugleichen, wird bei mehreren möglichen Verbindungen zwischen Bestandsund Bedarfsort stets die früheste abgehende Verbindung am Bestandsort gewählt.

Eine Verfügung d=(i(d),j(d),n(i,j)) bezeichnet die (Einzel-)Disposition von n(i,j) Wagen aus Bestand i zu Bestellung j und besitzt die Kosten c(d)=n(i,j)r(i,j). Eine (Gesamt-)Disposition D={d} ist eine Menge von Verfügungen und besitzt die Kosten c(D) definiert als Summe der einzelnen Verfügungskosten.

Eine zulässige Verfügung (für eine DP Instanz I=(S,D,S,T)) muss offenbar folgende Kriterien erfüllen:

1. i(d) ist ein Bestand aus S, j(d) ist ein Bedarf aus D

2. erl(i,j) bezüglich S

3. rec(i,j) bezüglich T

4. n(i,j)≤n(i)

5. v(t(i),t(j))n(i,j)≤n(j)

6. n(i,j) ist ganzzahlig

Eine zulässige Disposition (für I) umfasst nur zulässige Verfügungen (i,j,n(i,j)) und erfüllt zusätzlich:

Eine zulässige Disposition ist optimal bzw. eine Lösung des DP für I, falls sie minimale Kosten besitzt.

Im Folgenden bezeichnen wir gelegentlich auch Verfügungen als (fraktional-) zulässig, wenn n(i,j) nicht ganzzahlig ist und meinen damit, dass alle anderen oben aufgeführten Kriterien einer zulässigen Verfügung erfüllt sind. Dispositionen, die solche Verfügungen enthalten, jedoch alle anderen oben aufgeführten Kriterien erfüllen, werden ebenfalls als (fraktional-)zulässig und gegebenenfalls als (fraktional-)optimal bezeichnet.

Als a-Approximation bezeichnet man im Allgemeinen eine Lösung einer ProblemInstanz, deren Kosten höchstens dem a-fachen der Optimallösung entsprechen. Ein Algorithmus oder eine Lösungsmethode A ist eine a-Approximation für das Problem, falls der Quotient aus den Kosten der durch A ermittelten Lösung und den optimalen Kosten für keine Instanz (im Minimierungsfall) größer ist als a.

Im Fall, dass die Bedingungen für die Zulässigkeit einer Lösung wie im Dispositionsproblem durch (Un-)gleichungen gegeben sind, kann eine aApproximation auch diese um den Faktor a verletzen. Eine additive aApproximation besitzt Kosten, die die Summe aus den Kosten der Optimallösung und a nicht überschreiten, und Nebenbedingungen werden um nicht mehr als den additiven Term a verletzt.

3 Generalisiertes Netzwerkmodell

Wir konstruieren ein generalisiertes Netzwerk Ng(I)=(V,A) mit Kosten c:A -> |R, Kapazitäten k:A -> |R, Multiplikatoren m:A -> |R und Balancen b:V -> |R (siehe Abbildung 1) zu einer gegeben DP Instanz I.

Die Menge V enthält einen Knoten s(i) für jeden Bestand i in S und einen Knoten d(j) für jeden Bedarf j in D. Zusätzlich enthält V einen Knoten s (Quelle) und einen Knoten t (Senke). Für alle Knoten v in V mit Ausnahme von s und t setzen wir b(v)=0; für s und t:

Formel siehe PDF.

A enthält alle Bögen (gerichtete Kanten) (s(i),d(j)), so dass erl(i,j) und rec(i,j) erfüllt sind, sowie alle Bögen (s,s(i)) und (d(j),t). Letztere erhalten keine Kosten und besitzen Kantenmultiplikatoren vom Wert 1 (wie im klassischen Fall), jedoch die Kapazitäten n(i) bzw. n(j). Bögen (s(i),d(j)) besitzen dagegen unendliche Kapazität, jedoch Kosten c(s(i),d(j))=r(i,j). Die Kantenmultiplikatoren m(s(i),d(j))=v(t(i), t(j)) entsprechen relativen Wertigkeiten zwischen Bestandstyp und Bedarfstyp.

Sei nun f* ein Minimalkostenfluss in Ng(I) und erfülle daher die folgenden Kapazitätsund Flusserhaltungsbedingungen für generalisierte Netzwerkflüsse [1]:

1. Kapazitätsbedingung: Auf allen Bögen a in A ist der Flusswert f(a) kleiner oder gleich der Kapazität k(a).

2. Flusserhaltungsbedingung: Für alle Knoten v in V ist die Summe der einfliessenden Flüsse gewichtet mit dem jeweiligen Multiplikator und der ausgehenden Flüsse gleich der Balance.

Bild 1: Generalisiertes Flussnetzwerk Ng (l)

Wir setzen nicht voraus, dass b(s) = - b(t), sondern nehmen an, dass b(s) ≤- b(t). Letzteres kann durch Pseudo-Bedarfe, die Abstellungen entsprechen, bei jeder Wagenlage erreicht werden. Daher berechnet der Minimalkostenfluss in Ng(I) implizit einen maximalen Fluss mit Wert |f*|=b(s), der jedoch streng genommen bezüglich b(t) – und nur bezüglich b(t) – ein Pseudofluss sein kann, d.h. dass die Flusserhaltungsbedingung in t verletzt ist.

Bei Verwendung einer einzigen Modellsenke kann diese Besonderheit durch setzen von –b(t)=b(s) vermieden werden. Im allgemeineren Fall mit mehreren Senken ist dies nicht möglich. Letzterer wird in der Anwendung bei DB Schenker Rail zur Modellierung weiterer Nebenbedingungen herangezogen. Wir bleiben bei obiger Modellierung, da die spezielle Eigenschaft von f* als Pseudofluss kein Hindernis darstellt.

Wir definieren eine Disposition D*(I) abhängig von f* für I wie folgt:

Formel siehe PDF.

Theorem 1:

D*(I) ist eine optimale Disposition für I, genau dann wenn f*(Ng(I)) ganzzahlig ist.

Zum Beweis betrachten wir zunächst die einzelnen Verfügungen. Durch die Netzwerkkonstruktion (Existenz der Knoten und Kanten im Netzwerk) sind die ersten drei Kriterien einer zulässigen Verfügung erfüllt. Die Ungleichungen n(i,j) ≤ n(i) und v(t(i),t(j))∙n(i,j) ≤ n(j) werden durch Kapazitäts- und Flusserhaltungsbedingung für f* erfüllt, da die Summe der eingehenden Flüsse in jeden Knoten s(i) durch die Kapazität k(s,s(i))=n(i) beschränkt ist und die Summe der austretenden Flüsse aus jedem Knoten d(j) durch k(d(j), t)=n(j). Dies erfüllt insbesondere die Kriterien für zulässige Verfügungen, vor allem aber (mit obiger Annahme |f*|=b(s)) die allgemeineren Forderungen für eine zulässige Disposition. Die Zulässigkeit der Disposition hängt also nur von der Ganzzahligkeit der Flusses ab.

Wir bemerken: Umgekehrt kann aus jeder zulässigen Disposition D(I) auch ein zulässiger Fluss (oder Pseudofluss im obigen Sinne) in Ng(I) abgeleitet werden, indem der Fluss auf Bögen (s(i),d(j)) durch die Anzahl der verfügten Wagen definiert ist. Dieser kann unter gleicher Argumentation wie oben zu einem zulässigen Fluss erweitert werden.

Wir zeigen die Optimalität von D*(I) durch Widerspruch. Nehmen wir nun an D*(I) mit Kosten c(D*) ist nicht optimal, dann existiert eine zulässige Lösung D(I) mit c(D)<c(D*). Da nur Bögen a=(s(i),d(j)) in A Kosten c(a)=r(i,j)>0 besitzen und alle Flusswerte f(s(i),d(j))>0 mit Anzahl f(s(i),d(j)) und Kosten r(i,j) in die Disposition eingehen gilt:

Formel siehe PDF.

Dies gilt auch umgekehrt für Lösung D und einen aus ihr abgeleiteten Fluss f und damit c(f)=c(D)<c(D*)=c(f*). Letzteres ist ein Widerspruch zur vorausgesetzten Kostenminimalität von f* und Theorem 1 ist bewiesen. Als Korollar erhalten wir:

Korollar 2:

Jeder (fraktional-)zulässigen Fluss im Netzwerkmodell Ng(I) ist äquivalent zu einer (fraktional-)zulässigen Lösung D(I).

Tritt in I nur 1:1-Substitution auf, so sind alle relativen Wertigkeiten v(t(s),t(d))=1 (und damit auch totale Wertigkeiten) und alle Multiplikatoren m(s(i),d(j))=v(t(i),t(j))=1. Das generalisierte Netzwerkmodell Ng(I) entspricht also dem Spezialfall des klassischen Flussmodells ohne Multiplikatoren. Nach [2] kann ein ganzzahliger minimaler Kostenfluss in solchen Netzwerken mit ganzzahligen Kosten, Kapazitäten und Balancen (wie in der Anwendung gegeben) in polynomieller Zeit und damit effizient berechnet werden.

Im praktisch relevanten Fall der 2:1-Substitution muss hingegen das generalisierte Minimalkostenfluss-Problem (GMFP) ganzzahlig gelöst werden. Nach [3] ist dies für allgemeine generalisierte Netzwerke komplexitätstheoretisch NP-schwer (vergleiche [4]). Daher ist zu vermuten, dass kein polynomieller und damit effizienter Algorithmus zur Lösung des Problems existiert.

Die zur Modellierung von DP-Instanzen verwendeten generalisierten Netzwerke haben jedoch eine spezielle Struktur, da sie zum Beispiel bipartit sind (und im konkret vorliegenden Fall nur Multiplikatoren 1 und 2 verwenden). Dennoch bleibt die Komplexität bestehen, wie sich aus der Äquivalenz des DP und des GMFP in Korollar 2 und dem folgenden Theorem 3 ableiten lässt.

Theorem 3:

Das DP ist für Instanzen mit totalen Wertigkeiten v(t(s)) ϵ {1,2} NP-schwer.

Wir wollen auf eine Einführung in die Komplexitätstheorie und daher den Beweis für Theorem 3 an dieser Stelle verzichten. Im Hinblick auf eine praktisch anwendbare Lösung des DP bezüglich der Laufzeiten motiviert Theorem 3 die Entwicklung approximativer Verfahren.

Letztere sind Verfahren, die eine (beinahe) zulässige Lösung liefern, deren Kosten höchstens um einen festen (multiplikativen) Faktor von den minimalen Kosten abweichen. Um letzteres zu erreichen verwenden wir folgenden Ansatz: Wir berechnen einen Minimalkostenfluss f* in Ng(I) bzw. leicht modifizierten Netzwerken und verzichten auf die Bedingung der Ganzzahligkeit. Dies ist (insbesondere im Fall von Instanzen, die in der Praxis auftreten) in polynomieller Zeit möglich. Darüber hinaus kann die Halbzahligkeit von f* im Anwendungsfall garantiert werden. Dies ermöglicht ein Approximationsverfahren durch Runden der fraktionalen Lösung.

4 Halbzahlige Disposition

Sei I2=(S,D,S,T) eine DP-Instanz, wobei S nur solche Regeln (n(s)t(s),n(d)t(d)) enthält mit n(s)=n(d)=1 oder n(s)=2 und n(d)=1, wie es bei Anwendungsinstanzen der Fall ist. Zusätzlich nehmen wir zunächst an, dass I2 totale Wertigkeiten v(t(s)) für alle Bestandstypen t(s) besitzt. Letzteres ist generisch bei praktischen Instanzen nicht der Fall.

Wir modifizieren Ng(I) zu Ng(I)' indem wir alle Kantenmultiplikatoren auf 1, die Kapazitäten der Bögen (s,s(i)) auf k'(s,s(i))=v(t(i))n(i) und die Balance b'(s) der Quelle auf die Summe dieser neuen Kapazitäten der zu s inzidenten Bögen setzen. Zusätzlich passen wir die Kantenkosten zu c’(s(i),d(j))=1/v(t(i))∙c(s(i),d(j)) an.

Dieses Vorgehen entspricht einer Manipulation der DP-Instanz: Jeder Wagen eines bestimmten Bestandsund Bedarfstyps wird durch eine Menge von Wageneinheiten dieses Typs ersetzt, so dass jede Substitution mit Bezug auf die Wageneinheiten 1:1 geschehen kann. Dies ist für jede totale Instanz möglich, nicht jedoch für jede Instanz. Weiterhin gibt es nicht-totale Instanzen, die eine solche Modifikation erlauben. Die Anwendungsinstanzen gehören zu diesen, wie wir weiter unten zeigen.

Wir erhalten mit Ng(I)' (siehe Abbildung 2) wiederum ein klassisches Flussnetzwerk. Falls die eingehenden Werte (hier insbesondere die Kapazitäten k(s,s(i))) ganzzahlig sind, erhalten wir einen ganzzahligen Minimalkostenfluss f*' in polynomieller Zeit.

Ist keine Ganzzahligkeit gegeben, so kann diese durch Skalieren der Kapazitätsund Balance-Funktion mit einem passenden ganzzahligen Faktor q erreicht werden. Sei Nq das skalierte Netzwerk und f(q) ein ganzzahliger Minimalkostenfluss darin. Dann gilt aufgrund der Linearität von Kapazitätsund Flusserhaltungsbedigung, sowie der Definition der Kosten des Flusses offenbar:

Lemma 4:

Der Fluss 1/qf(q) ist eine Minimalkostenfluss in Ng(I)', genau dann wenn f(q) ein Minimalkostenfluss in Nq ist.

Bild 2: Generalisiertes modifiziertes Flussnetzwerk Ng(I)'

Vereinfachend betrachten wir zu der gegeben DP-Instanz I immer das modifizierte Netzwerk Nq (mit q=1, falls bereits Ng(I)' nur ganzzahlige Eingabewerte besitzt) und einen ganzzahligen Minimalkostenfluss f(q) darin. Wir setzen dann f*=1/qf(q). Offenbar können als Werte in f* nur Vielfache von 1/q und damit keine beliebigen fraktionalen Werte auftreten. Wir bezeichnen daher f* als q-fraktionalen Fluss.

Letzterer identifiziert jedoch Flusseinheiten mit den oben erwähnten Wageneinheiten, nicht wie zuvor mit Wagen. Daher definieren wir eine Disposition Dq(I) wie folgt:

Formel siehe PDF.

Analog zu Theorem 1 ist Dq(I) eine optimale Disposition, wenn alle Verfügungen ganzzahlig sind. Sei weiterhin p das kleinste gemeinsame Vielfache aller Werte v(t(i)). Dann sind alle Verfügungen d in Dq(I) Vielfache von 1/pq und es gilt:

Lemma 5:

Dq(I) ist eine pq-fraktionale optimale Disposition für I.

Um obiges Ergebnis auf Instanzen I aus der Praxis anwenden zu können, müssten diese total sein. Sie enthalten jedoch folgende Teilmengen von Subsitutionsregeln

Formel siehe PDF.

Offenbar ist l nicht total, da (Formel siehe PDF). Wir modifizieren I zu einer totalen Instanz I' durch Einführen von totalen Wertigkeiten w:D -> |R für alle Bedarfstypen, so dass v’(t(s))=v’(t(s),t(d))=w(t(d))n(d)/n(s) für alle Bestandstypen gilt und damit I'=(S,D',S',T) total ist. Wir setzen w(tx)=1 und w(ty)=w(tz)=2 und

Formel siehe PDF.

Damit ist I' total, da für alle Bestandstypen die relativen Wertigkeiten identisch sind: v'(tx)=v'(tx,tx)=v'(tx,tz)=1, v'(ty)=v'(ty,ty)=v'(ty,tz)=½. Sei nun Ng(I') ein modifiziertes generalisiertes Netzwerk wie oben, wobei das kleinste gemeinsame Vielfache p aller Werte v' bzw. w den Wert p=2 besitzt.

Dieses Netzwerk besitzt nur ganzzahlige Eingaben, so dass direkt ein ganzzahliger Minimalkostenfluss in polynomieller Zeit berechnet werden kann bzw. Nq das entsprechend skalierte Netzwerk mit (polynomiell berechenbarem) ganzzahligen Minimalkostenfluss f(q) mit q=1 ist.

Theorem 6:

Dq(I') ist eine halbzahlige optimale Disposition für I.

Analog zu Theorem 1 und mit Lemma 5 ist Dq(I') eine halbzahlige Optimallösung für I', somit sind alle Verfügungen d=(i(d),j(d),n(i,j)) in Dq(I’) halbzahlig zulässig. Mit der Konstruktion von I' aus I folgt, dass i(d) in S und j(d) in D, sowie erl(i(d),j(d)) und rec(i(d),j(d)) auch für I gelten.

Weiterhin ist n(i,j)≤n(i) und v’(t(i),t(j))∙n(i,j)=w(t(j))∙v(t(i),t(j))∙n(i,j)≤w(t(j))∙(j), woraus folgt v(t(i),t(j))∙n(i,j)≤n(j) und alle Verfügungen sind halbzahlig zulässig für I.

Für alle i in S gilt (Formel siehe PDF.) und für alle j in D: (Formel siehe PDF.) kleiner gleich w(t(j))∙n(i) und damit (Formel siehe PDF.).

Da also Dq(I') eine fraktional-zulässige Lösung für I ist und jede fraktional-zulässige Lösung für I auch eine solche für I' (siehe obige (Un)gleichungen), kann es keine solche Lösung mit kleineren Kosten für I geben und Dq(I') ist eine halbzahlige Optimallösung für I.

Wir bezeichnen die so in polynomieller Zeit erhaltene halbzahlige Optimallösung für I mit D2(I) und zeigen im nächsten Abschnitt, wie diese zu einer approximativen ganzzahligen Lösung gerundet werden kann.

Die Rückführung des Problems auf ein klassisches Netzwerkflussproblem dient vor allem dem Beweis, dass der generalisierte Minimalkostenfluss im Anwendungsfall ohne zusätzliche Forderungen (Ganzzahligkeit) in polynomieller Zeit berechnet werden kann und halbzahlig ist. Ist dies gegeben, so kann direkt ein generalisierter Minimalkostenfluss berechnet werden. Wir nutzen dazu eine Modifikation des Successive Shortest Path Algorithmus [1,5,6], der Kantenmultiplikatoren berücksichtigt. Andere klassische Flussalgorithmen wurden ebenfalls für den generalisierten Fall angepasst (vergleiche [7,8]).

5 Approximative Disposition

Sei D2(I)={d=(i(d),j(d),n(i,j))} eine halbzahlige Optimallösung der praktischen DP Instanz I mit Kosten c(D2) wie im obigen Abschnitt definiert. Für einige der Verfügungen d kann n(i,j) weiterhin ganzzahlig sein, so dass kein Runden notwenig ist. Wir schränken unsere Betrachtungen daher auf den halbzahligen Anteil (n(i,j)=1/2) halbzahliger Verfügungen und (später) Teilverfügungen mit n(i,j)=1 bestimmter ganzzahliger Verfügungen ein. Bevor wir dies formal definieren halten wir fest:

Lemma 7:

Für eine halbzahlige Verfügung d=(i(d),j(d),n(i,j)) gilt: t(i)=ty und t(j)=ty oder t(j)=tz.

Halbzahlige Verfügungen entstehen durch die Division von n(i,j) durch v(t(i)) in einer ganzzahligen Disposition. Da tz kein Bestandstyp ist und v(tx)=1 ist, muss t(i)=ty, andernfalls wäre d nicht halbzahlig. Aus den Substitutionsregeln ergeben sich ty und tz als erlaubte Bedarfstypen.

Sei der halbzahlige Anteil der Disposition D2(I) wie folgt defniert:

Formel siehe PDF.

Weiterhin definieren wir eine graphische Repräsentation als ungerichteten bipartiten Graph G∣2=(V , E) von D|2(I) mit V=X U Y und

Formel siehe PDF.

Sei g(v) für Knoten v in V der Grad (Anzahl der inzidenten Kanten) von v in G.

Offenbar muss für den Erhalt einer ganzzahligen Disposition jede zu einer Kante in E korrespondierende Verfügung entweder aufoder abgerundet werden. Damit die gerundete Disposition zulässig bleibt, muss sowohl in der Summe als auch bezogen auf jeden einzelnen Bestand i die Summe der verfügten Wagen gleich bleiben, da weiterhin alle Wagen verfügt sein müssen und insbesondere pro Bestand nicht mehr als die bereitstehenden Wagen verfügbar sind.

Bezüglich der Knoten x in X (Bestandsseite) muss also die Anzahl der aufgerundeten Verfügungen, die inzidenten Kanten (x,y), y in Y entsprechen, gleich der Anzahl der abgerundeten Verfügungen, die inzidenten Kanten (x,y), y in Y entsprechen, sein. Wir sprechen im Folgenden kurz von aufbzw. abgerundeten Kanten und meinen damit die korrespondierenden Verfügungen.

Für Knoten y in Y (Bedarfsseite) muss diese Gleichheit nicht unbedingt erfüllt sein, da für jeden Bedarf j, sowie die Summe der Bedarfe nur gefordert wird, dass die Anzahl an dorthin verfügten Wagen (gewichtet mit der relativen Wertigkeit) nicht über der (insgesamt) bestellten Wagenanzahl liegt. Es kann allerdings nur garantiert werden, dass ein Bedarf nicht übererfüllt wird, falls tatsächlich die gleiche

Anzahl von inzidenten Kanten (x,y), x in X aufund abgerundet wird.

Die hier vorgestellte Rundungsstrategie basiert auf einer eindeutigen Überdeckung aller Kanten aus E mit Pfaden und dem abwechselnden Aufund Abrunden von Kanten entlang dieser Pfade.
Benötigen wir nur einen einzigen Pfad p, um alle Kanten zu überdecken, und dieser beginnt und endet am gleiche Knoten so ist p ein Eulerkreis [9] und G eulersch. Hat G einen Eulerkreis, so erfüllt die Rundungsstrategie (insbesondere da G bipartit ist und der Eulerkreis somit gerade Länge besitzt) alle Anforderungen an das Runden der Kanten.

Eulersche Graphen sind dadurch charakterisiert, dass jeder Knoten v in V geraden Grad besitzt. Da wir mit folgendem Lemma nur zeigen können, dass g(x) für alle x in X gerade ist, nicht jedoch g(y) für alle y in Y, können wir nicht erwarten immer einen Eulerkreis zu finden.

Lemma 8:

Für alle Knoten x in X ist g(x) geradzahlig.

Da die Anzahl der Wagen n(i) des zu x gehörigen Bestandes i ganzzahlig ist und D2(I) zulässig ist, also alle Wagen verfügt werden, muss die Summe der Wagenanzahlen aller Verfügungen von Wagen aus dem Bestand i ganzzahlig sein. Daher muss die Anzahl halbzahliger Verfügungen, also zu x inzidente Kanten in G und damit g(x) gerade sein.

Das folgende Beispiel zeigt, dass dies nicht für g(y), y in Y gelten muss. Eine Instanz des DP enthalte die Bestände s(1)=(l(1), c(1), tx, 1), s(2)=(l(2), c(2), tx, 1) und s(3)=(l(3), c(3), ty, 1) sowie die Bedarfe d(4)=(l(4), c(4), tz, 1) und d(5)=(l(5), c(5), tz, 1). Dabei seien alle Bestände für alle Bedarfe rechtzeitig (und erlaubt nach den oben angenommenen Substitutionsregeln). Zusätzlich gelte r(1,4) < r(3,4)<r(2,4) und r(2,5)<r(3,5)<r(1,5). Dann ist die optimale halbzahlige Disposition durch folgende Verfügungen gegeben: (1,4,1), (2,5,1), (3,4,1/2), (3,5,1/2). Diese resultiert in G|2 wie in Abbildung 3 dargestellt.

Bild 3: G|2 mit Knoten y in Y ungeraden Grades

Sei O die Menge der Knoten y in Y mit ungeradem Grad g(y). Dann reichen |O|/2 Pfade p zwischen jeweils 2 Knoten aus O (und eventuell eine Menge von Kreisen) aus, um alle Kanten in E eindeutig, d.h. so zu überdecken, dass jede Kante nur in einem Pfad vorkommt. Dies ergibt sich aus der folgenden Konstruktion der Pfade, die lineare Zeit in |E| benötigt:

Algorithmus: Pfad-Überdeckung

Formel siehe PDF.

Schritt 2 ist immer möglich, da u in O ungeraden Grad hat, also mindestens eine inzidente Kante existiert bzw. v nicht in O liegt also geraden Grad hat. Da v über eine Kante betreten wurde ist g(v)>0 und es existiert mindestens eine weitere Kante. Schritt 3 ist ebenfalls immer möglich, da G bipartit ist und daher w in X immer geraden Grad besitzt. Da w über eine Kante betreten wurde ist g(w)>0 und es existiert mindestens eine weitere Kante.

In Schritt 4 werden entweder 2 Knoten aus O entfernt und es entsteht ein neuer Pfad oder der bestehende Pfad wird fortgesetzt. Innerhalb eines Pfades wird der Grad jedes besuchten Knotens um genau 2 verringert, so dass die Parität des Grades für alle Knoten gleich bleibt. Eine Ausnahme bilden Anfangsund Endknoten, deren Grad gerade wird und sie somit aus O entfernt werden, womit die Anzahl der Pfade |O|/2 ist. Die Ausführbarkeit der Schritte 2 und 3 ist damit auch bei mehreren Iterationen also der sukzessiven Berechnung der Pfade nach dieser Greedy-Methode [10] gegeben.

Da weiterhin jede gewählte Kante aus G entfernt wird, ist jede Kante in höchstens einem Pfad enthalten. Es kann der Fall eintreten, dass nach der Anwendung obiger Konstruktion eine Kante existiert, die in keinem Pfad p in P enthalten ist. Sei E' die Menge der nicht überdeckten Kanten. Da |O|=0 haben allerdings alle Knoten im Restgraphen G'=(V,E') geraden Grad und – je nach dem ob G' zusammenhängend ist oder nicht – hat G' somit einen – oder mehrere – Eulerkreise. Solche geraden Kreise führen, wie im Fall von eulerschen Graphen G, bei abwechselndem Aufund Abrunden der Kanten im Kreis immer zu einer zulässigen Lösung. Daher wollen wir zur Vereinfachung der Argumentation im Folgenden annehmen, dass E' leer ist.

Wir wenden nun das abwechselnde Aufund Abrunden der Kanten in p für jeden Pfad p in P an. Ob dabei zuerst aufoder abgerundet wird, wirkt sich zunächst nur auf die Kosten der resultierenden Disposition aus:

Die Kosten (Formel siehe PDF.) sind in den Kosten c(D|2(I)) enthalten und können über die Kanten eindeutig p zugeordnet werden. (Insbesondere gilt: (Formel siehe PDF.) Bezeichne (Formel siehe PDF.) die Kosten die in der gerundeten Disposition p zugeordnet werden können, falls in p mit dem Aufrunden der ersten Kante begonnen wird; (Formel siehe PDF.) ist analog definiert, wenn mit dem Abrunden der ersten Kante begonnen wird und c(p,r) bezeichne die p zugeordneten Kosten in der gerundeten Disposition D|2r(I). Wir runden jeden Pfad so, dass c(p,r)=min{c(p, auf), c(p, ab)}. Dann gilt:

Theorem 9:

D2R(I)=D2(I)-D|2(I)+D|2r(I) ist eine additive 1-Approximation der optimalen Disposition für I, die in polynomieller Zeit berechnet werden kann.

Zu jeder Verfügung d=(i(d), j(d), n(i,j)) in D|2r(I), gibt es eine entsprechende Disposition in D|2(I), zu der sich nur die Anzahl der verfügten Wagen auf ein ganzzahliges n(i,j) verändert hat. Daher ist auch erl(i(d),j(d)) und rec(i(d),j(d)) erfüllt. Die Anzahl verfügter Wagen hat sich maximal um ½ erhöht. Da sie zuvor halbzahlig war und d zulässig, v(t(i)), n(i) und n(j) jedoch ganzahlig, muss die Verfügung auch weiterhin zulässig sein.

Alle Pfade p in P verlaufen zwischen Knoten u und v aus (Formel siehe PDF.). Alle Knoten x werden von Pfad p genauso oft über inzidente Kanten betreten wie verlassen. Daher werden gleich viele Kanten aufund abgerundet, so dass D2R(I) die gleiche Wagenanzahl für Bestand i verfügt wie D2(I).

Das gleiche gilt für Bedarfe mit zugeordneten Knoten y in Y \ O. Für die Hälfte aller anderen Bedarfe j mit zugeordneten Knoten y in O wird genau eine Verfügung mehr abgerundet als aufgerundet. Dies beeinflusst nicht die Zulässigkeit von D2R(I). Lediglich für die restlichen Bedarfe j' mit zugeordneten Knoten y in O wird genau eine Verfügung mehr aufgerundet als abgerundet und daher ein einzelner zusätzlicher, nicht bestellter Wagen verfügt. Dies begründet die additive 1Approximation.

Die Kosten beider Dispositionen unterscheiden sich nur in c(D|2) und c(D|2r). Es gilt:

Formel siehe PDF.

Somit ist D2R(I) optimal, da (Formel siehe PDF.).

Theorem 9 ist insofern unbefriedigend, dass D2R(I) keine vollständige Zulässigkeit garantiert. Unter der Annahme, dass die Kosten r(i,j) die Dreiecksungleichung erfüllen, d.h. für drei beliebige Dispostellen A, B und C gilt r(A,C)≤r(A,B)+r(B,C) und zusätzlich bestimmte Erreichbarkeiten zwischen Dispostellen angenommen werden können, kann die Zulässigkeit unter höherem Kostenaufwand hergestellt werden.

Bezeichne U die Menge aller Bedarfe j', die durch D2R(I) übererfüllt wurden. Da dies durch Aufrunden einer halbzahligen Verfügung geschah, kann höchstens ein halber Wagen von Typ ty mehr nach j' disponiert worden sein, so dass j' bereits von D2(I) voll erfüllt wurde.

Dies ist – da der zu j' korrespondierende Knoten y in (Formel siehe PDF.) liegt – insbesondere nur möglich, wenn mindestens ein Wagen vom Typ tx durch eine ungeradzahlige Verfügung d=(i,j,n(i,j)=2k+1) in D2(I) von i nach j' verfügt wurde: Andernfalls wäre j' von D2(I) nicht voll erfüllt oder es gäbe eine gerade Anzahl halbzahliger Verfügungen im Widerspruch zu y in O. Daher muss insbesondere t(j)=tz sein.

Aufgrund des pfadbasierten Rundens korrespondiert zu jedem j' in U ein Bedarf j, der im Vergleich zu D2(I) von D2R(I) weniger gedeckt wird (am anderen Ende des Pfades). Sofern erl(i,j) und rec(i,j) erfüllt sind, können die Verfügungen d=(i,j',n(i,j')=2k+1) durch d'=(i,j',n(i,j')=2k) und d''=(i,j,n(i,j)=1) in D2R'(I) ersetzt werden. Damit ist D2R'(I) zulässig.

Die Kosten für Verfügungen d''=(i,j,n(i,j)=1) können über die ursprünglichen Kosten c(p) der eindeutig korrespondierenden Pfade p von j nach j' abgeschätzt werden:

Wir nehmen für die Kosten r(i,j) die Dreiecksungleichung an. Weiterhin korrespondiert zu jeder Kante im Pfad p eine Verfügung in D2(I) mit n(i,j)≥1/2.

Damit gilt:

Formel siehe PDF.

Da die Verfügungen d'' zu D2R(I) hinzukommen gilt insgesamt:

Korollar 10:

D2R'(I) ist eine 3-Approximation der optimalen Disposition für I, die in polynomieller Zeit berechnet werden kann.

6 Praktische Ergebnisse

Offenbar existiert D2R'(I) wie im letzten Abschnitt definiert nicht immer, da nicht zwingend passende Umverfügungen aus der Menge der Bedarfe j und j' in U gefunden werden. Erweitern wir die Menge der möglichen Umverfügungen auf alle noch offenen Bedarfe (inklusive Abstellkapazitäten), so kann eine zulässige Disposition gefunden werden.

In der Praxis wird daher – zur Zeit in einer Erprobungsphase – die 1-additive Approximation D2R(I) mit anschließender allgemeiner Umverfügung angewendet: Zunächst wird D2(I) berechnet und zu D2R(I) gerundet. Falls D2R(I) unzulässig ist, werden alle Verfügungen exklusive der überzählig zu Bedarfen j disponierten Wagen in eine entsprechende Reduktion der Bestände und Bedarfe umgesetzt und für die so reduzierte Instanz I' wird erneut eine Lösung D(I') berechnet. Nach Anwendung der 1-additiven Approximation ist sicher gestellt, dass nur Wagen vom Typ tx umdisponiert werden müssen. Somit ist D(I') immer ganzzahlig, da in I' keine 2:1-Substitution mehr vorliegt und das resultierende klassische Netzwerkmodell eine effiziente ganzzahlige Minimalkostenfluss-Berechnung erlaubt.

An eine Anwendung der 1-additiven Approximation schliesst sich demnach in den meisten Fällen eine Umverfügung von unzulässig disponierten Wagen an, ohne dass jedoch die Kosten der (hier beliebigen, aber zulässigen) Umverfügung abschätzbar sind. Für eine einzelne Anwendung der 1-additiven Approximation gilt nach Theorem 9 c(D2r(l))≤c(D2(l)). Bei anschliessender Umverfügung kann dieser Zusammenhang jedoch nicht auf die letztlich zulässige Disposition c(D2R(I)+D(I')) und c(D2(I)) übertragen werden. Wir verdeutlichen dies am Beispiel aus dem vorhergehenden Abschnitt, nehmen jedoch an, dass alle Kosten außer r(1,5) und r(3,4) gleich r sind. Die Kosten r(3,4)=r+e liegen nur unwesentlich über r, die Kosten r(3,4) jedoch mit R deutlich höher. Die halbzahlige Optimallösung ist weiterhin durch die Verfügungen D2(I)={(1,4,1), (2,5,1), (3,4,1/2), (3,5,1/2)} mit Kosten c(D2)=3r gegeben und in Abbildung 4 durch rote Pfeile innerhalb des generalisierten, modifizierten Flussnetzwerkes dargestellt.

Bild 4: Halbzahlige optimale Disposition (rot)

Bild 5: Reduzierte Instanz nach Runden der halbzahligen Disposition und entfernen des zulässigen Teils der Disposition

Die additive 1-Approximation rundet diese Lösung o.B.d.A. zu den Verfügungen (1,4,1), (2,5,1) und (3,5,1). Letztere disponiert einen überschüssigen Wagen zu Bedarf 5. Diese Verfügung wird damit zunächst nicht berücksichtigt. In Abbildung 6 ist das generalisierte, modifizierte Netzwerk der entsprechend reduzierten Instanz dargestellt. Jede Disposition wird hier zur einzig noch möglichen Verfügung (3,4,1) gezwungen. Die zulässige gerundete Lösung nach Umdisposition ist damit D2R(I)={(1,4,1), (2,5,1), (3,4,1)} mit Kosten c(D2R)=2r+R. Die Relation der Kosten (R/r) kann damit beliebig hohe Werte annehmen und es gibt keine approximative Kostengarantie.

Im Folgenden präsentieren wir einige Rechenergebnisse auf Instanzen mit realen Daten. Diesen Instanzen liegen die aggregierten Bestandsund Bedarfsdaten einer Kalenderwoche zu Grunde. Um eine möglichst realistische Testrechnung zu erhalten, wurden Bestände und Bedarfe nicht zufällig aus dieser Menge gezogen, sondern lediglich das Datenvolumen aus zeitlich sortierten Bestands und Bedarfslisten sukzessive erhöht. Dadurch entstandene einzelne Instanzen für jede Größe enthalten weiterhin eventuell vorliegende typische Bestandsund BedarfsKonstellationen.

Die Menge der jeweils in einer Instanz berücksichtigten aggregierten Bestände und Bedarfe wurde parallel ausgehend von 2000 bis zu 10000 in 1000er-Schritten erhöht. Damit entspricht der Datenumfang der generierten Instanzen in etwa einer Disposition mit einer Vorausschau von einem bis zu fünf Tagen (inklusive der Betrachtung halber Tage). Eine reale Instanz, die der Disposition für einen Tag entspricht, enthält ca. 2000-3000 aggregierte Bestände und eine eventuell größere Anzahl bekannter Bestellungen. Für die vorliegende Kalenderwoche lagen 5715 Bedarfe vor, so dass dies die Obergrenze der betrachteten Anzahl aggregierter Bedarfe darstellt.

Tabelle 1 gibt zunächst die Rahmendaten der betrachteten Instanzen I(x) an, wobei x die Anzahl der aggregierten Bestände und Bedarfe angibt. Die Spalte 'Bestand (2:1) (%)' enthält die Summe der disponiblen Wagen, in Klammern gefolgt von der Anzahl solcher Wagen, deren Wagentyp 2:1-substituieren kann und des prozentualen Anteils letzterer an der Gesamtzahl der Wagen im Bestand. Die Spalte 'Bedarf (2:1) (%)' ist analog aufgebaut. Die letzte Spalte enthält den allgemeinen Prozentsatz der an 2:1-Substitution beteiligten Wagen an der Summe verfügbarer und bestellter Wagen.

Tabelle 1: Betrachtete Instanzen des Dispositionsproblems

Wir sehen, dass der Prozentsatz der Bestände bzw. Bedarfe, deren Wagentypen an 2:1-Substitution beteiligt sind, mit im Schnitt 2,33% bzw. 4,44% und insgesamt 3,42% in realen Instanzen relativ niedrig ist. Aufgrund einiger hier nicht angeprochener Nebenbedingungen (z.B. gemeinsame Kontrolle der Abstellkapazitäten für alle Wagentypen), müssen die betroffenen Wagen jedoch auch im Kontext real großer Instanzen und nicht etwa separat betrachtet werden.

Beispielsweise kann es ohne Berücksichtigung der restlichen Disposition zu deutlich weniger halbzahligen Verfügungen kommen als in einer Gesamtlösung üblich wäre.

Dies hat Auswirkungen auf die Laufzeiten: Ist nach Berechnung der halbzahligen Optimallösung D2(I) und einmaligem Runden zu D2R(I) noch keine zulässige Disposition erreicht, so muss für die reduzierte Instanz I' erneut eine Disposition berechnet werden (Umverfügen der überzähligen Wagen). Dies benötigt im Vergleich zu reinem Runden mehr Zeit.

Tabelle 2 zeigt die Laufzeit für die Berechnung einer initialen halbzahligen Disposition D2 und einer zulässigen gerundeten Disposition D2R durch Anwendung der additiven 1-Approximation und Umverfügen in Abhängigkeit von der Instanzgröße.

Die letzte Spalte enthält die Gesamtzeit, die zur Berechnung einer gültigen Disposition notwendig war, jedoch ohne die benötigte Zeit für das Einlesen der Daten sowie den Aufbau des Netzwerkes aus den gegebenen Bestandsund Bedarfsdaten. (Das Einlesen der gesamten Daten dauerte in jedem Fall weniger als 5 Sekunden, wohingegen die Zeit des Netzwerkaufbaus von wenigen Sekunden bei der kleinsten Instanz bis zu 2,5 Minuten bei der größten Instanz dauerte. Alle Rechnungen wurden sequenziell auf einem einzelnen Cluster-Knoten, Intel Xeon CPU E5410, 2.33 GHz, 6144 KB RAM, ausgeführt.)

Zur Gesamtlaufzeit trägt die Anwendung der Heuristik für die größte Instanz bis zu einem Drittel bei. Neben dem Runden der halbzahligen Kanten (in linearer Zeit in der Anzahl der Kanten) war jeweils eine weitere Flussberechnung für die Umverfügung überzähliger Wagen notwendig. Letztere jedoch auf einer stark reduzierten Instanz.

Tabelle 2: Laufzeiten für die Berechnung der halbzahligen Optimallösung (D2) und der (iterierten) additiven 1-Approximation (D2R)

Tabelle 3 zeigt schließlich die Kosten c(D2(I)) und c(D2R(I)) der initialen halbzahligen Disposition D2(I) und der gerundeten zulässigen Disposition D2R(I) in den Spalten 2 und 3 (E+00x entspricht dabei ×10x). Weiterhin ist die Relation c(D2R(I))/c(D2(I)) der Kosten der zulässig gerundeten Lösung und der minimalen Kosten einer fraktionalen Lösung angegeben. Dieser empirische Approximationsfaktor demonstriert, dass es sich bei obigem Beispiel (Abbildung 4 und 5) um den in der Theorie üblichen 'schlimmsten Fall' handelt, der sich in der Praxis nur selten zeigt.

Weiterhin ist die Kostendifferenz (Spalte 4) und die prozentuale Kostendifferenz (Spalte 5) der zulässigen gerundeten Disposition gegenüber der halbzahligen Lösung angegeben. Die zu Grunde gelegten Kosten der halbzahligen Lösung sind allerdings nur eine untere Schranke der Kosten einer optimalen Disposition. Die minimalen Kosten einer ganzzahligen, also zulässigen Disposition c(D) können selbst deutlich höher liegen als c(D2). Damit ist ein Vergleich der Kosten c(D2R) einer zulässigen gerundeten Lösung zu c(D2) bezüglich der Approximationgüte zulässig. In der Praxis ist die Kostendifferenz zwischen c(D2) und c(D2R) allerdings niemals als reine Mehrkosten zu sehen, da eine zulässige Disposition mit Kosten c(D2) meist nicht existiert.

Tabelle 3: Kosten der halbzahligen optimalen Disposition c(D2) und der iterativ gerundeten zulässigen Disposition c(D2R)

7 Zusammenfassung und Ausblick

Wir haben für das Dispositionsproblem mit 2:1-Substitution zunächst die theoretische Komplexität untersucht und gesehen, dass eine effiziente ganzzahlige Optimallösung (unter der Annahme P≠NP, siehe [4]) nicht möglich ist.

In polynomieller Laufzeit kann jedoch eine halbzahlige Disposition berechnet werden, die zu einer additiven 1-Approximation der Optimallösung gerundet werden kann. Diese wird in der Praxis angewendet und durch Umverfügen von einzelnen Wagen ergänzt, um zu einer zulässigen Disposition zu gelangen.

Eine zulässige Disposition mit 3-approximativen Kosten durch Umverfügen einzelner Wagen kann mit dem in Abschnitt 5 erläuterten Ansatz in der Praxis nicht immer erreicht werden. Wir wollen in Zukunft weiter untersuchen, wie in diesem Fall zumindest die maximale Anzahl von Wagen so umverfügt werden kann, dass die Anzahl der übererfüllten Bedarfe (und damit die Unzulässigkeit der Disposition) minimiert wird.

Die Anzahl der möglichen Umverfügungen kann zum Einen durch Wahl der Rundungsrichtung (Aufoder Abrundens der jeweils ersten Kante) eines Pfades p in P beeinflusst werden. (Dadurch wird eventuell c(p,r)=min{c(p, auf), c(p, ab)} nicht mehr möglich. Da durch das Umverfügen ohnehin nur eine 3-Approximation der Kosten erreicht wird, ist dies jedoch kein Nachteil.) Die entsprechend günstigere Rundungsrichtung kann in polynomieller Zeit bestimmt werden.

Weiterhin hängt die Möglichkeit einer Umverfügung mit approximativ abschätzbaren Kosten (also eine Umverfügung von Bedarf j nach Bedarf j') davon ab, welche Paare von Bedarfen mit y in O durch einen Pfad p in P verbunden werden. Eine Beeinflussung der Pfadkonstruktion mittels vorab (aus anderen Kriterien wie z.B. der Umverfügungsmöglichkeit) bestimmten Bedarfspaaren führt zu einem weiteren NP-schwierigen und damit nicht effizient lösbaren Problem, dem Kantendisjunkte-Wege-Problem [4,11].

Wir untersuchen zur Zeit für welche Instanzen sich die vorgestellte 3-Approximation in polynomieller Zeit bezüglich der möglichen Umverfügungen verbessern lässt.

8 Literatur

[1] R.K. Ahuja, T.L. Magnati, J.B. Orlin: Network Flows – Theory, Algorithms and Applications. Prentice Hall, 1903.

[2] L.R. Ford, D.R. Fulkerson: Flows in Networks. Princeton University Press, Princeton, New Jersey, 1962.

[3] S. Sahni: Computationally Related Problems, SIAM Journal on Computing, 3, pp. 262-279, 1974.

[4] M. Garey and D. Johnson: Computers and Intractability: A guide to the theory of NP-completeness, W.H. Freeman, New York, 1979.

[5] R.G. Busaker and P.J. Gowen: A procedure for determining minimal-cost network flow patterns. ORO Technical Report 15. Operational Research Office, John Hopkins University, Baltimore, MD, 1961.

[6] W.S. Jewell: Optimal Flows through networks with gains. Operations Research 10, pp. 476-499, 1962.

[7] J.D. Oldham: Combinatorial Algorithms for Generalized Flow Problems. Journal on Algorithms 38, pp. 135-169, 2001.

[8] M. Restrepo und D. Williamson: A simple GAP-cancelling algorithm for the generalized maximum flow problem, SODA, ACM Press, pp.534-543, 2006.

[9] L. Euler: Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8, pp. 128-140, 1736.

[10] T.H.Cormen, C.E. Leiserson, R.L. Rivest and C. Stein: Introduction to Algorithms, MIT Press, Cambridge, Massachusettes, 2001.

[11] A. Frank: Packing paths, curcuits and cuts – a survey, in: B. Korte, L. Lovàsz, H.J. Prömel and A. Schrijver: Paths, Flows and VLSI-Layout,Springel, Berlin, pp. 47-100, 1990.