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 where is the number of vertices in the route. This can sometimes be skipped by performing a 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 C++ code #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);