K-Opt-Heuristik

Die k-Opt-Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (TSP). Die k-Opt-Heuristiken gehören zu den (engl.: Nach-Optimierung), die sich dadurch auszeichnen, dass sie eine bereits gefundene Lösung weiter verbessern. Die Grundidee besteht darin, Kanten aus einer gegebenen Tour zu entfernen und gegen andere Kanten auszutauschen, so dass sich wieder eine Tour ergibt. Ist die neue Tour kürzer als die alte, wird sie als neue Lösung verwendet.