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
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 . . .
I would like to be able to scale up the points being read to 5000. With the code above it would be painfully slow.
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.
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.