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.
Die Optimalitaet ist derzeit nicht bewiesen, jedoch konnten viele
Beispielprobleme (darunter einige aus der TspLib) erfolgreich geloest
werden. 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 lassen vermuten, dass diese Variante auch einen ATSP loesen kann.