ZU DEN KURSEN!

Operations Research 2 - Branch-and-Bound (TSP): 1. Iteration

Kursangebot | Operations Research 2 | Branch-and-Bound (TSP): 1. Iteration

Operations Research 2

Branch-and-Bound (TSP): 1. Iteration

In diesem und den folgenden Abschnitten soll das Branch-and-Bound-Verfahren am Traveling-Salesman-Problem (TSP) ausführlich behandelt werden. Die Schritte aus dem vorherigen Abschnitt sind dabei die Grundlage für die Anwendung des Verfahrens und werden im Folgenden nochmals aufgeführt und näher erläutert.

Gegeben sei die folgende Kostenmatrix mit den Umrüstungskosten $c_{ij}$ und den Produkten $i = 1, ... , 5$:

Kostenmatrix Branch and Bound


1. Schritt:  Die Kostenmatrix wird zunächst so umgeformt, dass alle nichtvorhandenen Verbindungen (Nullelemente) und alle extrem abweichenden Elemente $c_{32}$ gleich uendlich gesetzt werden:

Verfahren des besten Nachfolgers Kostenmatrix


2. Schritt: Die angepasste Kostenmatrix wird zeilen- und spaltenweise reduziert. Die Reduktionskonstante beträgt $k_R = 164$ (Summe der reduzierten Kosten in den Klammern). Dies entspricht auch gleichzeitig der oberen Schranke $s_0 = 164$.

Verfahren des besten Nachfolgers reduzierte Matrix


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. 

Für das Nullelement $c_{13}$ zum Beispiel wird demnach die Zeile $i =1$ und die Spalte $j = 3$ betrachtet und die zweitkleinste Elemente miteinander addiert:

$2 + 6 = 8$.

Dies sind die Kosten für die Teilstrecke $i \to j$: $1 \to 3$.

Dieses Vorgehen wird für jedes Nullelement durchgeführt, es ergibt sich:

Strecke$1 \to 3$   $2 \to 4$   $3 \to 1$   $4 \to 2$   $4 \to 5$   $5 \to 4$   
Summe848254

Es wird die maximale Summe gewählt. Da hier $1 \to 3$ als auch $3 \to 1$ dieselbe Summe aufweisen, wird diejenige Teilstrecke bevorzugt, die in der Ausgangsmatrix die geringsten Kosten aufweist. Dies ist die Strecke $3 \to 1$ mit $c_{31} = 32$. 


4. Schritt:
 Für das ausgewählte Nullelement $c_{ij}^*$ wird die zugehörige Spalte $j$ und Zeile $i$ gestrichen. Die Matrix wird wieder zeilen- und spaltenweise reduziert.

Es wurde also das Element $c_{ij}^* = c_{31}$ gewählt. Für dieses wird nun zunächst die Zeile $i = 3$ und die Spalte $j = 3$ gestrichen:

Rundreiseproblem Branch-and-Bound Verfahren

Da der Zyklus $3 \to 1 \to 3$ ausgeschlossen werden soll (es müssen schließlich noch weitere Knoten berücksichtigt werden), wird das Kostenelement $c_{13} = \infty'$ gesetzt.

Diese Matrix wird dann wieder zeilen- und spaltenweise reduziert:

Rundreiseproblem Branch-and-Bound Verfahren

Die obige Matrix ist zeilenweise reduziert worden (2) und spaltenweise (6). Insgesamt ergibt sich eine Reduktionskonstante von 8. Die Summe aus den zweitkleinsten Elemente für die betrachtete Teistrecke $3 \to 1$ und der Reduktionskonstante sind gleich. Es müssen demnach beide Äste verfolgt werden:

Rundreiseproblem Branch-and-Bound Verfahren

Die Schranke $s_1 = 172 ergibt sich, indem die Reduktionskonstante auf die obere Schranke $s_0$ addiert wird: $s_1 = 8 + 164 = 172$. Die Schranle $s_2 = 172$ ergibt sich, indem die Summe aus den zweitkleinsten Elemente auf die obere Schranke addiert wurde. 

Da beide Schranken denselben Wert aufweisen, muss für Schritt 4 sowohl der Fall (a) als auch der Fall (b) betrachtet werden. Es wird nun zunächst der Fall (a) betrachtet, d.h. die Teilstrecke $3 \to 1$ wird in die Tour aufgenommen. Im folgenden Abschnitt wird also der Ast mit $s_1 = 172$ weiterverfolgt. Hierfür wird die zuletzt betrachtete reduzierte Matrix mit der gestrichenen Zeile und Spalte herangezogen und wieder mit Schritt 3 begonnen.