2-opt

2-opt

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, although the basic move had already been suggested by Flood. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not.

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

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.

This is the mechanism by which the 2-opt swap manipulates a given route. 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) {
    1. take route[0] to route[v2] and add them in order to new_route
    2. take route[v1+1] to route[v1] 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
            }
        }
    }
}

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[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.

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

#include <algorithm>
#include <random>
#include <stdio.h>
#include <vector>

using namespace std;

class Point {
  public:
	int x, y;

	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
	Point() {
		this->x = 0;
		this->y = 0;
	}

	// Distance between two points squared
	inline int dist2(const Point &other) const {
		return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
	}
};

// Calculate the distance of the whole path (Squared Distances between points)
int pathLengthSq(vector<Point> &path) {
	int length = 0;
	for (int i = 0; i < path.size(); i++) {
		length += path[i].dist2(path[(i + 1) % path.size()]);
	}
	return length;
}

// Perform a 2-opt swap
void do2Opt(vector<Point> &path, int i, int j) {
	reverse(begin(path) + i + 1, begin(path) + j + 1);
}

// Print the path. 
void printPath(string pathName, vector<Point> &path) {
	printf("%s = [", pathName.c_str());
	for (int i = 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 betweeen 0 and 1000
vector<Point> createRandomPath(int n) {
	vector<Point> path;
	for (int i = 0; i < n; i++) {
		path.push_back(Point(rand() % 1000, rand() % 1000));
	}
	return path;
}

int main() {
	vector<Point> path = createRandomPath(100);
	printPath("path1", path);

	int curLength = pathLengthSq(path);
	int n = path.size();
	bool foundImprovement = true;
	while (foundImprovement) {
		foundImprovement = false;
		for (int i = 0; i <= n - 2; i++) {
			for (int j = i + 1; j <= n - 1; j++) {
				int lengthDelta = -path[i].dist2(path[(i + 1) % n]) - path[j].dist2(path[(j + 1) % n]) + path[i].dist2(path[j]) + path[(i + 1) % n].dist2(path[(j + 1) % n]);

				// If the length of the path is reduced, do a 2-opt swap
				if (lengthDelta < 0) {
					do2Opt(path, i, j);
					curLength += lengthDelta;
					foundImprovement = true;
				}
			}
		}
	}

	printPath("path2", path);
	return 0;
}

See also

• 3-opt
• local search (optimization)
• Lin–Kernighan heuristic

References

• 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

• The Traveling Salesman Problem: A Case Study in Local Optimization
• Improving Solutions: 2-opt Exchanges