TSP Ruin and Recreate greedy implementation with random+sequential+radial ruins

pcb442.cpp

//
// Developemnt of this gist is stopped, no further updates.
//
// This is the equivalent of this gist in new RR repo:
// https://github.com/Hermann-SW/RR/blob/main/tsp/greedy.cpp
//
// Code is split up, and a loader was added allowing for differnt problems.
// In addition that repo has 111 TSP problems with 108 corresponding
// optimal tours.
/*
hermann@7950x:~/RR/tsp$ make clean
rm -f load_test greedy
hermann@7950x:~/RR/tsp$ make greedy
g++ -O3 -std=c++20  -Wall -Wextra -pedantic greedy.cpp -o greedy -lstdc++ -lm
hermann@7950x:~/RR/tsp$ 
hermann@7950x:~/RR/tsp$ perf stat -e cycles,task-clock ./greedy 205 ../data/tsp/pcb442
50933           local minimum found (after 100,000 greedy mutations)
5854           ms (only recreate)
50778           global minimum

 Performance counter stats for './greedy 205 ../data/tsp/pcb442':

    37,708,902,114      cycles                           #    5.493 GHz                       
          6,864.89 msec task-clock                       #    1.000 CPUs utilized             

       6.865929950 seconds time elapsed

       6.864255000 seconds user
       0.001000000 seconds sys


hermann@7950x:~/RR/tsp$ 
*/

/*
   TSP Ruin and Recreate greedy implementation with random+sequential+radial ruins:
   https://www.semanticscholar.org/paper/Record-Breaking-Optimization-Results-Using-the-Ruin-Schrimpf-Schneider/4f80e70e51e368858c3df0787f05c3aa2b9650b4

   c++ -O3 -std=c++17 -Wall -Wextra -pedantic pcb442.cpp -o pcb442 -lstdc++ -lm
   (tested with g++ and clang++)

   for tour display
   - append compiler flags "-Dezxdisp -lezx -lX11"
   - after "make install" of ezxdisp repo first: 
   https://github.com/Hermann-SW/ezxdisp?tab=readme-ov-file#support-for-c--use-in-ide
   (left mouse click continues to next accepted mutation and updates display; repeat)

   cpplint --filter=-legal/copyright,-runtime/references pcb442.cpp
   cppcheck --enable=all --suppress=missingIncludeSystem pcb442.cpp
*/
#include <sys/time.h>
auto _sum = 0;
struct timeval _tv0;
#define _tim gettimeofday(&_tv0, NULL)
#define _start (_tim, _sum -= (1000000*_tv0.tv_sec + _tv0.tv_usec));
#define _stop  (_tim, _sum += (1000000*_tv0.tv_sec + _tv0.tv_usec));

#ifdef ezxdisp
#include <unistd.h>
#include <ezxdisp.h>
#endif

#include <sstream>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cassert>
#include <vector>
#include <list>

std::string i2s(int x) { std::stringstream s2; s2 << x; return s2.str(); }

template <typename C>
[[maybe_unused]] void print(const C& L) {
  std::for_each(L.begin(), L.end(), [](const typename C::value_type i) {
                                      std::cout << i << " ";
                                    });
  std::cout << '\n';
}

template <typename urn>
typename urn::value_type edraw(urn& U) {
  auto r = random() % U.size();
  typename urn::value_type ret = U[r];
  U[r] = U.back();
  U.pop_back();
  return ret;
}

template <typename val, int N>
class random_access_list {
  std::list<val> L;

 public:
  typedef typename std::list<val>::iterator iterator;
  iterator A[N];

  void init() {
    L.clear();
    for (int i = 0; i < N; ++i)  A[i] = L.end();
  }

  iterator& operator[](std::size_t i)  { return A[i]; }

  void sort()  { L.sort(); }
  void push_back(val& v )  { L.push_back(v); A[v] = --L.end(); }
  iterator insert(iterator it, val& v )  { return A[v] = L.insert(it, v); }
  iterator erase(iterator it)  { A[*it] = L.end(); return L.erase(it); }
  iterator erase(int i)  {
    iterator it = A[i]; A[i] = L.end(); return L.erase(it);
  }
  iterator begin()  { return L.begin(); }
  iterator end()  { return L.end(); }
  bool empty()  { return L.empty(); }
  val& back()  { return L.back(); }
  size_t size()  { return L.size(); }
};

template <typename config, typename urn>
class pcb442 {
 public:
  static const int N = 442;  // config::N;
  const double siz, ran, seq, rad;
  std::string last;

  pcb442(double _siz, double _ran, double _seq, double _rad) :
    siz(_siz), ran(_ran), seq(_seq), rad(_rad) {
    assert(siz >= 0.0 && siz <= 1.0);
    assert(ran+seq+rad == 1.0);
    assert(ran >= 0.0 && seq >= 0.0 && rad >= 0.0);

    init_dist();
  }


  int cost(config& C) {
    int cost = 0;
    int prev = C.empty() ? -1 : C.back();
    std::for_each(C.begin(), C.end(), [this, &cost, &prev](const int c) {
                                        cost += D[prev][c]; prev = c;
                                      });
    return cost;
  }


  void init(config &C, std::pair<urn, urn> &Us) {
    C.init();
    Us.first.clear();
    Us.second.clear();
    for (int i = 0; i < N; ++i)  Us.first.push_back(i);
  }

  void RR_all(config &C, std::pair<urn, urn> &Us) {
    init(C, Us);
    recreate(C, Us);
  }

  int draw_rad(config& C, int size, std::pair<urn, urn>& Us) {
    auto center = random() % C.size();
    last = "rad(" + i2s(center) + "," + i2s(size) + ")";
    Us.first.clear();
    std::for_each_n(rad_nxt[center].begin(), size, [&C, &Us](auto& c) {
      C.erase(c);
      Us.first.push_back(c);
    });
    return center;
  }

  int draw_seq(config& C, int size, std::pair<urn, urn>& Us) {
    auto start = random() % C.size();
    last = "seq(" + i2s(start) + "," + i2s(size) + ")";
    typename config::iterator it = C[start];
    int ret = *it;
    while (size-- > 0 && it != C.end()) {
      int c = *it;
      it = C.erase(it);
      Us.first.push_back(c);
    }
    it = C.begin();
    while (size-- > 0) {
      int c = *it;
      it = C.erase(it);
      Us.first.push_back(c);
    }
    return -1-ret;
  }

  int draw_ran(config& C, int size,
               std::pair<urn, urn>& Us) {
    assert(Us.first.size() == 0);
    assert(Us.second.size() == N);
    last = "ran(" + i2s(size) + ")";
    for (; size > 0; --size) {
      int r = edraw(Us.second);
      Us.first.push_back(r);
      C.erase(r);
    }
    std::for_each(Us.first.begin(), Us.first.end(), [&Us](int c)  {
      Us.second.push_back(c);
    });
    return std::numeric_limits<int>::max();
  }

  int draw(config& C, int size,
           std::pair<urn, urn>& Us) {
    double d = drand48();

    if      (d < ran)      return draw_ran(C, size, Us);
    else if (d < ran+seq)  return draw_seq(C, size, Us);
    else                   return draw_rad(C, size, Us);
  }

/*
  returns
  -  std::numeric_limits<int>::max() for ran
  -  center city for rad
  -  -(1+start) city for seq
*/
  int ruin(config& C, std::pair<urn, urn>& Us) {
    return draw(C, ceil(drand48() * (siz * N)), Us);
  }


  void recreate(config& C, std::pair<urn, urn>& Us) {
    while (!Us.first.empty()) {
      int c = edraw(Us.first);
      assert(C[c] == C.end());
_start
      int mincost = std::numeric_limits<int>::max();
      int prev = C.empty() ? -1 : C.back();
      typename config::iterator best = C.end();
      for (typename config::iterator it = C.begin(); it != C.end(); ++it) {
        int cur = *it;
        int ncost = D[prev][c] + D[c][cur] - D[prev][cur];
        if (ncost < mincost) {
          best = it;
          mincost = ncost;
        }
        prev = cur;
      }
_stop
      C.insert(best, c);
    }
  }


  int D[N][N];           // distance matrix

  struct {
    int* vi;
    bool  operator()(int a, int b)  {
      return vi[a] < vi[b];
    }
  } Dless;

  std::vector<int> rad_nxt[N];     // radial next

  void init_dist() {
    for (int from = 0; from < N; ++from) {
      rad_nxt[from].clear();
      for (int to = 0; to < N; ++to) {
        D[from][to] = dist(from, to);
        rad_nxt[from].push_back(to);
      }
    }

    for (int from = 0; from < N; ++from) {
      Dless.vi = D[from];
      std::sort(rad_nxt[from].begin(), rad_nxt[from].end(), Dless);
    }
  }


  inline int nint(double d) { return static_cast<int>(0.5 + d); }
  // http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf#page=6
  // $ grep EDGE_WEIGHT_TYPE pcb442.tsp
  // EDGE_WEIGHT_TYPE : EUC_2D
  // $
  int dist(int from, int to) {
    double xd = C[from][0] - C[to][0];
    double yd = C[from][1] - C[to][1];
    return nint(sqrt(xd*xd + yd*yd));
  }

  // http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/pcb442.tsp.gz
  const double C[N][2]={
    {2.00000e+02, 4.00000e+02},
    {2.00000e+02, 5.00000e+02},
    {2.00000e+02, 6.00000e+02},
    {2.00000e+02, 7.00000e+02},
    {2.00000e+02, 8.00000e+02},
    {2.00000e+02, 9.00000e+02},
    {2.00000e+02, 1.00000e+03},
    {2.00000e+02, 1.10000e+03},
    {2.00000e+02, 1.20000e+03},
    {2.00000e+02, 1.30000e+03},
    {2.00000e+02, 1.40000e+03},
    {2.00000e+02, 1.50000e+03},
    {2.00000e+02, 1.60000e+03},
    {2.00000e+02, 1.70000e+03},
    {2.00000e+02, 1.80000e+03},
    {2.00000e+02, 1.90000e+03},
    {2.00000e+02, 2.00000e+03},
    {2.00000e+02, 2.10000e+03},
    {2.00000e+02, 2.20000e+03},
    {2.00000e+02, 2.30000e+03},
    {2.00000e+02, 2.40000e+03},
    {2.00000e+02, 2.50000e+03},
    {2.00000e+02, 2.60000e+03},
    {2.00000e+02, 2.70000e+03},
    {2.00000e+02, 2.80000e+03},
    {2.00000e+02, 2.90000e+03},
    {2.00000e+02, 3.00000e+03},
    {2.00000e+02, 3.10000e+03},
    {2.00000e+02, 3.20000e+03},
    {2.00000e+02, 3.30000e+03},
    {2.00000e+02, 3.40000e+03},
    {2.00000e+02, 3.50000e+03},
    {2.00000e+02, 3.60000e+03},
    {3.00000e+02, 4.00000e+02},
    {3.00000e+02, 5.00000e+02},
    {3.00000e+02, 6.00000e+02},
    {3.00000e+02, 7.00000e+02},
    {3.00000e+02, 8.00000e+02},
    {3.00000e+02, 9.00000e+02},
    {3.00000e+02, 1.00000e+03},
    {3.00000e+02, 1.10000e+03},
    {3.00000e+02, 1.20000e+03},
    {3.00000e+02, 1.30000e+03},
    {3.00000e+02, 1.40000e+03},
    {3.00000e+02, 1.50000e+03},
    {3.00000e+02, 1.60000e+03},
    {3.00000e+02, 1.70000e+03},
    {3.00000e+02, 1.80000e+03},
    {3.00000e+02, 1.90000e+03},
    {3.00000e+02, 2.00000e+03},
    {3.00000e+02, 2.10000e+03},
    {3.00000e+02, 2.20000e+03},
    {3.00000e+02, 2.30000e+03},
    {3.00000e+02, 2.40000e+03},
    {3.00000e+02, 2.50000e+03},
    {3.00000e+02, 2.60000e+03},
    {3.00000e+02, 2.70000e+03},
    {3.00000e+02, 2.80000e+03},
    {3.00000e+02, 2.90000e+03},
    {3.00000e+02, 3.00000e+03},
    {3.00000e+02, 3.10000e+03},
    {3.00000e+02, 3.20000e+03},
    {3.00000e+02, 3.30000e+03},
    {3.00000e+02, 3.40000e+03},
    {3.00000e+02, 3.50000e+03},
    {4.00000e+02, 4.00000e+02},
    {4.00000e+02, 5.00000e+02},
    {4.00000e+02, 6.00000e+02},
    {4.00000e+02, 7.00000e+02},
    {4.00000e+02, 8.00000e+02},
    {4.00000e+02, 9.00000e+02},
    {4.00000e+02, 1.00000e+03},
    {4.00000e+02, 1.10000e+03},
    {4.00000e+02, 1.20000e+03},
    {4.00000e+02, 1.30000e+03},
    {4.00000e+02, 1.40000e+03},
    {4.00000e+02, 1.50000e+03},
    {4.00000e+02, 1.60000e+03},
    {4.00000e+02, 1.70000e+03},
    {4.00000e+02, 1.80000e+03},
    {4.00000e+02, 1.90000e+03},
    {4.00000e+02, 2.00000e+03},
    {4.00000e+02, 2.10000e+03},
    {4.00000e+02, 2.20000e+03},
    {4.00000e+02, 2.30000e+03},
    {4.00000e+02, 2.40000e+03},
    {4.00000e+02, 2.50000e+03},
    {4.00000e+02, 2.60000e+03},
    {4.00000e+02, 2.70000e+03},
    {4.00000e+02, 2.80000e+03},
    {4.00000e+02, 2.90000e+03},
    {4.00000e+02, 3.00000e+03},
    {4.00000e+02, 3.10000e+03},
    {4.00000e+02, 3.20000e+03},
    {4.00000e+02, 3.30000e+03},
    {4.00000e+02, 3.40000e+03},
    {4.00000e+02, 3.50000e+03},
    {4.00000e+02, 3.60000e+03},
    {5.00000e+02, 1.50000e+03},
    {5.00000e+02, 1.82900e+03},
    {5.00000e+02, 3.10000e+03},
    {6.00000e+02, 4.00000e+02},
    {7.00000e+02, 3.00000e+02},
    {7.00000e+02, 6.00000e+02},
    {7.00000e+02, 1.50000e+03},
    {7.00000e+02, 1.60000e+03},
    {7.00000e+02, 1.80000e+03},
    {7.00000e+02, 2.10000e+03},
    {7.00000e+02, 2.40000e+03},
    {7.00000e+02, 2.70000e+03},
    {7.00000e+02, 3.00000e+03},
    {7.00000e+02, 3.30000e+03},
    {7.00000e+02, 3.60000e+03},
    {8.00000e+02, 3.00000e+02},
    {8.00000e+02, 6.00000e+02},
    {8.00000e+02, 1.03000e+03},
    {8.00000e+02, 1.50000e+03},
    {8.00000e+02, 1.80000e+03},
    {8.00000e+02, 2.10000e+03},
    {8.00000e+02, 2.40000e+03},
    {8.00000e+02, 2.60000e+03},
    {8.00000e+02, 2.70000e+03},
    {8.00000e+02, 3.00000e+03},
    {8.00000e+02, 3.30000e+03},
    {8.00000e+02, 3.60000e+03},
    {9.00000e+02, 3.00000e+02},
    {9.00000e+02, 6.00000e+02},
    {9.00000e+02, 1.50000e+03},
    {9.00000e+02, 1.80000e+03},
    {9.00000e+02, 2.10000e+03},
    {9.00000e+02, 2.40000e+03},
    {9.00000e+02, 2.70000e+03},
    {9.00000e+02, 3.00000e+03},
    {9.00000e+02, 3.30000e+03},
    {9.00000e+02, 3.60000e+03},
    {1.00000e+03, 3.00000e+02},
    {1.00000e+03, 6.00000e+02},
    {1.00000e+03, 1.10000e+03},
    {1.00000e+03, 1.50000e+03},
    {1.00000e+03, 1.62900e+03},
    {1.00000e+03, 1.80000e+03},
    {1.00000e+03, 2.10000e+03},
    {1.00000e+03, 2.40000e+03},
    {1.00000e+03, 2.60000e+03},
    {1.00000e+03, 2.70000e+03},
    {1.00000e+03, 3.00000e+03},
    {1.00000e+03, 3.30000e+03},
    {1.00000e+03, 3.60000e+03},
    {1.10000e+03, 3.00000e+02},
    {1.10000e+03, 6.00000e+02},
    {1.10000e+03, 7.00000e+02},
    {1.10000e+03, 9.00000e+02},
    {1.10000e+03, 1.50000e+03},
    {1.10000e+03, 1.80000e+03},
    {1.10000e+03, 2.10000e+03},
    {1.10000e+03, 2.40000e+03},
    {1.10000e+03, 2.70000e+03},
    {1.10000e+03, 3.00000e+03},
    {1.10000e+03, 3.30000e+03},
    {1.10000e+03, 3.60000e+03},
    {1.20000e+03, 3.00000e+02},
    {1.20000e+03, 6.00000e+02},
    {1.20000e+03, 1.50000e+03},
    {1.20000e+03, 1.70000e+03},
    {1.20000e+03, 1.80000e+03},
    {1.20000e+03, 2.10000e+03},
    {1.20000e+03, 2.40000e+03},
    {1.20000e+03, 2.70000e+03},
    {1.20000e+03, 3.00000e+03},
    {1.20000e+03, 3.30000e+03},
    {1.20000e+03, 3.60000e+03},
    {1.30000e+03, 3.00000e+02},
    {1.30000e+03, 6.00000e+02},
    {1.30000e+03, 7.00000e+02},
    {1.30000e+03, 1.13000e+03},
    {1.30000e+03, 1.50000e+03},
    {1.30000e+03, 1.80000e+03},
    {1.30000e+03, 2.10000e+03},
    {1.30000e+03, 2.20000e+03},
    {1.30000e+03, 2.40000e+03},
    {1.30000e+03, 2.70000e+03},
    {1.30000e+03, 3.00000e+03},
    {1.30000e+03, 3.30000e+03},
    {1.30000e+03, 3.60000e+03},
    {1.40000e+03, 3.00000e+02},
    {1.40000e+03, 6.00000e+02},
    {1.40000e+03, 9.30000e+02},
    {1.40000e+03, 1.50000e+03},
    {1.40000e+03, 1.80000e+03},
    {1.40000e+03, 2.00000e+03},
    {1.40000e+03, 2.10000e+03},
    {1.40000e+03, 2.40000e+03},
    {1.40000e+03, 2.50000e+03},
    {1.40000e+03, 2.70000e+03},
    {1.40000e+03, 2.82000e+03},
    {1.40000e+03, 2.90000e+03},
    {1.40000e+03, 3.00000e+03},
    {1.40000e+03, 3.30000e+03},
    {1.40000e+03, 3.60000e+03},
    {1.50000e+03, 1.50000e+03},
    {1.50000e+03, 1.80000e+03},
    {1.50000e+03, 1.90000e+03},
    {1.50000e+03, 2.10000e+03},
    {1.50000e+03, 2.40000e+03},
    {1.50000e+03, 2.70000e+03},
    {1.50000e+03, 2.80000e+03},
    {1.50000e+03, 2.86000e+03},
    {1.50000e+03, 3.00000e+03},
    {1.50000e+03, 3.30000e+03},
    {1.50000e+03, 3.60000e+03},
    {1.60000e+03, 1.10000e+03},
    {1.60000e+03, 1.30000e+03},
    {1.60000e+03, 1.50000e+03},
    {1.60000e+03, 1.80000e+03},
    {1.60000e+03, 2.10000e+03},
    {1.60000e+03, 2.40000e+03},
    {1.60000e+03, 2.70000e+03},
    {1.60000e+03, 3.00000e+03},
    {1.60000e+03, 3.30000e+03},
    {1.60000e+03, 3.60000e+03},
    {1.70000e+03, 1.20000e+03},
    {1.70000e+03, 1.50000e+03},
    {1.70000e+03, 1.80000e+03},
    {1.70000e+03, 2.10000e+03},
    {1.70000e+03, 2.40000e+03},
    {1.70000e+03, 3.60000e+03},
    {1.80000e+03, 3.00000e+02},
    {1.80000e+03, 6.00000e+02},
    {1.80000e+03, 1.23000e+03},
    {1.80000e+03, 1.50000e+03},
    {1.80000e+03, 1.80000e+03},
    {1.80000e+03, 2.10000e+03},
    {1.80000e+03, 2.40000e+03},
    {1.90000e+03, 3.00000e+02},
    {1.90000e+03, 6.00000e+02},
    {1.90000e+03, 3.00000e+03},
    {1.90000e+03, 3.52000e+03},
    {2.00000e+03, 3.00000e+02},
    {2.00000e+03, 3.70000e+02},
    {2.00000e+03, 6.00000e+02},
    {2.00000e+03, 8.00000e+02},
    {2.00000e+03, 9.00000e+02},
    {2.00000e+03, 1.00000e+03},
    {2.00000e+03, 1.10000e+03},
    {2.00000e+03, 1.20000e+03},
    {2.00000e+03, 1.30000e+03},
    {2.00000e+03, 1.40000e+03},
    {2.00000e+03, 1.50000e+03},
    {2.00000e+03, 1.60000e+03},
    {2.00000e+03, 1.70000e+03},
    {2.00000e+03, 1.80000e+03},
    {2.00000e+03, 1.90000e+03},
    {2.00000e+03, 2.00000e+03},
    {2.00000e+03, 2.10000e+03},
    {2.00000e+03, 2.20000e+03},
    {2.00000e+03, 2.30000e+03},
    {2.00000e+03, 2.40000e+03},
    {2.00000e+03, 2.50000e+03},
    {2.00000e+03, 2.60000e+03},
    {2.00000e+03, 2.70000e+03},
    {2.00000e+03, 2.80000e+03},
    {2.00000e+03, 2.90000e+03},
    {2.00000e+03, 3.00000e+03},
    {2.00000e+03, 3.10000e+03},
    {2.00000e+03, 3.50000e+03},
    {2.10000e+03, 3.00000e+02},
    {2.10000e+03, 6.00000e+02},
    {2.10000e+03, 3.20000e+03},
    {2.20000e+03, 3.00000e+02},
    {2.20000e+03, 4.69000e+02},
    {2.20000e+03, 6.00000e+02},
    {2.20000e+03, 3.20000e+03},
    {2.30000e+03, 3.00000e+02},
    {2.30000e+03, 6.00000e+02},
    {2.30000e+03, 3.40000e+03},
    {2.40000e+03, 3.00000e+02},
    {2.40000e+03, 6.00000e+02},
    {2.40000e+03, 2.10000e+03},
    {2.50000e+03, 3.00000e+02},
    {2.50000e+03, 8.00000e+02},
    {2.60000e+03, 4.00000e+02},
    {2.60000e+03, 5.00000e+02},
    {2.60000e+03, 8.00000e+02},
    {2.60000e+03, 9.00000e+02},
    {2.60000e+03, 1.00000e+03},
    {2.60000e+03, 1.10000e+03},
    {2.60000e+03, 1.20000e+03},
    {2.60000e+03, 1.30000e+03},
    {2.60000e+03, 1.40000e+03},
    {2.60000e+03, 1.50000e+03},
    {2.60000e+03, 1.60000e+03},
    {2.60000e+03, 1.70000e+03},
    {2.60000e+03, 1.80000e+03},
    {2.60000e+03, 1.90000e+03},
    {2.60000e+03, 2.00000e+03},
    {2.60000e+03, 2.10000e+03},
    {2.60000e+03, 2.20000e+03},
    {2.60000e+03, 2.30000e+03},
    {2.60000e+03, 2.40000e+03},
    {2.60000e+03, 2.50000e+03},
    {2.60000e+03, 2.60000e+03},
    {2.60000e+03, 2.70000e+03},
    {2.60000e+03, 2.80000e+03},
    {2.60000e+03, 2.90000e+03},
    {2.60000e+03, 3.00000e+03},
    {2.60000e+03, 3.10000e+03},
    {2.60000e+03, 3.40000e+03},
    {2.70000e+03, 7.00000e+02},
    {2.70000e+03, 8.00000e+02},
    {2.70000e+03, 9.00000e+02},
    {2.70000e+03, 1.00000e+03},
    {2.70000e+03, 1.10000e+03},
    {2.70000e+03, 1.20000e+03},
    {2.70000e+03, 1.30000e+03},
    {2.70000e+03, 1.40000e+03},
    {2.70000e+03, 1.50000e+03},
    {2.70000e+03, 1.60000e+03},
    {2.70000e+03, 1.70000e+03},
    {2.70000e+03, 1.80000e+03},
    {2.70000e+03, 1.90000e+03},
    {2.70000e+03, 2.00000e+03},
    {2.70000e+03, 2.10000e+03},
    {2.70000e+03, 2.20000e+03},
    {2.70000e+03, 2.30000e+03},
    {2.70000e+03, 2.50000e+03},
    {2.70000e+03, 2.60000e+03},
    {2.70000e+03, 2.70000e+03},
    {2.70000e+03, 2.80000e+03},
    {2.70000e+03, 2.90000e+03},
    {2.70000e+03, 3.00000e+03},
    {2.70000e+03, 3.10000e+03},
    {2.70000e+03, 3.20000e+03},
    {2.70000e+03, 3.30000e+03},
    {2.70000e+03, 3.40000e+03},
    {2.70000e+03, 3.50000e+03},
    {2.70000e+03, 3.60000e+03},
    {2.70000e+03, 3.70000e+03},
    {2.70000e+03, 3.80000e+03},
    {2.80000e+03, 9.00000e+02},
    {2.80000e+03, 1.13000e+03},
    {2.90000e+03, 4.00000e+02},
    {2.90000e+03, 5.00000e+02},
    {2.90000e+03, 1.40000e+03},
    {2.90000e+03, 2.40000e+03},
    {2.90000e+03, 3.00000e+03},
    {3.00000e+03, 7.00000e+02},
    {3.00000e+03, 8.00000e+02},
    {3.00000e+03, 9.00000e+02},
    {3.00000e+03, 1.00000e+03},
    {3.00000e+03, 1.10000e+03},
    {3.00000e+03, 1.20000e+03},
    {3.00000e+03, 1.30000e+03},
    {3.00000e+03, 1.50000e+03},
    {3.00000e+03, 1.60000e+03},
    {3.00000e+03, 1.70000e+03},
    {3.00000e+03, 1.80000e+03},
    {3.00000e+03, 1.90000e+03},
    {3.00000e+03, 2.00000e+03},
    {3.00000e+03, 2.10000e+03},
    {3.00000e+03, 2.20000e+03},
    {3.00000e+03, 2.30000e+03},
    {3.00000e+03, 2.50000e+03},
    {3.00000e+03, 2.60000e+03},
    {3.00000e+03, 2.70000e+03},
    {3.00000e+03, 2.80000e+03},
    {3.00000e+03, 2.90000e+03},
    {3.00000e+03, 3.00000e+03},
    {3.00000e+03, 3.10000e+03},
    {3.00000e+03, 3.20000e+03},
    {3.00000e+03, 3.30000e+03},
    {3.00000e+03, 3.40000e+03},
    {3.00000e+03, 3.50000e+03},
    {3.00000e+03, 3.60000e+03},
    {3.00000e+03, 3.70000e+03},
    {3.00000e+03, 3.80000e+03},
    {1.50000e+02, 3.50000e+03},
    {1.50000e+02, 3.55000e+03},
    {4.69000e+02, 2.55000e+03},
    {4.69000e+02, 3.35000e+03},
    {4.69000e+02, 3.45000e+03},
    {5.40000e+02, 2.33000e+03},
    {5.40000e+02, 2.43000e+03},
    {6.20000e+02, 3.65000e+03},
    {6.20000e+02, 3.70900e+03},
    {7.50000e+02, 2.55000e+03},
    {8.50000e+02, 5.20000e+02},
    {8.50000e+02, 7.00000e+02},
    {8.50000e+02, 2.28000e+03},
    {9.39000e+02, 7.40000e+02},
    {9.50000e+02, 2.22000e+03},
    {9.10000e+02, 2.60000e+03},
    {1.05000e+03, 1.05000e+03},
    {1.15000e+03, 1.35000e+03},
    {1.17000e+03, 2.28000e+03},
    {1.22000e+03, 2.21000e+03},
    {1.35000e+03, 7.50000e+02},
    {1.35000e+03, 1.70000e+03},
    {1.35000e+03, 2.14000e+03},
    {1.45000e+03, 7.70000e+02},
    {1.55000e+03, 3.00000e+02},
    {1.55000e+03, 5.00000e+02},
    {1.55000e+03, 1.85000e+03},
    {1.65000e+03, 1.05000e+03},
    {1.69000e+03, 2.68000e+03},
    {1.71000e+03, 3.10000e+02},
    {1.71000e+03, 5.10000e+02},
    {1.75000e+03, 7.50000e+02},
    {1.79000e+03, 2.58000e+03},
    {1.72000e+03, 2.61000e+03},
    {1.79000e+03, 3.33000e+03},
    {1.72000e+03, 3.40900e+03},
    {1.82900e+03, 2.70000e+03},
    {1.82900e+03, 2.80000e+03},
    {1.82900e+03, 3.45000e+03},
    {2.06000e+03, 1.65000e+03},
    {2.05000e+03, 3.15000e+03},
    {2.17000e+03, 1.90000e+03},
    {2.11000e+03, 2.00000e+03},
    {2.12000e+03, 2.75000e+03},
    {2.15000e+03, 3.25000e+03},
    {2.29000e+03, 1.40000e+03},
    {2.22000e+03, 2.82000e+03},
    {2.28000e+03, 3.25000e+03},
    {2.39000e+03, 1.30000e+03},
    {2.32000e+03, 1.50000e+03},
    {2.45000e+03, 7.10000e+02},
    {2.62000e+03, 3.65000e+03},
    {2.75000e+03, 5.20000e+02},
    {2.76000e+03, 2.36000e+03},
    {2.85000e+03, 2.20000e+03},
    {2.85000e+03, 2.70000e+03},
    {2.85000e+03, 3.35000e+03},
    {2.93000e+03, 9.50000e+02},
    {2.95000e+03, 1.75000e+03},
    {2.95000e+03, 2.05000e+03},
    {5.20000e+02, 3.20000e+03},
    {2.30000e+03, 3.50000e+03},
    {2.32000e+03, 3.15000e+03},
    {5.30000e+02, 2.10000e+03},
    {2.55000e+03, 7.10000e+02},
    {7.50000e+02, 4.90000e+02},
    {0.00000e+00, 0.00000e+00}
  };

  // http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/pcb442.opt.tour.gz
  // (optimal tour, 1-based)
  const int Opt[N]={
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 53,
    52, 51, 83, 84, 85, 381, 382, 86, 54, 21, 22, 55, 87, 378, 88, 56, 23, 24,
    25, 26, 27, 28, 29, 30, 31, 32, 376, 377, 33, 65, 64, 63, 62, 61, 60, 59,
    58, 57, 89, 90, 91, 92, 93, 101, 111, 123, 133, 146, 158, 169, 182, 197,
    196, 195, 194, 181, 168, 157, 145, 144, 391, 132, 122, 110, 121, 385, 109,
    120, 388, 131, 143, 156, 167, 180, 193, 192, 204, 216, 225, 233, 408, 409,
    412, 413, 404, 217, 205, 206, 207, 208, 218, 219, 209, 198, 183, 170, 159,
    147, 134, 124, 112, 436, 94, 95, 379, 96, 380, 97, 98, 384, 383, 113, 125,
    135, 148, 160, 171, 184, 199, 210, 220, 226, 411, 410, 414, 237, 265, 437,
    275, 423, 438, 272, 420, 268, 416, 264, 236, 263, 262, 261, 422, 419, 260,
    259, 258, 257, 256, 255, 254, 253, 418, 417, 252, 251, 250, 415, 249, 248,
    247, 246, 245, 244, 243, 242, 241, 407, 228, 235, 240, 267, 271, 270, 274,
    277, 426, 280, 440, 308, 309, 283, 284, 310, 339, 311, 285, 286, 312, 340,
    313, 287, 288, 314, 315, 316, 290, 289, 424, 421, 425, 291, 317, 318, 292,
    293, 319, 320, 294, 295, 321, 322, 296, 278, 297, 323, 430, 429, 324, 298,
    299, 300, 325, 326, 301, 302, 327, 328, 303, 304, 329, 330, 305, 306, 331,
    332, 333, 432, 334, 307, 335, 336, 427, 337, 338, 375, 374, 373, 372, 371,
    370, 369, 368, 345, 367, 366, 365, 431, 364, 363, 362, 344, 361, 360, 359,
    435, 358, 357, 356, 434, 355, 354, 353, 343, 352, 351, 350, 349, 433, 348,
    347, 346, 342, 341, 428, 282, 281, 279, 276, 273, 269, 266, 239, 238, 234,
    227, 405, 406, 401, 400, 185, 172, 161, 149, 136, 126, 114, 103, 102, 441,
    104, 115, 386, 127, 387, 389, 116, 138, 392, 152, 151, 137, 150, 162, 173,
    186, 174, 396, 399, 187, 175, 211, 403, 221, 229, 212, 230, 222, 213, 200,
    188, 176, 163, 393, 153, 139, 140, 128, 117, 105, 106, 107, 118, 129, 141,
    154, 165, 164, 397, 177, 189, 201, 202, 402, 214, 223, 231, 232, 224, 215,
    203, 190, 191, 398, 178, 179, 395, 394, 166, 155, 142, 390, 130, 119, 108,
    439, 82, 50, 49, 81, 100, 80, 48, 47, 79, 78, 46, 45, 77, 99, 76, 44, 43,
    75, 74, 42, 41, 73, 72, 40, 39, 71, 70, 38, 37, 69, 68, 36, 35, 67, 66, 34,
    442
  };
};  // class pcb442


void errlog(int i, int v, const std::string& trailer = "") {
  if (i >= 0)  std::cerr << i << ": ";
  std::cerr << v << "           " << trailer << "\r";
  if (i < 0)  std::cerr << "\n";
}

#ifdef ezxdisp
const int mar = 8;
const int wid = 3000;
const int hei = 3800;
const int Div = 5;

void mp(int x, int y, int s, std::pair<int, int>& a) {
  a = std::pair<int, int>(mar+x/Div+s*(2*mar+wid/Div), mar+(hei-y)/Div);
}

void city(const std::pair<int, int>& c, ezx_t *e) {
  ezx_fillrect_2d(e, c.first-2, c.second-2, c.first+2, c.second+2, &ezx_black);
}

void city2(const std::pair<int, int>& c, ezx_t *e) {
  ezx_fillrect_2d(e, c.first-4, c.second-4, c.first+4, c.second+4, &ezx_orange);
}

void city2a(const std::pair<int, int>& c, ezx_t *e) {
  ezx_fillrect_2d(e, c.first-6, c.second-6, c.first+6, c.second+6, &ezx_orange);
}

template <typename config, typename urn>
void ezx_tours(pcb442<config, urn>& P, config& T, config& R, urn& U, config& N,
               int ret, int mut, ezx_t*& e) {
  bool initial = (ret == std::numeric_limits<int>::min());
  ezx_wipe(e);

  ezx_line_2d(e, wid/Div+2*mar, hei/Div+2*mar, wid/Div+2*mar, 0, &ezx_black, 1);
  ezx_line_2d(e, 2*(wid/Div+2*mar), hei/Div+2*mar, 2*(wid/Div+2*mar), 0,
              &ezx_black, 1);

  ezx_str_2d(e, 5, 10, const_cast<char *>(reinterpret_cast<const char*>
                         (initial ? (mut == 0 ? "RR_all" : "minimum found")
                                  : "previous")), &ezx_black);
  std::stringstream s2;
  s2 << P.cost(T);
  ezx_str_2d(e, 50, hei/Div+mar,
             const_cast<char *>(reinterpret_cast<const char*>
              (s2.str().c_str())), &ezx_black);
  if (ret != std::numeric_limits<int>::min()) {
    s2 = std::stringstream();
    s2 << mut << ": ";
    if (ret == std::numeric_limits<int>::max())
      s2 << "ran";
    else
      s2 << (ret >= 0 ? "rad" : "seq");
    s2 << "(" << U.size() << ") ";
    s2 << P.cost(R);
    ezx_str_2d(e, 50+wid/Div+2*mar, hei/Div+mar,
               const_cast<char*>(reinterpret_cast<const char *>
                 (s2.str().c_str())), &ezx_black);
    s2 = std::stringstream();
    s2 << P.cost(N) << " (" << P.cost(N) - P.cost(T) << ")";
    ezx_str_2d(e, 50+2*(wid/Div+2*mar), hei/Div+mar,
               const_cast<char*>(reinterpret_cast<const char *>
                 (s2.str().c_str())), &ezx_black);

    ezx_str_2d(e, 5+wid/Div+2*mar, 10,
               const_cast<char*>(reinterpret_cast<const char*>("ruined")),
               &ezx_black);
    ezx_str_2d(e, 5+2*(wid/Div+2*mar), 10,
               const_cast<char*>(reinterpret_cast<const char*>("recreated")),
               &ezx_black);
  } else if (mut != 0) {
    ezx_str_2d(e, 5+wid/Div+2*mar, 10,
               const_cast<char*>(reinterpret_cast<const char*>
                 ("global minimum")), &ezx_black);

    s2 = std::stringstream();
    s2 << P.cost(R);
    ezx_str_2d(e, 50+wid/Div+2*mar, hei/Div+mar,
               const_cast<char*>(reinterpret_cast<const char *>
                 (s2.str().c_str())), &ezx_black);
  }

  if (ret != std::numeric_limits<int>::max() && ret >= 0) {
    std::pair<int, int> c;
    mp(P.C[ret][0], P.C[ret][1], 0, c);
    int r = P.D[ret][P.rad_nxt[ret][U.size()-1]];
    ezx_circle_2d(e, c.first, c.second, r/Div, &ezx_orange, 2);
    ezx_circle_2d(e, c.first+2*(wid/Div+2*mar), c.second, r/Div,
                  &ezx_orange, 2);
  }

  int prev = T.back();
  std::pair<int, int> p;
  mp(P.C[prev][0], P.C[prev][1], 0, p);

  std::for_each(T.begin(), T.end(), [&p, &e, &P](int i) {
    std::pair<int, int> c;
    mp(P.C[i][0], P.C[i][1], 0, c);
    ezx_line_2d(e, p.first, p.second, c.first, c.second, &ezx_blue, 1);
    p = c;
  });

  int hig = (ret < 0) ? -(1 + ret)
                      : (ret != std::numeric_limits<int>::max()) ? ret : -1;
  std::for_each(U.begin(), U.end(), [hig, &e, &P](int i) {
    std::pair<int, int> c;
    mp(P.C[i][0], P.C[i][1], 1, c);
    if (i == hig) { city2a(c, e); } else { city2(c, e); }
  });

  prev = R.back();
  mp(P.C[prev][0], P.C[prev][1], 1,  p);

  std::for_each(R.begin(), R.end(), [&p, &e, &P](int i) {
    std::pair<int, int> c;
    mp(P.C[i][0], P.C[i][1], 1, c);
    ezx_line_2d(e, p.first, p.second, c.first, c.second, &ezx_blue, 1);
    p = c;
  });

  prev = N.back();
  mp(P.C[prev][0], P.C[prev][1], 2,  p);

  std::for_each(N.begin(), N.end(), [&p, &e, &P](int i) {
    std::pair<int, int> c;
    mp(P.C[i][0], P.C[i][1], 2, c);
    ezx_line_2d(e, p.first, p.second, c.first, c.second, &ezx_blue, 1);
    p = c;
  });

  std::for_each(T.begin(), T.end(), [ret, &e, &P](int i) {
    std::pair<int, int> c;
    mp(P.C[i][0], P.C[i][1], 0, c);
    city(c, e);
    if (ret != std::numeric_limits<int>::min()) {
      mp(P.C[i][0], P.C[i][1], 2, c);
      city(c, e);
    }
  });

  std::for_each(R.begin(), R.end(), [&e, &P](int i) {
    std::pair<int, int> c;
    mp(P.C[i][0], P.C[i][1], 1, c);
    city(c, e);
  });

  // ezx_window_name(e, "57123 -> 53207 -> 51219");
  ezx_redraw(e);
  usleep(10000);
}
#endif

template <typename config, typename urn>
void RR() {
  std::pair<urn, urn> Us;
  config T;
  pcb442<config, urn> P(0.3,  1.0/3, 1.0/3, 1.0/3);

#ifdef ezxdisp
  ezx_t *e = ezx_init(3*(wid/Div+2*mar), hei/Div+2*mar,
                      const_cast<char*>(reinterpret_cast<const char*>
                      ("TSP greedy Ruin and Recreate")));
#endif

  P.RR_all(T, Us);

  errlog(0, P.cost(T), "RR_all() [" + i2s(_sum) + "us]");
  _sum = 0;

#ifdef ezxdisp
  config RC;
  urn UC;

  std::cerr << "\n";

  ezx_tours(P, T, RC, Us.first, RC, std::numeric_limits<int>::min(), 0, e);

  (void) ezx_pushbutton(e, NULL, NULL);
#endif

  for (int i = 1; i <= 100000; ++i) {
    config R = T;
    std::pair<urn, urn> UsR;
    for (typename config::iterator it = R.begin(); it != R.end(); ++it) {
      R[*it] = it;
      UsR.second.push_back(*it);
    }

#ifdef ezxdisp
    int ret = P.ruin(R, UsR);
    RC = R;
    UC = UsR.first;
#else
    (void) P.ruin(R, UsR);
#endif

    auto oldsum = _sum;
    P.recreate(R, UsR);

    if (P.cost(R) < P.cost(T)) {
      P.last += " (" + i2s(_sum - oldsum) + "us)          ";
      errlog(i, P.cost(R), P.last);

#ifdef ezxdisp
      std::cerr << "\n";
      ezx_tours(P, T, RC, UC, R, ret, i, e);

      while (1 != ezx_pushbutton(e, NULL, NULL))  { usleep(10000); }
#endif

      T = R;
      UsR.second.clear();
      for (typename config::iterator it = T.begin(); it != T.end(); ++it) {
        T[*it] = it;
        UsR.second.push_back(*it);
      }
    }
  }
  errlog(-1, P.cost(T), "local minimum found (after 100,000 greedy mutations)");
  errlog(-1, (_sum+500)/1000, "ms (only recreate)");
  // print(T);
  /*
  std::cout << "[";
  bool first = true;
  std::for_each(T.begin(), T.end(), [&first, P](int i) {
    if (!first) std::cout << ","; else first = false;
    std::cout << "[" << P.C[i][0] << "," << P.C[i][1] << "]";
  });
  std::cout << "]\n";
  */

  config O;  // P.Opt is 1-based
  for (int i = 0; i < P.N; ++i)  { int c = P.Opt[i] - 1; O.push_back(c); }
  errlog(-1, P.cost(O), "global minimum");

  config S = T;
  S.sort();
  urn V(S.begin(), S.end());
  for (int i = 0; i < P.N; ++i)  assert(V[i] == i);

#ifdef ezxdisp
  config dummy;
  ezx_tours(P, T, O, Us.first, dummy, std::numeric_limits<int>::min(), -1, e);

  while (3 != ezx_pushbutton(e, NULL, NULL))  { usleep(10000); }
#endif
}


int main(int argc, char *argv[]) {
  srandom(argc > 1 ? atoi(argv[1]) : time(0));

  RR<random_access_list<int, 442>, std::vector<int>>();

  return 0;
}

Revision 7:

• now added enhanced console output discussed in this previous comment
• in addition append the microseconds used between _start and _stop for just the reported mutation

As discussed in previous comment, running with nohup has advantages, see below.
For 442 cities TSP problem the time between _start and _stop is in range 12..865 microseconds on AMD 7950X CPU. The 865us time happened for a recreate of 60 cities:

pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | head -3
12
15
19
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | tail -3
206
213
865
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out | grep 865us
112: 54281           ran(60) (865us)          
pi@raspberrypi5:~/tsp $ 

pi@raspberrypi5:~/tsp $ rm nohup.out
pi@raspberrypi5:~/tsp $ nohup time ./pcb442 1001
nohup: ignoring input and appending output to 'nohup.out'
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out
0: 58634           RR_all()
2: 58603           ran(6) (13us)          
3: 58292           ran(49) (90us)          
4: 58210           seq(279,13) (22us)          
8: 58133           ran(74) (134us)          
10: 57882           ran(34) (62us)          
14: 57857           seq(217,118) (181us)          
15: 57528           rad(129,11) (20us)          
16: 57028           ran(131) (226us)          
21: 56906           ran(100) (161us)          
22: 56788           ran(83) (147us)          
23: 56730           rad(148,82) (144us)          
25: 56420           ran(68) (121us)          
34: 56418           ran(36) (65us)          
41: 56411           ran(24) (43us)          
42: 56249           rad(351,114) (173us)          
45: 56233           ran(17) (33us)          
50: 56014           rad(174,39) (68us)          
54: 55589           rad(236,60) (101us)          
62: 55445           rad(306,49) (81us)          
71: 55444           seq(197,45) (75us)          
72: 55288           rad(188,94) (148us)          
74: 55135           rad(316,13) (22us)          
75: 55119           ran(24) (40us)          
76: 55094           ran(56) (98us)          
80: 55023           ran(32) (60us)          
81: 54891           seq(320,30) (52us)          
83: 54875           ran(103) (171us)          
90: 54703           ran(24) (47us)          
94: 54595           rad(141,44) (81us)          
104: 54530           seq(215,55) (91us)          
109: 54394           seq(19,28) (51us)          
112: 54281           ran(60) (106us)          
113: 54199           ran(27) (50us)          
116: 54191           seq(261,56) (95us)          
118: 54139           ran(52) (92us)          
122: 54137           ran(115) (188us)          
126: 54133           ran(115) (189us)          
133: 54056           ran(97) (167us)          
137: 53979           ran(114) (189us)          
140: 53968           ran(9) (18us)          
150: 53926           ran(49) (87us)          
151: 53885           ran(113) (182us)          
163: 53863           ran(9) (18us)          
165: 53740           ran(47) (81us)          
183: 53718           ran(128) (203us)          
188: 53624           ran(117) (192us)          
195: 53579           rad(122,32) (54us)          
204: 53540           ran(99) (165us)          
211: 53464           rad(343,29) (50us)          
234: 53368           ran(90) (155us)          
235: 53296           ran(58) (101us)          
236: 53214           ran(17) (32us)          
252: 53175           rad(377,48) (82us)          
268: 53106           ran(59) (106us)          
269: 53035           seq(286,19) (34us)          
280: 53018           ran(43) (77us)          
313: 53005           ran(64) (112us)          
319: 53002           rad(35,55) (93us)          
320: 52955           rad(77,62) (98us)          
327: 52906           ran(36) (66us)          
328: 52873           ran(66) (117us)          
329: 52761           ran(15) (29us)          
332: 52759           seq(21,17) (29us)          
351: 52628           ran(59) (106us)          
361: 52613           ran(105) (171us)          
372: 52466           rad(103,71) (117us)          
378: 52463           rad(222,27) (45us)          
389: 52352           rad(224,49) (79us)          
393: 52300           ran(87) (153us)          
409: 52289           ran(125) (204us)          
419: 52225           ran(100) (171us)          
433: 52158           ran(100) (168us)          
451: 52143           ran(98) (168us)          
525: 52074           seq(27,42) (71us)          
561: 52011           ran(59) (105us)          
568: 51969           ran(102) (168us)          
583: 51932           ran(83) (141us)          
587: 51877           ran(32) (84us)          
650: 51866           ran(51) (92us)          
651: 51845           ran(78) (135us)          
664: 51795           ran(7) (12us)          
728: 51772           ran(108) (174us)          
756: 51769           ran(16) (26us)          
983: 51736           rad(35,38) (60us)          
2422: 51714           ran(94) (156us)          
2473: 51693           ran(61) (108us)          
2549: 51667           ran(63) (111us)          
2733: 51645           ran(94) (158us)          
2796: 51618           ran(27) (51us)          
2972: 51615           ran(104) (174us)          
4422: 51587           seq(43,14) (26us)          
4434: 51562           rad(395,24) (42us)          
4435: 51547           ran(42) (78us)          
4450: 51511           ran(119) (193us)          
4470: 51499           ran(38) (65us)          
4482: 51461           seq(208,37) (67us)          
4514: 51440           ran(62) (105us)          
4520: 51430           ran(40) (72us)          
4967: 51418           ran(79) (132us)          
14228: 51375           rad(199,26) (44us)          
14280: 51236           ran(87) (145us)          
14508: 51233           ran(70) (121us)          
56088: 51217           seq(126,22) (38us)          
56141: 51204           ran(35) (62us)          
56416: 51099           rad(195,23) (37us)          
62316: 51085           rad(194,23) (39us)          
51085           local minimum found (after 100,000 greedy mutations)

10824           ms (only recreate)

50778           global minimum

14.44user 0.00system 0:14.45elapsed 99%CPU (0avgtext+0avgdata 4752maxresident)k
0inputs+64outputs (1major+205minor)pagefaults 0swaps
pi@raspberrypi5:~/tsp $ 

I created a copy for usa13509 problem and

• adjusted N to 13509
• used 13509 coordinates from that problem
• had to create the distance matrix in a loop executed 13509 times doing D[from] = new int[N];
• did only 500 mutations instead of 100,000 because so slow

This time for 13509 cities TSP problem the time between _start and _stop is in range 1818..436904 microseconds on AMD 7950X CPU. The 437ms time ( AMD 7950X CPU runs single thread with 5.5GHz boost clock) happened for a recreate of 3,992 of the 13,509 cities (29.6%, RR is configured for ruins of sizes up to 30%) — time to parallelize the recreate step to 60 CUs or even 3,840 cores of a Vega20 type GPU ...

hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | head -3
1818
9618
9764
hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out | grep ") ("| cut -f3 -d\(| cut -f1 -du | sort -n | tail -3
367500
413481
436904
hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out | grep 436904us
16: 22289370           ran(3992) (436904us)          
hermann@7950x:~/tsp$ 

Cost of 22,769,244 after initial RR_all(), global optimum is 19,982,859. Reduction of more than a million after only 283 mutations:

hermann@7950x:~/tsp$ rm nohup.out 
hermann@7950x:~/tsp$ nohup time ./usa13509 1001
nohup: ignoring input and appending output to 'nohup.out'
hermann@7950x:~/tsp$ sed "s/^M/\n/g" nohup.out 
0: 22769244           RR_all()
2: 22765777           ran(169) (18435us)          
3: 22710358           ran(1478) (154853us)          
6: 22702144           rad(2358,946) (101035us)          
8: 22569463           ran(2254) (242485us)          
9: 22456757           ran(3109) (330930us)          
10: 22427246           ran(1023) (119492us)          
13: 22321845           ran(3285) (367500us)          
16: 22289370           ran(3992) (436904us)          
18: 22278027           ran(409) (52408us)          
21: 22225775           ran(3051) (353126us)          
22: 22188101           ran(2531) (300199us)          
25: 22151904           ran(2065) (249684us)          
33: 22130237           ran(1355) (168983us)          
34: 22112424           ran(1096) (138036us)          
41: 22100784           ran(718) (91791us)          
45: 22092895           ran(515) (66138us)          
53: 22076233           ran(1897) (232294us)          
65: 22054523           ran(1945) (237061us)          
68: 22029934           ran(3643) (413481us)          
75: 22025914           ran(708) (90857us)          
76: 22000413           ran(1699) (208322us)          
79: 21985921           ran(1215) (152274us)          
80: 21974989           ran(968) (122176us)          
83: 21962460           ran(3137) (365057us)          
90: 21954339           ran(715) (91891us)          
91: 21947134           ran(470) (60755us)          
99: 21938819           ran(1112) (140036us)          
101: 21926642           ran(2555) (303714us)          
106: 21919494           ran(736) (93581us)          
107: 21918693           ran(95) (12411us)          
112: 21908416           ran(1823) (222600us)          
113: 21899485           ran(814) (103152us)          
114: 21896743           ran(203) (26330us)          
118: 21891733           ran(1589) (195413us)          
119: 21887518           ran(1158) (144560us)          
124: 21882051           ran(526) (67645us)          
129: 21879981           ran(310) (40219us)          
130: 21879708           seq(2691,14) (1818us)          
133: 21874860           ran(2946) (345715us)          
134: 21858133           ran(1035) (130577us)          
140: 21854653           ran(256) (33407us)          
141: 21849446           ran(772) (98776us)          
147: 21840523           ran(1241) (155529us)          
150: 21829999           ran(1494) (185652us)          
157: 21828723           ran(119) (15685us)          
158: 21828668           ran(75) (9764us)          
159: 21821311           ran(627) (80444us)          
163: 21814301           ran(267) (34749us)          
174: 21811846           ran(400) (51587us)          
200: 21811431           ran(532) (68092us)          
213: 21809716           ran(219) (28603us)          
215: 21808489           ran(465) (60223us)          
233: 21808218           ran(129) (16899us)          
235: 21804165           ran(1759) (216274us)          
236: 21803798           ran(504) (65137us)          
239: 21798560           ran(602) (77141us)          
243: 21794699           ran(1337) (167115us)          
257: 21794546           ran(78) (10459us)          
265: 21791608           ran(878) (111211us)          
268: 21785236           ran(1799) (219712us)          
273: 21783947           ran(185) (24456us)          
280: 21776516           ran(1285) (159687us)          
283: 21764905           ran(1340) (166724us)          
287: 21763982           ran(417) (53700us)          
288: 21762024           ran(937) (118219us)          
290: 21761845           ran(440) (56808us)          
295: 21760941           rad(2532,146) (17893us)          
316: 21760360           ran(210) (27203us)          
327: 21751934           ran(1086) (137088us)          
329: 21750825           ran(444) (57319us)          
358: 21750289           ran(87) (11473us)          
365: 21746224           ran(1183) (149084us)          
370: 21743695           rad(12903,178) (22473us)          
375: 21741929           ran(148) (19338us)          
400: 21736507           ran(1152) (144793us)          
422: 21731731           ran(965) (121790us)          
443: 21729399           ran(1539) (190556us)          
453: 21729023           ran(640) (82394us)          
458: 21727568           ran(291) (37828us)          
469: 21723650           ran(1903) (232104us)          
486: 21722996           ran(1421) (177341us)          
500: 21722657           ran(73) (9618us)       
...

Revision 8:
On the path to parallelization of Recreate step. New class template <typename val, int N> class random_access_list was needed so that a GPU CU or core can do computation wrt its id. The [] operator of config returns the iterator in internal list with *C[c] == c.

Use of std::find() as well as std::advance() completely eliminated.

Part of the improvements was an unavoidable change in the way the random cities get created for radial ruin. Therefore same seed produces different result. With new code random seed of 205 even results in cost less than 51,000. Below will be used as something to compare against and detect unwanted changes in the future:

pi@raspberrypi5:~/tsp $ make 
g++ -O3 -std=c++17  -Wall -Wextra -pedantic pcb442.cpp -o pcb442 -lstdc++ -lm
pi@raspberrypi5:~/tsp $ rm nohup.out
pi@raspberrypi5:~/tsp $ nohup time ./pcb442 205
nohup: ignoring input and appending output to 'nohup.out'
pi@raspberrypi5:~/tsp $ sed "s/^M/\n/g" nohup.out
0: 58473           RR_all() [474us]
3: 58347           ran(49) (97us)          
4: 58282           seq(363,13) (25us)          
8: 58094           ran(74) (127us)          
9: 57833           ran(102) (171us)          
13: 57568           ran(108) (184us)          
16: 57308           ran(131) (209us)          
21: 57113           ran(100) (167us)          
22: 56541           ran(83) (144us)          
28: 56521           seq(370,70) (131us)          
30: 56321           rad(272,23) (41us)          
33: 56210           ran(45) (94us)          
34: 56074           ran(36) (72us)          
53: 55990           ran(63) (110us)          
54: 55899           rad(238,60) (100us)          
62: 55893           rad(31,49) (82us)          
65: 55874           ran(64) (114us)          
67: 55861           seq(264,25) (44us)          
68: 55757           ran(120) (197us)          
75: 55718           ran(24) (44us)          
76: 55591           ran(56) (99us)          
79: 55568           ran(40) (74us)          
80: 55565           ran(32) (58us)          
83: 55529           ran(103) (171us)          
85: 55479           seq(164,46) (78us)          
99: 55408           ran(37) (68us)          
107: 55320           ran(4) (8us)          
111: 55261           seq(409,73) (682us)          
112: 55179           ran(60) (737us)          
113: 55167           ran(27) (259us)          
126: 55150           ran(115) (491us)          
134: 55072           ran(34) (61us)          
140: 55069           ran(9) (20us)          
144: 55036           seq(360,87) (152us)          
147: 55013           ran(41) (73us)          
165: 54914           ran(47) (89us)          
200: 54894           ran(18) (34us)          
203: 54753           rad(71,16) (28us)          
213: 54720           ran(8) (13us)          
231: 54675           ran(110) (182us)          
263: 54668           rad(204,17) (27us)          
265: 54583           ran(29) (50us)          
279: 54581           ran(101) (165us)          
281: 54511           seq(222,20) (35us)          
291: 54330           ran(117) (195us)          
299: 54306           ran(52) (93us)          
316: 54241           ran(7) (14us)          
333: 54184           ran(108) (176us)          
384: 54149           rad(111,33) (59us)          
400: 54141           ran(38) (70us)          
528: 54045           seq(172,42) (74us)          
587: 54023           ran(32) (59us)          
642: 54014           ran(131) (208us)          
683: 53902           ran(33) (62us)          
704: 53871           ran(74) (131us)          
727: 53868           ran(80) (138us)          
733: 53862           ran(51) (91us)          
769: 53838           rad(293,15) (23us)          
789: 53797           ran(99) (165us)          
790: 53758           seq(224,51) (83us)          
791: 53717           ran(34) (63us)          
838: 53688           ran(57) (99us)          
869: 53671           ran(94) (157us)          
883: 53646           ran(70) (124us)          
902: 53598           ran(101) (172us)          
969: 53573           ran(60) (103us)          
980: 53572           ran(71) (127us)          
984: 53559           rad(359,19) (33us)          
997: 53477           rad(80,29) (46us)          
1016: 53444           ran(9) (18us)          
1110: 53432           rad(233,12) (22us)          
1137: 53429           seq(399,4) (7us)          
1169: 52966           rad(367,70) (113us)          
1196: 52917           seq(257,11) (17us)          
1229: 52904           ran(55) (100us)          
1284: 52893           ran(120) (196us)          
1309: 52842           ran(98) (167us)          
1319: 52831           ran(33) (60us)          
1373: 52811           ran(51) (90us)          
1375: 52744           ran(63) (110us)          
1437: 52662           ran(57) (99us)          
1561: 52656           ran(54) (94us)          
1712: 52638           ran(38) (70us)          
2030: 52610           rad(368,42) (68us)          
2054: 52580           ran(59) (103us)          
2221: 52559           ran(27) (48us)          
2319: 52556           ran(49) (91us)          
3024: 52355           rad(27,120) (185us)          
3041: 52348           ran(26) (47us)          
3049: 52337           ran(54) (98us)          
3062: 52285           ran(96) (160us)          
3102: 52261           ran(66) (112us)          
3114: 52239           ran(77) (130us)          
3151: 52168           ran(29) (54us)          
3191: 52142           rad(19,38) (62us)          
3275: 52121           ran(74) (126us)          
3325: 52099           ran(78) (133us)          
6147: 52090           seq(391,8) (15us)          
7652: 52085           rad(383,29) (50us)          
7840: 52059           rad(416,9) (16us)          
7875: 52056           ran(82) (139us)          
10129: 52055           seq(110,19) (31us)          
10239: 51987           ran(77) (130us)          
10272: 51973           ran(95) (161us)          
10445: 51964           rad(313,41) (69us)          
10497: 51948           ran(21) (36us)          
10558: 51890           ran(55) (98us)          
11130: 51882           seq(341,57) (89us)          
11271: 51829           ran(70) (121us)          
11309: 51823           ran(25) (45us)          
11653: 51801           ran(117) (186us)          
11822: 51779           seq(276,10) (18us)          
11845: 51744           ran(85) (143us)          
11858: 51724           ran(49) (87us)          
11991: 51721           ran(75) (126us)          
12214: 51698           rad(20,30) (50us)          
13224: 51685           rad(172,41) (71us)          
13254: 51670           ran(56) (101us)          
13288: 51541           ran(69) (116us)          
13302: 51514           ran(24) (42us)          
13615: 51502           ran(106) (176us)          
13760: 51496           seq(125,12) (23us)          
15054: 51419           seq(101,34) (60us)          
15074: 51417           ran(75) (134us)          
15147: 51399           ran(88) (150us)          
15845: 51393           ran(43) (78us)          
16216: 51384           seq(170,23) (37us)          
16232: 51363           ran(79) (136us)          
18350: 51315           rad(295,76) (117us)          
18388: 51313           rad(299,30) (51us)          
18563: 51268           rad(361,28) (48us)          
27451: 51238           rad(360,15) (25us)          
32949: 51232           seq(297,18) (31us)          
36311: 51231           seq(360,28) (45us)          
74444: 51181           rad(242,47) (79us)          
74532: 51179           ran(40) (70us)          
74581: 51174           ran(60) (103us)          
74646: 51027           rad(286,30) (49us)          
74695: 50969           ran(7) (13us)          
80526: 50953           seq(420,27) (46us)          
80558: 50947           ran(10) (19us)          
96003: 50940           ran(105) (173us)          
96948: 50933           seq(290,28) (48us)          
50933           local minimum found (after 100,000 greedy mutations)

10832           ms (only recreate)

50778           global minimum

13.35user 0.00system 0:13.37elapsed 99%CPU (0avgtext+0avgdata 4672maxresident)k
0inputs+64outputs (1major+199minor)pagefaults 0swaps
pi@raspberrypi5:~/tsp $ 

TODO:
There is a lot of copying, current tour config T is copied into R, that gets ruined and recreated, and if improvement (greedy) T=R is copied again.
In little example code I have solution already, just need to integrate here.
Instead of erasing iterator from list, splice the single iterator at end of a helper list.
Before doing so, push_back the successor of it onto a vector.
These operations happen on T, no copy R.
In case cost did not improve after ruin and recreate step, the vector and auxiliary list allow for "T.restore()" operation, with runtime proportional to the items removed.

Much more to come, but not in this gist. Development of this gist is stopped, no further updates.

Code is split up, and a loader was added allowing for different problems.
In addition that repo has 111 TSP problems with 108 corresponding optimal tours.

New repo:
https://github.com/Hermann-SW/RR/tree/main?tab=readme-ov-file#ruin-and-recreate

So many new features, and Mona Lisa ...