Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche

Kapitel 1

Das Briefträgerproblem als Optimierungsaufgabe

Das Briefträgerproblem wurde erstmals im Jahre 1962 von dem chinesischen Mathematiker Mei-Ko Kwan behandelt.^[1] Im angelsächsischen Sprachraum ist es, ihm zu Ehren, als Chinese Postman Problem (kurz: CPP) bekannt. Die zugrundeliegende Problematik kann wie folgt skizziert werden:

Ein Briefträger verteilt in seinem Zustellbezirk täglich die Post. Um sämtliche Empfänger zu erreichen und mit Post zu beliefern ist es notwendig, jede einzelne Straße seines Bezirks mindestens einmal zu durchlaufen. Zur optimalen Aufgabenerfüllung steht der Briefträger somit vor zwei Teilproblemen:

- Zum einen muß er eine geschlossene Tour, d.h. die Tour beginnt und endet an einem Punkt (dem Postamt), abarbeiten.
- Zum andern ist er daran interessiert die Tour so kurz wie möglich bzw. so effektiv wie möglich zu gestalten.

Werden diejenigen Teilwege auf denen keine Post verteilt wird als unproduktive Strecken bezeichnet, so läßt sich das Briefträgerproblem wie folgt formulieren:

„Der Briefträger interessiert sich für einen geschlossenen, jede zu bedienende Straße (...) enthaltenden Weg, in dem die Länge der unproduktiven Strecken so gering wie möglich ist.“^[2]

Eine analoge Aufgaben- bzw. Problemstellung ergibt sich z.B. für die Planung und Durchführung der Müllabfuhr oder Straßenreinigung sowie für die Festlegung kürzester Routen wenn es um das Ablesen von Zählerständen in Haushalten geht.

Das Briefträgerproblem kann sowohl mittels klassischer Konstruktionsverfahren aus dem Bereich der Graphentheorie, als auch mit Hilfe intelligenter Strategien bzw. heuristischer Algorithmen gelöst werden.

In Kapitel 2 werden Ansätze der Graphentheorie vorgestellt und anhand einfach gehaltener Beispiele verdeutlicht. Intelligente Strategien zur Lösung des Briefträgerproblems werden in Kapitel 3 dargestellt. Schließlich gibt Kapitel 4 einen kurzen Ausblick hinsichtlich verschiedener Varianten des CPP und der Bedeutung des Briefträgerproblems in Theorie und Praxis.

Kapitel 2

Klassische Konstruktionsverfahren

Dieses Kapitel ist den aus der Graphentheorie stammenden Konstruktionsverfahren gewidmet. Ein Graph besteht zunächst aus den zwei grundlegenden Elementen Knoten (V) und Kanten (E). Für das Briefträgerproblem seien nun Kreuzungen als Knoten und Straßen bzw. Wege als Kanten in einem Graphen definiert.

Bei der Postverteilung gibt es jedoch verschiedene Möglichkeiten die Straßen des Zustellgebietes zu durchlaufen:^[3]

- Die Straße kann beliebig in jede Richtung durchlaufen werden.
- Es liegt ein Wegenetz aus Einbahnstraßen vor.
- Das Straßennetz besteht aus einem Mix von beliebig zu durchlaufenden Straßen und solchen Straßen die nur in eine Richtung passiert werden können.

Entsprechend dieser verschiedenen Möglichkeiten der Straßenanordnung liegt bei der Optimierung in Graphen eine Dreiteilung des Briefträgerproblems vor. Sind die Straßen frei passierbar, so ist ein (ungerichteter) Graph G = [V, E; c] gegeben. Die Variable c steht für die Bewertung der einzelnen Teilwege und ist als Weglänge zu verstehen, wobei alternativ auch die Wegzeit ein gutes Bewertungskriterium darstellt. Gibt es zudem große Hauptstraßen auf denen der Briefträger jede Seite separat beliefert, so wird eine parallele Kante zwischen den entsprechenden Knoten eingefügt. In diesem Fall liegt ein Multigraph vor. Ist dagegen ein System von Einbahnstraßen gegeben, so liegt ein bewerteter (Multi-) Digraph G = ÓV, P; cÔ vor. Anstelle von Kanten (E) werden nun Pfeile (P) verwendet. Sind in dem Graphenmodell des Zustellungsgebietes Kanten und Pfeile angegeben, so handelt es sich um einen gemischten (Multi-) Graphen Gm = ÓV, E, P; cÔ.

Die Modellierung des CPP in gemischten Graphen entspricht den in der Praxis vorliegenden Gegebenheiten wohl am häufigsten. Aufgrund der Komplexität dieser Problemstellung ist eine exakte algorithmische Lösung bislang jedoch nicht mit polynomialem Rechenaufwand zu bewältigen.^[4]

Nachfolgend wird in Abschnitt 2.1 gezeigt, daß die Optimierung des CPP in Graphen auf die Bestimmung kürzester Wege und der Bestimmung eines minimalen Summen-Matchings hinausläuft. In Abschnitt 2.2 wird beschrieben, wie eine Optimierung in Digraphen durch die Lösung eines Transportproblems erreicht werden kann. Auf die Problemstellung in gemischten (Multi-) Graphen wird in Abschnitt 2.3 kurz eingegangen.

2.1 Optimierung einer Briefträgertour in Graphen

Zunächst müssen einige wesentliche Annahmen an den Graphen gestellt werden.^[5] Der Graph muß mindestens aus einer Kante und somit aus zwei Knoten bestehen. Des weiteren ist G zusammenhängend, d.h. alle Knoten von G sind direkt oder indirekt über eine Kantenfolge miteinander verbunden. Eine Briefträgertour g ist im folgenden eine geschlossene Kantenfolge, die jede in G enthaltene Kante mindestens einmal enthält. Bezüglich der Bewertung der Kanten ist anzumerken, das cij nicht negativ sein darf. Würden negativ bewertete Kanten existieren, so könnten diese beliebig oft durchlaufen werden ohne Kosten zu verursachen bzw. die auf den positiv bewerteten Kanten entstandenen Kosten reduzieren.

Hilfreich für die Konstruktion einer optimalen Briefträgertour g* in G ist der Zusammenhang zwischen einer Briefträgertour und einer geschlossenen Eulerschen Linie. Eine geschlossene Eulersche Linie in G ist eine geschlossene Kantenfolge, die jede Kante von G genau einmal enthält. Wenn ein solcher Weg in G existiert, wird G auch Eulerscher Graph genannt. Der schweizer Mathematiker und Physiker Leonard Euler (1707 – 1783) legte, so wird gesagt, bereits 1736 mit dem Königsberger Brückenproblem den Grundstein der Graphentheorie.^[6] Bei diesem Problem wird ein Weg über die sieben Brücken des Flusses Pregel gesucht wobei Start- und Endpunkt der Route identisch sein sollen und jede Brücke nur einmal passiert werden soll. Ein solcher Weg existiert jedoch für dieses spezielle Problem nicht.

Ein Weg, der jede Kante von G genau einmal enthält und zudem geschlossen ist, existiert genau dann, wenn der Grad d(i) eines jeden Knotens i c V gerade ist. Ein Eulerscher Graph liegt somit genau dann vor, wenn G zusammenhängend ist und sämtliche Knoten in G einen geraden Grad d aufweisen.

Der Beweis hierfür ist trivial, da auf einer Eulerschen Linie jeder Knoten genau so häufig besucht wie verlassen wird.

Für das Briefträgerproblem und die Optimierung einer Briefträgertour g in G bedeutet dies folgendes:

- Es liegt kein Optimierungsproblem vor wenn das als Graph modellierte Zustellgebiet des Briefträgers vom Typ eines Eulerschen Graphen ist.
- Ist G jedoch kein Eulerscher Graph, d.h. es gibt eine Knotenmenge V‘ ` V mit d(i) ungerade; i c V, so wird eine optimale Eulersche Vergrößerung H = [V, E; c] gesucht.

Die optimale Eulersche Vergrößerung wird durch Hinzufügen von Kanten in G erzeugt. Durch dieses Hinzufügen von Kanten E‘ in den nicht Eulerschen Graphen G soll dieser zu einem Eulerschen Graphen werden, d.h. es werden nach der Vergrößerung keine Knoten mit ungeradem Grad in G vorhanden sein. Optimal ist die Vergrößerung dann, wenn die Summe der Kosten bzw. der Länge der hinzugefügten Kanten minimal ist. Die Vorgehensweise gestaltet sich nun wie folgt:

Schritt 1: Zunächst wird der Graph G auf Knoten mit ungeradem Grad d untersucht. Gibt es keine Knotenmenge Vu mit ungeradem Grad, so kann eine geschlossene Eulersche Linie und damit eine Briefträgertour ohne weitere Optimierungsschritte angegeben werden.

Schritt 2: Ist G kein Eulerscher Graph wird ein zusammenhängender Untergraph G‘ von G erstellt. G‘ enthält lediglich die Knoten Vu, also diejenigen mit ungeradem Grad. G‘ ist hierbei automatisch zusammenhängend, da die Anzahl der Knoten i in G mit ungeradem Grad d(i) eine gerade Zahl ist. Dies liegt daran, daß die Summe der Knotengrade d(i); i c V genau 2xEx entspricht. Die Menge der Knoten i mit geradem Grad d(i) sei Vg. Aufgrund der geraden Knotengrade muß die Anzahl der Knoten i der Menge Vg eine gerade Zahl ergeben. Für die Knoten i der Menge Vu, also mit ungeradem Grad, gilt die Beziehung Vu = V / Vg und damit auch obige Aussage.

In dem Graphen G‘ werden nun kürzeste Ketten Kij zwischen allen Knoten i,j c Vu und die zugehörigen Entfernungen ermittelt. Dies kann beispielsweise mit dem Verfahren von Dijkstra^[7] oder dem Tripel-Algorithmus^[8] geschehen.

Schritt 3: In dem Untergraphen G‘ wird nun ein perfektes minimales Summen- Matching X* bestimmt. Ein Matching X in einem Graphen G = [V, E] ist eine Teilmenge E‘ der Kantenmenge E mit der Eigenschaft, daß keine zwei verschiedenen Kanten aus X mit ein und dem selben Knoten inzident sind.^[9] Perfekt ist ein Matching genau dann, wenn alle Knoten von G überdeckt sind. Perfekte Matchings gibt es somit nur in Graphen mit gerader Knotenanzahl n, da es genau n/2 Kanten enthalten muß. Für das Briefträgerproblem wird nun genau das perfekte Matching in G‘ gesucht, dessen Summe, ausgedrückt durch die Kantenbewertung cij bzw. die Kantenlänge dij, minimal ist.

Das Aufspüren solcher Matchings ist für bipartite Graphen bzw. Digraphen unter dem Namen „Zuordnungsproblem“ bekannt und eine Lösungsmöglichkeit des Problems besteht in der Anwendung der Ungarischen Methode.^[10] Bei der Konstruktion einer optimalen Briefträgertour in Graphen ist der in Schritt 2 erstellte Untergraph G‘ außer im Falle von Vu = 2 nicht bipartit. Die Lösungsverfahren für den allgemeinen, nicht bipartiten Graphen sind jedoch sehr komplex und würden hier nicht wesentlich zum Verständnis der eigentlichen Methode beitragen. Für die Lösung von Matchings im allgemeinen Fall sei daher auf weiterführende Literatur^[11] verwiesen.

In einfachen, d.h. überschaubaren, Untergraphen G‘ (mit ca. vier bis acht Knoten) kann ein adäquates Matching jedoch auch durch „genaues Hinsehen“ leicht ermittelt werden. Eine weitere Möglichkeit besteht darin, das perfekte minimale Summen-Matching Problem als symmetrisches Zuordnungsproblem zu formulieren und durch die Anwendung der Ungarischen Methode zu lösen.^[12] Diese Methode führt leider nicht automatisch zum Erfolg, da die Symmetriebedingung (2.5), siehe folgende formale Darstellung, i.d.R. nicht automatisch erfüllt wird. Für kleinere Untergraphen ist aber ein Versuch lohnenswert, da eine gute Erfolgschance besteht und der Rechenaufwand recht gering ist.

Formale Darstellung des symmetrischen Zuordnungsproblems:

Abbildung in dieser Leseprobe nicht enthalten

Sollten die durch die ungarische Methode ermittelten unabhängigen Nullen keine symmetrische Anordnung haben, so besteht die Möglichkeit der Anwendung des Branch-and-Bound Verfahrens zur Lösung des symmetrischen Rundreiseproblems.^[13]

Schritt 4: Nach der Ermittlung des perfekten minimalen Summen-Matchings in dem Untergraph G‘ wird der ursprüngliche Graph G = [V, E; c] erweitert. Die Erweiterung erfolgt durch das Hinzufügen von denjenigen Kanten E‘, die mit einer in Schritt 3 ermittelten Kette [ik, ik+1, ..., jl] c X* übereinstimmen. Der so entstandene erweiterte Graph H = [V, E; c] enthält nun keine Knoten i mit ungeradem Grad d(i) mehr. Es kann somit eine Eulersche Linie und damit auch eine optimale Briefträgertour angegeben werden.

Ein bewußt einfach und übersichtlich gehaltenes Beispiel soll die Vorgehensweise verdeutlichen, wobei hier und im folgenden Knoten 1 als Start- und Endknoten gilt.

[...]

^[1] Vgl. NEUMANN/MORLOCK (2002, S. 337).

^[2] DOMSCHKE (1982, S. 108).

^[3] Siehe auch NEUMANN/MORLOCK (2002, S. 338).

^[4] Ebenda.

^[5] Siehe auch NEUMANN/MORLOCK (2002, S.338 – 345).

^[6] Vgl. LAWLER (1976, S.36f.).

^[7] Siehe z.B. NEUMANN/MORLOCK (2002, S.212 – 214).

^[8] Ebenda (2002, S.219 – 225).

^[9] Siehe auch NEUMANN/MORLOCK (2002, Abschnitt 2.7).

^[10] Vgl. etwa CHRISTOFIDES (1982, S. 373 – 387)

oder JUNGNICKEL (1987, Abschnitt 11.2).

^[11] Siehe z.B. CHRISTOFIDES (1975, Kapitel 12; insbesondere S. 359 – 373)

oder LAWLER (1976, Kapitel 6).

^[12] Vgl. DOMSCHKE (1982, S. 118 – 120).

^[13] Siehe DOMSCHKE (1982, S. 119).