How about adding simulated annealing?

[0wwafa]

something like this:

// Add Simulated Annealing function to the TSP library
Tour simulated_annealing(const IntMatrix& dists, float duration_seconds, double initial_temperature = 1.0, double cooling_rate = 0.99, double min_temperature = 0.01) {
    uint_fast16_t n = dists.size();
    Tour current_tour = greedy_nearest_neighbor(dists);
    uint_fast32_t current_cost = compute_cost(n, current_tour, dists);
    Tour best_tour = current_tour;
    uint_fast32_t best_cost = current_cost;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<double> dis(0.0, 1.0);

    double temperature = initial_temperature;

    clock_t clock_begin = clock();

    while (!is_time_exceeded(clock_begin, duration_seconds) && temperature > min_temperature) {
        Tour neighbor_tour = double_bridge_move(n, current_tour);
        uint_fast32_t neighbor_cost = compute_cost(n, neighbor_tour, dists);

        if (neighbor_cost < current_cost) {
            current_tour = neighbor_tour;
            current_cost = neighbor_cost;

            if (current_cost < best_cost) {
                best_tour = current_tour;
                best_cost = current_cost;
            }
        } else {
            double probability = std::exp(-(neighbor_cost - current_cost) / temperature);
            if (dis(gen) < probability) {
                current_tour = neighbor_tour;
                current_cost = neighbor_cost;
            }
        }

        temperature *= cooling_rate;
    }

    return best_tour;
}

[shmulvad]

Can you give a motivation for why it should be added?

[0wwafa]

to improve the results?! fine tune...

[shmulvad]

When this project was initially written, some experiments were conducted with simulated annealing, but it was found to be worse than what is implemented now.

If you can show me some benchmarks that it indeed is faster or results in better TSP solutions within the same amount of time, I would be open to adding it.

[shmulvad]

Closed due to inactivity.