A special class of 4-opt moves plays a key role in several leading heuristics for the traveling salesman problem (TSP). However, the number of such moves is quite large – O(n4) for a graph of n nodes, on the order of the square of the number of 2-opt moves. Consequently, classical TSP heuristics have not attempted to seek best (and often not even improving) instances of these moves. We show that a best move from the collection that consists of these moves, together with an additional class of 4-opt moves and certain related 3-opt moves, can nevertheless be found in the same order of time required to find a best 2-opt move. Our method employs an acyclic shortest path model based on ideas introduced with ejection chain procedures and generates a sequence that can include improving moves at earlier stages. Joined with candidate list strategies that limit the tour edges available to be dropped, the method can also be structured to find best members from the set of implied surviving moves in O(n) time, making available TSP strategies for incorporating 4-opt moves that were previously beyond practical consideration.
