Loest einen (a)symmetrischen TSP.
Dies ist eine Eigenkomposition, die sowohl auf dem
TspS
,
als auch auf dem
TspA
beruht. Die Kernidee ist, die Bounds
der restlichen Kanten selektiv neu zu berechnen, anstatt einfach
nur den Vorgaenger und Nachfolger nach Herausnahme der Zwischenstation,
wenn Teil der Anfangs-Tour, zu ueberbruecken.
Bei letzterem sinken die Bounds pro Station stetig. Das Wegnehmen von
Kanten sollte einzelne Bounds aber auch wieder steigen lassen duerfen.
Zudem werden die initialen Bounds analog des
TspS
berechnet.
Diese sind hoeher als die des
TspA
, da ja TwoTour-Theorie.
Diese Variante konnten bereits viele Beispielprobleme
(darunter einige aus der TspLib) erfolgreich loesen. Das hier zusaetzlich
erforderliche O(n) fuer die Bounds-Berechnung ist in kleineren
Problemstellungen dem O(1) des
TspS
unterlegen,
zeigt aber mit steigender Groesse des Problems seine Ueberlegenheit.
Neue Tests zeigen, dass diese Variante haeufig bis sehr dicht an eine
optimale Loesung herankommt.