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 "paal/local_search/2_local_search/2_local_search.hpp"
#include "paal/data_structures/cycle/cycle_algo.hpp"
#include "paal/data_structures/cycle/simple_cycle.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());
    typedef data_structures::simple_cycle<int> Cycle;
    Cycle cycle(v.begin(), v.end());
    std::cout << "Length \t" << get_cycle_length(gm, cycle) << std::endl;

    // search
    tsp_first_improving(cycle, get_default_two_local_components(gm));

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

References

The algorithm is described in [19]. The approximation ratio is proved in [5].