How to reduce the time complexity of the Travelling salesman problem?

Question

path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))])
two_opt_swap = lambda r,i,k: np.concatenate((r[0:i],r[k:-len(r)+i-1:-1],r[k+1:len(r)]))

def two_opt(cities,improvement_threshold): # 2-opt Algorithm adapted from https://en.wikipedia.org/wiki/2-opt
    route = np.arange(cities.shape[0]) # Make an array of row numbers corresponding to cities.
    improvement_factor = 1 # Initialize the improvement factor.
    best_distance = path_distance(route,cities) # Calculate the distance of the initial path.

    while improvement_factor > improvement_threshold: # If the route is still improving, keep going!
        distance_to_beat = best_distance # Record the distance at the beginning of the loop.

        for swap_first in range(1,len(route)-2): # From each city except the first and last,
            for swap_last in range(swap_first+1,len(route)): # to each of the cities following,
                new_route = two_opt_swap(route,swap_first,swap_last) # try reversing the order of these cities
                new_distance = path_distance(new_route,cities) # and check the total distance with this modification.

                if new_distance < best_distance: # If the path distance is an improvement,
                    route = new_route # make this the accepted best route
                    best_distance = new_distance # and update the distance corresponding to this route.
        improvement_factor = 1 - best_distance/distance_to_beat # Calculate how much the route has improved.
    return route # When the route is no longer improving substantially, stop searching and return the route.

from math import radians,cos,sin

lat = cities2['lattitude'].map(radians)
lon = cities2['longitude'].map(radians)
x = lon.map(cos)*lat.map(cos)*6371
y = lon.map(cos)*lat.map(sin)*6371

cities2["lat_radians"] = lat
cities2["lon_radians"] = lon
cities2["x"] = x
cities2["y"] = y
cities2.head()

df = cities.copy()

scaler = MinMaxScaler(feature_range=(0, 100), copy=True)
scaled_df = scaler.fit_transform(df)
scaled_df = pd.DataFrame(scaled_df, columns=['x1', 'x2'])

cities = np.asarray(cities)

scaled = np.asarray(scaled_df)

route = two_opt(scaled,0.001)
route

I have one TSP problem, here I'm facing time complexity. How can I remove the for loop and how to reduce the time complexity?

Could anyone help to optimize it or ensure it can work on an increasingly large number of cities?

score 0 · Accepted Answer · answered Jun 27 '22 at 16:27

Using the CPython interpreter for that is not efficient. Consider using a native language, a JIT like Numba, Cython or a natively compiled module that does that for you (if any). Using Numpy functions (like np.linalg.norm) on scalar items or very-small arrays is very inefficient (see this related post).

The TSP problem is NP-Hard so the best known algorithm known yet is exponential. Several decades of the best worldwide researchers failed so far to find a better algorithm that is not exponential (nor to prove P=NP which is considered to be rather wrong by researchers but they also failed to prove P!=NP yet). If the number of cities is big, I advise you to make use of an approximation (which can be computed in polynomial time).

How to reduce the time complexity of the Travelling salesman problem?

1 Answers1