2-opt
   HOME

TheInfoList



OR:

In
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, 2-opt is a simple local search algorithm for solving the
traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or 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 cit ...
. The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood.M. M. Flood, The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75. 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 The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises t ...
(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 you wish to swap when traversing through the route: procedure 2optSwap(route, v1, v2) 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: *# (A → B) *# A → B → (C → D → E) *# 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 Note: If you start/end at a particular node or depot, then you must remove this from the search as an eligible candidate for swapping, as reversing the order will cause an invalid path. For example, with depot at A: A → B → C → D → A Swapping using node and node 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 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 1 route
1+1 1 (one, unit, unity) is a number representing a single or the only entity. 1 is also a numerical digit and represents a single unit of counting or measurement. For example, a line segment of ''unit length'' is a line segment of length 1 ...
- dist(route 2 route 2+1 + dist(route
1+1 1 (one, unit, unity) is a number representing a single or the only entity. 1 is also a numerical digit and represents a single unit of counting or measurement. For example, a line segment of ''unit length'' is a line segment of length 1 ...
route 2+1 + dist(route 1 route 2 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. Also using squared distances there helps reduce the computation by skipping a square root function call. Since we only care about comparing two distances and not the exact distance, this will help speed things up. It's not much, but it helps with large datasets that have millions of vertices


C++ code

#include #include #include #include using namespace std; class Point ; // Calculate the distance of the whole path (Squared Distances between points) int pathLengthSq(vector &path) // Perform a 2-opt swap void do2Opt(vector &path, int i, int j) // Print the path. void printPath(string pathName, vector &path) // Create a path of length n with random points betweeen 0 and 1000 vector createRandomPath(int n) int main()


Output

path1 = ____ ____[_743,_933_[_529,_262">743,_933.html"_;"title="____[_743,_933">____[_743,_933_[_529,_262_[_508,_700.html" ;"title="743,_933_[_529,_262.html" ;"title="743,_933.html" ;"title=" [ 743, 933"> [ 743, 933 [ 529, 262">743,_933.html" ;"title=" [ 743, 933"> [ 743, 933 [ 529, 262 [ 508, 700">743,_933_[_529,_262.html" ;"title="743,_933.html" ;"title=" [ 743, 933"> [ 743, 933 [ 529, 262">743,_933.html" ;"title=" [ 743, 933"> [ 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.html" ;"title="743,_933.html" ;"title=" [ 743, 933"> [ 743, 933 750, 995 [ 847, 917">743,_933.html" ;"title=" [ 743, 933"> [ 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


See also

* 3-opt *
local search (optimization) In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate s ...
*
Lin–Kernighan heuristic In combinatorial optimization, Lin–Kernighan is one of the best heuristic algorithm, heuristics for solving the symmetric travelling salesman problem. It belongs to the class of Local search (optimization), local search algorithms, which take a t ...


References

* * {{cite book, author = M. M. FLOOD , year = 1956 , title = The traveling-salesman problem , publisher = Operations Res. 4 (1956), pp., 61-75.


External links


The Traveling Salesman Problem: A Case Study in Local Optimization
Heuristic algorithms Travelling salesman problem