In diesem Abschnitt soll das Branch-and-Bound-Verfahren für ein Rundreiseproblem (Traveling-Salesman-Problem) aufgezeigt werden.
Methode
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
3. Schritt: In der reduzierten Kostenmatrix werden nun als nächstes die Nullelemente betrachtet. Für jedes Nullelement
4. Schritt: Für das ausgewählte Nullelement
(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
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.
Weitere interessante Inhalte zum Thema
-
Branch-and-Bound (TSP): Weitere Iterationen
Vielleicht ist für Sie auch das Thema Branch-and-Bound (TSP): Weitere Iterationen (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Branch-and-Bound-Verfahren
Vielleicht ist für Sie auch das Thema Branch-and-Bound-Verfahren (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.