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 und den Produkten :

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

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

3. Schritt: In der reduzierten Kostenmatrix werden nun als nächstes die Nullelemente betrachtet. Für jedes Nullelement wird die Summe aus den zweitkleineren Elementen der zugehörigen Spalte und Zeile 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 zum Beispiel wird demnach die Zeile und die Spalte betrachtet und die zweitkleinste Elemente miteinander addiert:

.

Dies sind die Kosten für die Teilstrecke : .

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

Es wird die maximale Summe gewählt. Da hier als auch dieselbe Summe aufweisen, wird diejenige Teilstrecke bevorzugt, die in der Ausgangsmatrix die geringsten Kosten aufweist. Dies ist die Strecke mit . 

4. Schritt: Für das ausgewählte Nullelement wird die zugehörige Spalte und Zeile gestrichen. Die Matrix wird wieder zeilen- und spaltenweise reduziert.

Es wurde also das Element gewählt. Für dieses wird nun zunächst die Zeile und die Spalte gestrichen:

Da der Zyklus ausgeschlossen werden soll (es müssen schließlich noch weitere Knoten berücksichtigt werden), wird das Kostenelement gesetzt.

Diese Matrix wird dann wieder zeilen- und spaltenweise reduziert:

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 und der Reduktionskonstante sind gleich. Es müssen demnach beide Äste verfolgt werden:

Die Schranke s_0s_1 = 8 + 164 = 172s_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 wird in die Tour aufgenommen. Im folgenden Abschnitt wird also der Ast mit weiterverfolgt. Hierfür wird die zuletzt betrachtete reduzierte Matrix mit der gestrichenen Zeile und Spalte herangezogen und wieder mit Schritt 3 begonnen.