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

In this question I present a method to solve the Traveling Salesman Problem and/or the Single Route Optimization problem.

I am extracting 100 lat/long points from Google Maps and placing these into a text file. The program should be able to read in the text file, calculate the haversine distance between each point, and store in an adjacency matrix. The adjacency matrix will eventually be fed to a 2-opt algorithm.

Extracting an adjaceny matrix containing haversine distance from points on map has already been dealt with. This question tackles the 2-opt algorithm.

The 2-opt function is called from main as follows. route is a randomly generated list of 100 numbers, which is the path the 2-opt should follow.

def main():
best = two_opt(connect_mat, route)  #connectivity/adjacency matrix

And here is the 2-opt function and a cost function that it utilizes. Can they be optimized in any way?

def cost(cost_mat, route):
return cost_mat[np.roll(route, 1), route].sum()  # shifts route array by 1 in order to look at pairs of cities

def two_opt(cost_mat, route):
best = route
improved = True
while improved:
improved = False
for i in range(1, len(route) - 2):
for j in range(i + 1, len(route)):
if j - i == 1: continue  # changes nothing, skip then
new_route = route[:]  # Creates a copy of route
new_route[i:j] = route[j - 1:i - 1:-1]  # this is the 2-optSwap since j >= i we use -1
if cost(cost_mat, new_route) < cost(cost_mat, best):
best = new_route
improved = True
route = best
return best

Sample Input:

35.905333, 14.471970
35.896389, 14.477780
35.901281, 14.518173
35.860491, 14.572245
35.807607, 14.535320
35.832267, 14.455894
35.882414, 14.373217
35.983794, 14.336096
35.974463, 14.351006
35.930951, 14.401137
.
.
.

Sample Output I would like to be able to scale up the points being read to 5000. With the code above it would be painfully slow.

Timer Test:

Starting a timer at the beginning of the function and ending before the return statement gives an average of 1.5s per 100 points. If simple proportion can be used to test algorithm scaling performance, then:

• 100 points: 1.5s
• 1000 points: 15s
• 5000 points: 75s

Please correct me if my above assumption is wrong.

I was wondering whether it could be improved in any way. More information can be added if requested.

EDIT:

I noticed that I was using an extra variable best. This can be removed as such:

def two_opt(connect_mat, route):
improved = True
while improved:
improved = False
for i in range(1, len(route) - 2):
for j in range(i + 1, len(route)):
if j - i == 1:
continue  # changes nothing, skip then
new_route = route[:]    # Creates a copy of route
new_route[i:j] = route[j - 1:i - 1:-1]  # this is the 2-optSwap since j >= i we use -1
if cost(connect_mat, new_route) < cost(connect_mat, route):
route = new_route    # change current route to best
improved = True

return route

I doubt how much (if any) this increases efficiency, however it does sacrifice readability to some extent.