Cfrtjryk

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.