Sukzessive Einbeziehung

Die Sukzessive Einbeziehung ist ein Algorithmus zum Lösen von kombinatorischen Optimierungsproblemen wie zum Beispiel dem Problem des Handlungsreisenden. Für diese Probleme liefert dieses heuristische Eröffnungsverfahren eine approximierte Lösung. Es wurde 1964 von Karg und Thompson entwickelt ^[1].

Die Sukzessive Einbeziehung gehört zu den Greedy-Algorithmen und lässt deswegen keine Aussage über die Qualität des Ergebnisses zu. In der Praxis sind die Ergebnisse jedoch meist besser als die anderer Methoden, wie zum Beispiel die Nearest-Neighbor-Heuristik.

Der Algorithmus beginnt mit einem Kreis bestehend aus 2 Punkten und fügt sukzessiv weitere Punkte sinnvoll in den Kreis ein, so dass zum Ende ein Hamiltonkreis entsteht, der alle Punkte beinhaltet.

Beispiel des Algorithmus

Bild 1: Kreis aus den Punkten A und B

Gegeben sind 6 Punkte, die sich in einem 2-dimensionalen Koordinatensystem befinden. Als Ausgangspunkt dienen der Punkt A und der Punkt B, die den
Kreis A – B – A bilden, wie in Bild 1 zu erkennen.

Bei dem ersten Schritt wird der minimale Abstand von einem weiteren Punkt zu den im Kreis enthaltenen Punkten berechnet. In diesem Fall sind das die Punkte A und B. Dieses vorgehen wird für alle Punkte wiederholt, die noch nicht eingebunden sind. Anschließend wird von den minimalen Abständen das Maximum gebildet und der entsprechende Punkt in den Kreis eingefügt. Im vorhandenen Beispiel ist das der Punkt C.

Bild 2: Kreis A - B - C, nach dem ersten Schritt

Der neue Kreis bildet nun die Route A - B - C - A.

An dieser Stelle spielt es für die Weglänge keine Rolle, zwischen welchen Punkten Punkt C in die Strecke eingefügt wird. Wenn jedoch 3 oder mehr Punkte vorhanden sind, wird der Punkt C so in den Kreis integriert, dass die resultierende Länge für diesen minimal ist.

Bei dem nächsten Schritt werden wieder die minimalen Abstände von den verbleibenden Punkten berechnet. Diesmal wird neben Punkt A und B auch der Punkt C berücksichtigt, da dieser nun in dem Kreis einbezogen ist.

Bild 3: gesamte berechnete Route

Es wird der Punkt E in den Kreis einbezogen. Hierbei ist es entscheidend, an welcher Stelle dieser Punkt eingefügt wird. Daher wird geprüft, welche Möglichkeit die geringste Strecke zur Folge hat. In diesem Fall kann der Punkt E wie folgt in den gesamten Kreis integriert werden:

A - B - C - E - A
A - B - E - C - A
A - E - B - C - A

Die zuletzt genannte Möglichkeit hat die minimale Streckenlänge zur Folge und wird daher gewählt.

Dieses Vorgehen wird so oft wiederholt, bis alle Punkte in dem Kreis integriert wurden. In Bild 3 ist der Streckenverlauf zu sehen, den der Algorithmus für dieses Beispiel berechnet hat.

Literatur

• Wolfgang Domschke: Logistik II Rundreisen und Touren, Band 2. München 2010 ISBN 978-3-486-59093-7
• Werner Zimmermann,Ulrich Stache: Operations-Research: quantitative Methoden zur Entscheidungsvorbereitung. München 2001 ISBN 3-486-25816-8

Quellen

1. ↑ : A Heuristic Approach to Solving Travelling Salesman Problems. In: Management Science. 10, Nr. 2, 1964, S. 225–248. doi:10.1287/mnsc.10.2.225.