2-opt for Traveling Salesman Problem

# Problem definition.

In the Traveling Salesman Problem (TSP) we are given set of nodes and metric m. Our goal is to find such permutation of nodes $$(a_1, a_2, ... ,a_n)$$ such that the sum $$m(a_1, a_2) + m(a_2, a_3) + ... + m(a_(n-1),a_n) + m(a_n, a_1)$$ is minimized.

# Solution

We solve this problem by local search, using well known 2-opt moves (see paal::local_search::two_local_search::TwoLocalSearchStep for more details).

# Example

#include "test/test_utils/sample_graph.hpp"
#include <vector>
#include <iostream>
using namespace paal::local_search;
using namespace paal;
int main() {
// sample data
typedef sample_graphs_metrics SGM;
auto gm = SGM::get_graph_metric_small();
const int size = gm.size();
std::cout << size << std::endl;
std::vector<int> v(size);
std::iota(v.begin(), v.end(), 0);
// create random solution
std::random_shuffle(v.begin(), v.end());
Cycle cycle(v.begin(), v.end());
std::cout << "Length \t" << get_cycle_length(gm, cycle) << std::endl;
// search
// printing
std::cout << "Length \t" << get_cycle_length(gm, cycle) << std::endl;
return 0;
}

example file is 2_local_search_example.cpp

# Approximation Ratio

Approximation ratio equals $$4\sqrt{n}$$ and $$O(log(n)/log(log(n)))$$ for euclidean instances in $$R^2$$. Although the approximation ratio is weak, the algorithm works well in many practical instances.

# Complexity

The complexity of each round of the algorithm is $$O(n^2)$$, where n is nuber of vertices in the space.