2-opt algorithm for the Traveling Salesman and/or SRO
You repeatedly evaluate

cost(cost_mat, best)


There is an opportunity to memoize this, or at least store it in a temp var.

You should decide if you want "optimal" TSP, or "good enough" TSP
that is k-competitive with an optimal solution.

You suggest you're taking 15ms per city.
You didn't post profile / timing data, but
I have to believe that much of the time is taken up by roll + sum,
rather than by, say, creating route copies.
Could we pre-compute distances between points, and
then consider just next hops within some threshold distance?
Or order by distance, and consider only a fixed number of next hops,
adjusted upward each time a better route is found?

Could the cost() function be broken into "near" and "far" components,
with the advantage that "far" would be substantially constant?
Usually we do not find a better cost.
If we do find one, we could then fall back to "carefully"
computing the detailed "far" cost.