Resumen
Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the T(??3)
T
(
n
3
)
enumeration of all triples is likely to exist for this problem, but algorithms with average case ??(??3-??)
O
(
n
3
-
?
)
are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by ??(??2.5)
O
(
n
2.5
)
) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances.