2-opt

Last updated May 06, 2024

In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem. The 2-opt algorithm was first proposed by Croes in 1958,^[1] although the basic move had already been suggested by Flood.^[2] The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. A complete 2-opt local search will compare every possible valid combination of the swapping mechanism. This technique can be applied to the traveling salesman problem as well as many related problems. These include the vehicle routing problem (VRP) as well as the capacitated VRP, which require minor modification of the algorithm.

Pseudocode

Visually, one swap looks like:

 - A   B -             - A - B -      ×         ==>  - C   D -             - C - D -

In pseudocode, the mechanism by which the 2-opt swap manipulates a given route is as follows. Here v1 and v2 are the first vertices of the edges that are to be swapped when traversing through the route:

procedure 2optSwap(route, v1, v2) {     1. take route[0] to route[v1] and add them in order to new_route     2. take route[v1+1] to route[v2] and add them in reverse order to new_route     3. take route[v2+1] to route[start] and add them in order to new_route     return new_route; }

Here is an example of the above with arbitrary input:

Example route: A → B → E → D → C → F → G → H → A
Example parameters: v1=1, v2=4 (assuming starting index is 0)
Contents of new_route by step:
1. (A → B)
2. A → B → (C → D → E)
3. A → B → C → D → E → (F → G → H → A)

This is the complete 2-opt swap making use of the above mechanism:

repeat until no improvement is made {     best_distance = calculateTotalDistance(existing_route)     start_again:     for (i = 0; i <= number of nodes eligible to be swapped - 1; i++) {         for (j = i + 1; j <= number of nodes eligible to be swapped; j++) {             new_route = 2optSwap(existing_route, i, j)             new_distance = calculateTotalDistance(new_route)             if (new_distance < best_distance) {                 existing_route = new_route                 best_distance = new_distance                 goto start_again             }         }     } }

The particular nodes or depots that are at the start and at the end of the path should be removed from the search as an eligible candidates for swapping, as reversing the order would cause an invalid path.

For example, with depot at A:

   A → B → C → D → A

Swapping using node[0] and node[2] would yield

   C → B → A → D → A

which is not valid (does not leave from A, the depot).

Efficient implementation

Building the new route and calculating the distance of the new route can be a very expensive operation, usually $O(n)$ where $n$ is the number of vertices in the route. This can sometimes be skipped by performing a $O(1)$ operation. Since a 2-opt operation involves removing 2 edges and adding 2 different edges we can subtract and add the distances of only those edges.

lengthDelta = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])

If lengthDelta is negative that would mean that the new distance after the swap would be smaller. Once it is known that lengthDelta is negative, then we perform a 2-opt swap. This saves us a lot of computation.

C++ code

#include<algorithm>#include<random>#include<stdio.h>#include<vector>usingnamespacestd;classPoint{public:intx,y;Point(intx,inty){this->x=x;this->y=y;}Point(){this->x=0;this->y=0;}// Distance between two pointsinlineintdist(constPoint&other)const{returnsqrt((x-other.x)*(x-other.x)+(y-other.y)*(y-other.y));}};// Calculate the distance of the whole path (Squared Distances between points)intpathLengthSq(vector<Point>&path){intlength=0;for(inti=0;i<path.size();i++){length+=path[i].dist(path[(i+1)%path.size()]);}returnlength;}// Perform a 2-opt swapvoiddo2Opt(vector<Point>&path,inti,intj){reverse(begin(path)+i+1,begin(path)+j+1);}// Print the path. voidprintPath(stringpathName,vector<Point>&path){printf("%s = [",pathName.c_str());for(inti=0;i<path.size();i++){if(i%10==0){printf("\n    ");}if(i<path.size()-1){printf("[ %3d, %3d], ",path[i].x,path[i].y);}else{printf("[ %3d, %3d]",path[i].x,path[i].y);}}printf("\n];\n");}// Create a path of length n with random points between 0 and 1000vector<Point>createRandomPath(intn){vector<Point>path;for(inti=0;i<n;i++){path.push_back(Point(rand()%1000,rand()%1000));}returnpath;}intmain(){vector<Point>path=createRandomPath(100);printPath("path1",path);intcurLength=pathLengthSq(path);intn=path.size();boolfoundImprovement=true;while(foundImprovement){foundImprovement=false;for(inti=0;i<=n-2;i++){for(intj=i+1;j<=n-1;j++){intlengthDelta=-path[i].dist(path[(i+1)%n])-path[j].dist(path[(j+1)%n])+path[i].dist(path[j])+path[(i+1)%n].dist(path[(j+1)%n]);// If the length of the path is reduced, do a 2-opt swapif(lengthDelta<0){do2Opt(path,i,j);curLength+=lengthDelta;foundImprovement=true;}}}}printPath("path2",path);return0;}

Output

path1 = [    [ 743, 933], [ 529, 262], [ 508, 700], [ 256, 752], [ 119, 256], [ 351, 711], [ 705, 843], [ 393, 108], [ 366, 330], [ 932, 169],    [ 847, 917], [ 868, 972], [ 223, 980], [ 592, 549], [ 169, 164], [ 427, 551], [ 624, 190], [ 920, 635], [ 310, 944], [ 484, 862],    [ 301, 363], [ 236, 710], [ 431, 876], [ 397, 929], [ 491, 675], [ 344, 190], [ 425, 134], [  30, 629], [ 126, 727], [ 334, 743],    [ 760, 104], [ 620, 749], [ 932, 256], [ 613, 572], [ 509, 490], [ 405, 119], [  49, 695], [ 719, 327], [ 824, 497], [ 649, 596],    [ 184, 356], [ 245,  93], [ 306,   7], [ 754, 509], [ 665, 352], [ 738, 783], [ 690, 801], [ 337, 330], [ 656, 195], [  11, 963],    [  42, 427], [ 968, 106], [   1, 212], [ 480, 510], [ 571, 658], [ 814, 331], [ 564, 847], [ 625, 197], [ 931, 438], [ 487,  18],    [ 187, 151], [ 179, 913], [ 750, 995], [ 913, 750], [ 134, 562], [ 547, 273], [ 830, 521], [ 557, 140], [ 726, 678], [ 597, 503],    [ 893, 408], [ 238, 988], [  93,  85], [ 720, 188], [ 746, 211], [ 710, 387], [ 887, 209], [ 103, 668], [ 900, 473], [ 105, 674],    [ 952, 183], [ 787, 370], [ 410, 302], [ 110, 905], [ 996, 400], [ 585, 142], [  47, 860], [ 731, 924], [ 386, 158], [ 400, 219],    [  55, 415], [ 874, 682], [   6,  61], [ 268, 602], [ 470, 365], [ 723, 518], [ 106,  89], [ 130, 319], [ 732, 655], [ 974, 993]];path2 = [    [ 743, 933], [ 750, 995], [ 847, 917], [ 868, 972], [ 974, 993], [ 913, 750], [ 920, 635], [ 874, 682], [ 726, 678], [ 732, 655],    [ 830, 521], [ 900, 473], [ 893, 408], [ 931, 438], [ 996, 400], [ 932, 256], [ 952, 183], [ 968, 106], [ 932, 169], [ 887, 209],    [ 760, 104], [ 746, 211], [ 720, 188], [ 656, 195], [ 625, 197], [ 624, 190], [ 585, 142], [ 557, 140], [ 487,  18], [ 306,   7],    [ 245,  93], [ 187, 151], [ 169, 164], [ 106,  89], [  93,  85], [   6,  61], [   1, 212], [ 119, 256], [ 130, 319], [ 184, 356],    [ 301, 363], [ 337, 330], [ 366, 330], [ 410, 302], [ 344, 190], [ 393, 108], [ 405, 119], [ 425, 134], [ 386, 158], [ 400, 219],    [ 529, 262], [ 547, 273], [ 470, 365], [ 509, 490], [ 597, 503], [ 710, 387], [ 665, 352], [ 719, 327], [ 814, 331], [ 787, 370],    [ 824, 497], [ 754, 509], [ 723, 518], [ 649, 596], [ 571, 658], [ 613, 572], [ 592, 549], [ 480, 510], [ 427, 551], [ 268, 602],    [ 134, 562], [  55, 415], [  42, 427], [  30, 629], [  49, 695], [ 103, 668], [ 105, 674], [ 126, 727], [  47, 860], [  11, 963],    [ 110, 905], [ 179, 913], [ 223, 980], [ 238, 988], [ 310, 944], [ 256, 752], [ 236, 710], [ 334, 743], [ 351, 711], [ 491, 675],    [ 508, 700], [ 431, 876], [ 397, 929], [ 484, 862], [ 564, 847], [ 620, 749], [ 690, 801], [ 738, 783], [ 705, 843], [ 731, 924]];

Visualization

Related Research Articles

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

In information theory, the Hamming distance between two strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or equivalently, the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Algorithm for finding shortest paths

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In computing, a vector processor or array processor is a central processing unit (CPU) that implements an instruction set where its instructions are designed to operate efficiently and effectively on large one-dimensional arrays of data called vectors. This is in contrast to scalar processors, whose instructions operate on single data items only, and in contrast to some of those same scalar processors having additional single instruction, multiple data (SIMD) or SWAR Arithmetic Units. Vector processors can greatly improve performance on certain workloads, notably numerical simulation and similar tasks. Vector processing techniques also operate in video-game console hardware and in graphics accelerators.

In linear algebra, two vectors in an inner product space are orthonormal if they are orthogonal unit vectors. A unit vector means that the vector has a length of 1, which is also known as normalized. Orthogonal means that the vectors are all perpendicular to each other. A set of vectors form an orthonormal set if all vectors in the set are mutually orthogonal and all of unit length. An orthonormal set which forms a basis is called an orthonormal basis.

In computer networking, split-horizon route advertisement is a method of preventing routing loops in distance-vector routing protocols by prohibiting a router from advertising a route back onto the interface from which it was learned.

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by Alfonso Shimbel, but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.

In vector calculus, Green's theorem relates a line integral around a simple closed curve $C$ to a double integral over the plane region $D$ bounded by $C$ . It is the two-dimensional special case of Stokes' theorem.

In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. The Levenshtein distance between two words is the minimum number of single-character edits required to change one word into the other. It is named after Soviet mathematician Vladimir Levenshtein, who defined the metric in 1965.

Arc length is the distance between two points along a section of a curve.

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. However, in 2006 it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.

In mathematical optimization, the push–relabel algorithm is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.

<span class="mw-page-title-main">Recursion (computer science)</span> Use of functions that call themselves

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

Mason's gain formula (MGF) is a method for finding the transfer function of a linear signal-flow graph (SFG). The formula was derived by Samuel Jefferson Mason, for whom it is named. MGF is an alternate method to finding the transfer function algebraically by labeling each signal, writing down the equation for how that signal depends on other signals, and then solving the multiple equations for the output signal in terms of the input signal. MGF provides a step by step method to obtain the transfer function from a SFG. Often, MGF can be determined by inspection of the SFG. The method can easily handle SFGs with many variables and loops including loops with inner loops. MGF comes up often in the context of control systems, microwave circuits and digital filters because these are often represented by SFGs.

In computer science, the segment tree is a data structure used for storing information about intervals or segments. It allows querying which of the stored segments contain a given point. A similar data structure is the interval tree.

<span class="mw-page-title-main">Euclidean plane</span> Geometric model of the planar projection of the physical universe

In mathematics, a Euclidean plane is a Euclidean space of dimension two, denoted $or . It is a geometric space in which two real numbers are required to determine the position of each point. It is an affine space, which includes in particular the concept of parallel lines. It has also metrical properties induced by a distance, which allows to define circles, and angle measurement.$

In fracture mechanics, the energy release rate, $, is the rate at which energy is transformed as a material undergoes fracture. Mathematically, the energy release rate is expressed as the decrease in total potential energy per increase in fracture surface area, and is thus expressed in terms of energy per unit area. Various energy balances can be constructed relating the energy released during fracture to the energy of the resulting new surface, as well as other dissipative processes such as plasticity and heat generation. The energy release rate is central to the field of fracture mechanics when solving problems and estimating material properties related to fracture and fatigue.$

Velocity is the speed in combination with the direction of motion of an object. Velocity is a fundamental concept in kinematics, the branch of classical mechanics that describes the motion of bodies.

In mathematics, a line integral is an integral where the function to be integrated is evaluated along a curve. The terms path integral, curve integral, and curvilinear integral are also used; contour integral is used as well, although that is typically reserved for line integrals in the complex plane.

A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex $to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem.$

References

↑ G. A. Croes, A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.
↑ M. M. Flood, The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.

G. A. CROES (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.
M. M. FLOOD (1956). The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] G. A. Croes, A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.

[2] M. M. Flood, The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.

[1]

[2]