Vwwxrf

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.

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.