Algorithmic strategies for a fast exploration of the TSP $$4$$-OPT neighborhood
提出一种新算法来高效搜索旅行商问题的4-OPT邻域，平均复杂度约为O(n^2.5)，比完全枚举的O(n^4)快，实验表明其有效性。
Abstract We describe an effective algorithm for exploring the $$4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> -OPT neighborhood for the Traveling Salesman Problem. $$4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a $$\Theta (n^4)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>4</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> algorithm by complete enumeration, but a $$\Theta (n^3)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> algorithm also exists for a particular subset of symmetric $$4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at $$O(n^{2.5})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>2.5</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> ) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best $$4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> -OPT move, and discuss the strength of the $$4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> -OPT neighborhood compared to 2- and $$3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> -OPT.