Das  Briefträgerproblem - klassische Konstruktionsverfahren intelligente Strategien  I

Inhaltsverzeichnis

Abbildungs  - und Tabellenverzeichnis  II

Symbolverzeichnis.   III

Das  Briefträgerproblem als Optimierungsaufgabe 1.  1

Klassische  Konstruktionsverfahren 2.  2

2.1  Optimierung einer Briefträgertour in Graphen.  3

2.2  Optimierung einer Briefträgertour in Digraphen.  8

2.3  Das Briefträgerproblem in gemischten Multigraphen.  10

L  ösungsmöglichkeiten mittels heuristischer Algorithmen. 3.  11

3.1  Anwendungsmöglichkeiten von Meta-Heuristiken.  13

3.2  Anwendung des A - Algorithmus  

   19

Abschlie  ßende Bemerkungen 4.  21

Literaturverzeichnis.   22

Eidesstattliche  Erklärung  23

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien Abbildungs- und Tabellenverzeichnis

I Abbildungsübersicht

Abbildung 1: Ungerichteter Graph G = [V, E; c] ...................................... 7 Abbildung 2: Untergraph G‘ mit der Knotenmenge V u ............................. 7 Abbildung 3: Erweiterter Graph H............................................................. 8

Digraph G = …V, P; c ........................................................... Abbildung 4: 9 Abbildung 5: Transportnetzwerk ............................................................... 10 Abbildung 6: Digraph G A für Briefträgertour ............................................. 15 Abbildung 7: Darstellung von G A durch G B .............................................. 15

Graph G mit n c V u = 6........................................................ Abbildung 8: 17

Multigraph G m = …V, E, P; c  ............................................... Abbildung 9: 20 ^* 21 Abbildung 10: Optimale Erweiterung mit 1 = 48......................................

II Tabellenübersicht

Kürzeste Wege; i,j c V u ....................................................... 7 Tabelle 1: 10 Tabelle 2: Knotengrade in G................................................................. 15 Tabelle 3: Entfernungs- bzw. Kostenmatrix ......................................... 15 Tabelle 4: Wegematrix.......................................................................... 16 Tabelle 5: Tabu Search Verfahren ohne Verwendung von Attributen . 16 Tabelle 6: Zwei voneinander verschiedene optimale Briefträgertouren 17 Tabelle 7: Entfernungsmatrix für G‘..................................................... 18 Tabelle 8: Anwendungsbeispiel für einen Genetischen Algorithmus... Ablauf des A ^* - Algorithmus ............................................... 20 Tabelle 9:

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien Symbolverzeichnis

a i : Angebot des Knotens i in einem Transportnetzwerk b j Nachfrage des Knotens j in einem Transportnetzwerk

:

c : Bewertungsangabe von Kosten bzw. von Längen c ij : Kosten des Durchlaufes von Knoten i nach Knoten j : Gesamtgrad des Knotens i (i) d ij : Längenangabe zwischen Knoten i und Knoten j (hier: d ij = c ij ) : Grad des Knotens i (bei Kanten) (i) + (i) : Ausgangsgrad des Knotens i (bei Pfeilen) - (i) : Eingangsgrad des Knotens i (bei Pfeilen) D : Entfernungsmatrix E : Kantenmenge (engl. edge) : Teilmenge von Kanten E‘ ` E die in X ^* vorkommen E‘ E : Zu einem Graphen hinzugefügte Kanten : Alphabetische Bezeichnung von Kanten und Pfeilen G : Ungerichteter Graph mit Knoten und Kanten, kurz G = [V, E] G‘ : Untergraph von G, kurz G‘ = [V u , E] H : Ein in Bezug auf G um die Kanten E‘ erweiterter Graph, H = [V, E] G m : Gemischter Graph mit Knoten, Kanten und Pfeilen : Gerichteter Graph (Digraph) mit Knoten und Pfeilen, G = …V, P  G G‘ : Unterdigraph von G, entspricht einem Transportnetzwerk G e : Eulerscher Digraph G A : Darstellung des ursprünglichen CPP vor der Transformation G B : Knotenorientierte Darstellung von G ^A : Symbol für eine Briefträgertour i, j : Variablen zur Bezeichnung von Knoten h : Heuristik h * : Tatsächliche Länge bzw. Kosten des noch zu durchlaufenden Weges K ij : Kette zwischen Knoten i und Knoten j (evtl. über andere Knoten) m : Anzahl der in einem Graphen enthaltenen Kanten n : Anzahl der in einem Graphen enthaltenen Knoten N(x) : Nachbarschaft von x NN : Suchverfahren „nächster Nachbar“

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien

O : Landausches Symbol, Komplexitätsfunktion P : Pfeilmenge Q : Wegematrix

: Reihenfolge der Kante oder des Pfeils in einer Tour V : Knotenmenge (engl. vertex) : Knoten i,j c V u haben ungeraden Grad V u

: Knoten i,j c V g haben geraden Grad V g x s : Startlösung für die Anwendung von Meta-Heuristiken X : Symbol für ein perfektes minimales Summen-Matching z(x) : Zielfunktionswert von x * : Kennzeichnet Optimalität bezüglich der entsprechenden Variablen

Mathematische Symbole

c : Ist Element ` : Ist Teilmenge von O : Leere Menge < : Kleiner [ : Kleiner gleich g : Ist nicht gleich = : Ist gleich := : Definiert als

Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche L. Laboch

Kurzfassung

Das Briefträgerproblem wurde 1962 erstmals von dem chinesischen Mathematiker Mei-Ko Kwan formuliert und ist dem Bereich kombinatorischer Optimierungsprobleme zuzuordnen.

Der Briefträger muß in einem bestimmten Gebiet die Post für nahezu alle Haushalte verteilen. Um dies zu erreichen müssen alle Straßen oder Wege innerhalb seines Gebietes mindestens einmal durchlaufen werden. Start- und Endpunkt der Tour ist das Postamt. Gesucht ist eine Rundreise auf der jede Straße oder jeder Weg genau einmal durchlaufen wird, da dies eine kostenminimale Tour darstellt. Eine solche Tour ist aber nicht immer gegeben. In einem solchen Fall muß der Briefträger bereits abgearbeitete Teilstrecken erneut durchlaufen. Die Optimierungsaufgabe besteht darin, die Kosten dieser unproduktiven Teilstrecken zu minimieren. In bezug auf das zugrundeliegende Straßen- bzw. Wegenetz ergibt sich eine Dreiteilung des Briefträgerproblems. Es können zum Beispiel nur Straßen oder Wege vorliegen die frei in beide Richtungen passierbar sind. Ebenfalls können auch nur Einbahnstraßen vorhanden sein, oder es kann ein Mix aus beiden gegeben sein. Die ersten beiden Varianten sind gut mit exakten Algorithmen aus dem Bereich der Graphentheorie zu lösen. Bei einem Mix aus frei passierbaren Straßen und Einbahnstraßen stoßen diese Verfahren jedoch an ihre Grenzen. Für die Lösung dieser Problemausprägung sind sogenannte Meta-Heuristiken gut geeignet. Diese Methoden können selbstverständlich auch auf die beiden zuerst genannten Problemformulierungen anwendet werden. Sowohl Lösungsansätze unter Verwendung von Meta-Heuristiken als auch durch Zuhilfenahme klassischer Methoden der Graphentheorie werden in dieser Arbeit vorgestellt.

Schlüsselwörter

Briefträgerproblem, optimale Briefträgertour, Eulerscher Graph, Meta-Heuristiken, A ^* - Algorithmus.

Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche L. Laboch

Abstract

The Chinese Postman Problem was first formulated by the Chinese mathematician Mei-Ko Kwan in 1962 and it belongs to the class of combinatorial optimization. The postman has to deliver post to nearly every household in a defined area. For a successful delivery, every road or way has to be walked through at least for one time. The post-office marks the beginning and the ending of a postman’s roundtrip through his delivery area. It is necessary to find a tour where every road or way is only passed once because such a roundtrip leads to the minimum of costs. But it’s not possible to find such a tour for every given area. In this case, the postman has to walk again through roads or ways which he has passed already. The goal of optimization is to minimize the costs of those parts of a postman’s roundtrip. The Chinese Postman Problem can be divided into three sub-problems depending on the structure of the area. There can be only roads which can be passed in every direction or there can be only one-way roads or even a mix of both types. These sub-problems are known as the Undirected-, the Directed- and the Mixed-Chinese Postman Problem. The first two sub-problems can easily be solved with exact algorithms having their roots in the field of graph theory. These algorithms fail to achieve good resolutions on the Mixed-Chinese Postman Problem. The Mixed-Chinese Postman Problem can be solved by using so called metaheuristics. These metaheuristics can even be used to solve the Directed- and the Undirected-Chinese Postman Problem.

This paper gives an introduction how classic algorithms and modern metaheuristics can be used in various ways to solve the Chinese Postman Problem.

Keywords

Chinese Postman Problem, optimized postman-tour, Eulerian graph, metaheuristics, A ^* - Algorithm

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien Kapitel 1

Das Briefträgerproblem als Optimierungsaufgabe

Das Briefträgerproblem wurde erstmals im Jahre 1962 von dem chinesischen Mathematiker Mei-Ko Kwan behandelt. ¹ 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.

¹ Vgl. NEUMANN/MORLOCK (2002, S. 337).

² DOMSCHKE (1982, S. 108).

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien 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 G m = …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

³ Siehe auch NEUMANN/MORLOCK (2002, S. 338).

⁴ Ebenda.

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien 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. ⁵ 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 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 c ij 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 ^* 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. ⁶ 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 (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 aufweisen.

⁵ Siehe auch NEUMANN/MORLOCK (2002, S.338 - 345).

⁶ Vgl. LAWLER (1976, S.36f.).

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien 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 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‘ ` Vmit (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

Schritt 2: Ist G kein Eulerscher Graph wird ein zusammenhängender Untergraph

⁷ Siehe z.B. NEUMANN/MORLOCK (2002, S.212 - 214).

⁸ Ebenda (2002, S.219 - 225).

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien Schritt 3: In dem Untergraphen G‘ wird nun ein perfektes minimales Summen-

⁹ Siehe auch NEUMANN/MORLOCK (2002, Abschnitt 2.7).

¹⁰ Vgl. etwa CHRISTOFIDES (1982, S. 373 - 387)

oder JUNGNICKEL (1987, Abschnitt 11.2).

¹¹ Siehe z.B. CHRISTOFIDES (1975, Kapitel 12; insbesondere S. 359 - 373)

oder LAWLER (1976, Kapitel 6).

¹² Vgl. DOMSCHKE (1982, S. 118 - 120).

Das Briefträgerproblem - klassische Konstruktionsverfahren & intelligente Strategien

Schritt 4: Nach der Ermittlung des perfekten minimalen Summen-Matchings in

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

Beispiel 2.1

Der in Abbildung 1 dargestellte Graph G = [V, E; c] ist trotz seiner simplen Gestalt durchaus auf eine Variante des Briefträgerproblems in der Praxis übertragbar. In dünn besiedelten ländlichen Gegenden wird die Post häufig durch einen Briefträger zugestellt, der mit einem PKW von Dorf zu Dorf fährt und so den ganzen Tag die Post verteilt. Der gezeigte Graph möge nun das Straßennetz eines der zu besuchenden Dörfer repräsentieren.

Eine optimale Briefträgertour ^* ist nicht möglich, da der Graph die Knotenmenge V u = {1,2,3,6} mit ungeradem Grad enthält.

¹³ Siehe DOMSCHKE (1982, S. 119).