ZU DEN KURSEN!

Operations Research 2 - Branch-and-Bound Verfahren am Traveling-Salesman-Problem

Kursangebot | Operations Research 2 | Branch-and-Bound Verfahren am Traveling-Salesman-Problem

Operations Research 2

Branch-and-Bound Verfahren am Traveling-Salesman-Problem

In diesem Abschnitt soll das Branch-and-Bound-Verfahren für ein Rundreiseproblem (Traveling-Salesman-Problem) aufgezeigt werden. 

Methode

Hier klicken zum Ausklappen

Vorgehensweise: Branch-and-Bound am Traveling-Salesman-Problem

1. Schritt: Die Kostenmatrix wird zunächst so umgeformt, dass alle nichtvorhandenen Verbindungen (Nullelemente) und alle extrem abweichenden Elemente gleich unendlich gesetzt werden.

2. Schritt: Die angepasste Kostenmatrix wird zeilen- und spaltenweise reduziert. Hierfür wird das kleinste Element einer Zeile von allen anderen Elementen der Zeile subtrahiert. Dies führt dazu, dass sich nun in jeder Zeile ein Nullelement befindet. Danach werden die Spalten überprüft. Befindet sich in einer Spalte kein Nullelement, so wird das kleinste Element der Spalte von allen anderen Elementen in der Spalte subtrahiert. Die Summe der subtrahierten Elemente ist die Reduktionskonstante und stellt gleichzeitig die obere Schranke $s_0$ dar. 

3. Schritt: In der reduzierten Kostenmatrix werden nun als nächstes die Nullelemente betrachtet. Für jedes Nullelement $c_{ij}$ wird die Summe aus den zweitkleineren Elementen der zugehörigen Spalte $j$ und Zeile $i$ bestimmt. Dabei wird die größte Summe ausgewählt. Bei zwei gleichen Summe, ist eine beliebig zu wählen. Sinnvoll ist es aber, die Teilstrecke mit derjenigen Summe zu wählen, die in der Ausgangsmatrix (nicht reduziert) die geringsten Kosten aufweist. 

4. Schritt: Für das ausgewählte Nullelement $c_{ij}^*$ wird die zugehörige Spalte $j$ und Zeile $i$ gestrichen. Es wird das Kostenelement $c_{ji} = \infty'$ gesetzt damit kein Zyklus entsteht und dann die Matrix wird wieder zeilen- und spaltenweise reduziert.

(a) Ist die sich hier ergebene erneute Reduktionskonstante kleiner als die Summe der zweitkleinsten Elemente in Schritt 3, so wird dieser Ast weiterverfolgt. Es wird dann hierfür die reduzierte Matrix mit der gestrichenen Zeile und Spalte gewählt. Die Reduktionstionskonstante muss auf die obere Schranke addiert werden und ergibt die neue obere Schranke. Dieser Ast bedeutet, dass die Tour mit aufgenommen wird. Es wird wieder Schritt 3 betrachtet.

(b) Ist hingegen die sich ergebene Reduktionskonstante größer als die Summe aus den zweitkleinsten Elemente aus Schritt 3, so wird dieser Ast weiterverfolgt. Hierbei muss nun aber die Matrix aus Schritt 2 herangezogen werden (ohne Streichung von Zeile und Spalte). Dann wird das Kostenelement $c_{ij}^* = \infty$ gesetzt und die Matrix reduziert. Die sich ergebene Reduktionskonstante ist gleich der Summe der zweitkleinsten Elemente und muss auf die obere Schranke addiert werden. Es ergibt sich eine neue obere Schranke. Dieser Ast bedeutet, dass die Tour nicht berücksichtigt wird. Es wird wieder Schritt 3 betrachtet.

Sind beide Werte gleich groß, so müssen beide Äste verfolgt werden. Es muss also sowohl (a) als auch (b) durchgeführt werden.

Das Verfahren soll in den folgenden Abschnitten ausführlich anhand des Rundreiseproblems aus dem Abschnitt Vollständige Enumeration durchgeführt werden.