13

How do I solve a Travelling Salesman problem in python? I did not find any library, there should be a way using scipy functions for optimization or other libraries.

My hacky-extremelly-lazy-pythonic bruteforcing solution is:

tsp_solution = min( (sum( Dist[i] for i in izip(per, per[1:])), n, per) for n, per in enumerate(i for i in permutations(xrange(Dist.shape[0]), Dist.shape[0])) )[2]

where Dist (numpy.array) is the distance matrix. If Dist is too big this will take forever.

Suggestions?

6
  • When you say solve what do you mean? Finding the single shortest route for very large numbers of cities is not something that humans actually know how to do short of exaustively checking the combinations, something that is very hard. Will a near-optimal solution do? Can we put a constraint on the number of cities to <=60?
    – BKay
    Aug 30, 2014 at 19:25
  • @BKay sure we do, back in 2006 an instance with 85900 cities was solved. I guarantee you that didn't happen with brute force. In general we're in trouble because it's NP-complete, but that doesn't mean we can't be clever about it.
    – harold
    Aug 31, 2014 at 11:47
  • I know that cannot be solved for many cities. I just want a state of the art heuristic solution. (Or a smarter deterministic approach for lower number of cities)
    – Gioelelm
    Aug 31, 2014 at 12:13
  • That's right. I spoke too fast. There are pretty good approximate solutions that are fast, and some complicated but much faster than brute force methods. I really just wanted to know what you wanted.
    – BKay
    Aug 31, 2014 at 13:05
  • The Lin–Kernighan heuristic works pretty well. If you want to go for actual optimality, you can look at the linear programming based solvers.
    – harold
    Aug 31, 2014 at 13:59

3 Answers 3

28

The scipy.optimize functions are not constructed to allow straightforward adaptation to the traveling salesman problem (TSP). For a simple solution, I recommend the 2-opt algorithm, which is a well-accepted algorithm for solving the TSP and relatively straightforward to implement. Here is my implementation of the algorithm:

import numpy as np

# Calculate the euclidian distance in n-space of the route r traversing cities c, ending at the path start.
path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))])
# Reverse the order of all elements from element i to element k in array 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.

Here is an example of the function being used:

# Create a matrix of cities, with each row being a location in 2-space (function works in n-dimensions).
cities = np.random.RandomState(42).rand(70,2)
# Find a good route with 2-opt ("route" gives the order in which to travel to each city by row number.)
route = two_opt(cities,0.001)

And here is the approximated solution path shown on a plot:

import matplotlib.pyplot as plt
# Reorder the cities matrix by route order in a new matrix for plotting.
new_cities_order = np.concatenate((np.array([cities[route[i]] for i in range(len(route))]),np.array([cities[0]])))
# Plot the cities.
plt.scatter(cities[:,0],cities[:,1])
# Plot the path.
plt.plot(new_cities_order[:,0],new_cities_order[:,1])
plt.show()
# Print the route as row numbers and the total distance travelled by the path.
print("Route: " + str(route) + "\n\nDistance: " + str(path_distance(route,cities)))

2-opt Traveling Salesman Problem Approximate Solution

If the speed of algorithm is important to you, I recommend pre-calculating the distances and storing them in a matrix. This dramatically decreases the convergence time.

Edit: Custom Start and End Points

For a non-circular path (one which ends at a location different from where it starts), edit the path distance formula to

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

and then reorder the cities for plotting using

new_cities_order = np.array([cities[route[i]] for i in range(len(route))])

With the code as it is, the starting city is fixed as the first city in cities, and the ending city is variable.

To make the ending city the last city in cities, restrict the range of swappable cities by changing the range of swap_first and swap_last in two_opt() with the code

for swap_first in range(1,len(route)-3):
    for swap_last in range(swap_first+1,len(route)-1):

To make both the starting and ending cities variable, instead expand the range of swap_first and swap_last with

for swap_first in range(0,len(route)-2):
    for swap_last in range(swap_first+1,len(route)):
6
  • 1
    Would this implementation be valid for a non circular path, by just changing path_distance? (e.g. So that cities traversal does not have to end at path start)
    – Gioelelm
    May 20, 2017 at 7:15
  • @Gioelelm Yes, it certainly is. I've added an explanation of how to change path_distance for non-circular paths. With a non-circular path, you may also want to customize the start and end points, so I've added a note on how to customize those as well. Note that I've made a slight modification to two_opt_swap to accommodate a variable starting city. May 20, 2017 at 16:13
  • Is this valid for an asymmetrical TSP problem? I tried an asymmetrical path_distance function, but I don't really know if 2-opt works for asymmetrical cases :?
    – jjmontes
    Nov 5, 2017 at 16:47
  • 1
    @jjmontes It seems like this would be valid for an asymmetric problem, though I don’t know how it would compare with other heuristics. I’d be interested to know how it performs. Also, I recommend creating a pre-calculated distances table. It will dramatically speed up performance in both the symmetric and asymmetric cases. Nov 5, 2017 at 18:37
  • Nice answer. I find that this solution is more scalable.
    – zabop
    Feb 20, 2022 at 15:55
0

I recently found out this option to use linear optimization for the TSP problem

https://gist.github.com/mirrornerror/a684b4d439edbd7117db66a56f2483e0

Nonetheless I agree with some of the other comments, just a remainder that there are ways to use linear optimization for this problem.

Some academic publications include the following http://www.opl.ufc.br/post/tsp/ https://phabi.ch/2021/09/19/tsp-subtour-elimination-by-miller-tucker-zemlin-constraint/

0

there's 'graph' lib in Python exactly for Network Problems (vertex cover optimization problem in theoretical computer science & operations research) - NetworkX. In its docs (Reference/Algorithms/Approximations and Heuristics) you can find an example (perhaps, it could be more convinient than scipy for such problem type - incl. shortest path problem, min cost flow problem , etc). TSP:

The NP-hard graphical traveling salesman problem (GTSP) is to find a closed walk of total minimum weight that visits each vertex in an undirected edge-weighted and not necessarily complete graph.

"""
==========================
Traveling Salesman Problem
==========================

This is an example of a drawing solution of the traveling salesman problem

The function used to produce the solution is `christofides <networkx.algorithms.approximation.traveling_salesman.christofides>`,
where given a set of nodes, it calculates the route of the nodes
that the traveler has to follow in order to minimize the total cost.
"""

import matplotlib.pyplot as plt
import networkx as nx
import networkx.algorithms.approximation as nx_app
import math

G = nx.random_geometric_graph(20, radius=0.4, seed=3)
pos = nx.get_node_attributes(G, "pos")

# Depot should be at (0,0)
pos[0] = (0.5, 0.5)

H = G.copy()


# Calculating the distances between the nodes as edge's weight.
for i in range(len(pos)):
    for j in range(i + 1, len(pos)):
        dist = math.hypot(pos[i][0] - pos[j][0], pos[i][1] - pos[j][1])
        dist = dist
        G.add_edge(i, j, weight=dist)

cycle = nx_app.christofides(G, weight="weight")
edge_list = list(nx.utils.pairwise(cycle))

# Draw closest edges on each node only
nx.draw_networkx_edges(H, pos, edge_color="blue", width=0.5)

# Draw the route
nx.draw_networkx(
    G,
    pos,
    with_labels=True,
    edgelist=edge_list,
    node_color = 'r',
    edge_color="red",
    node_size=200,
    width=3,
)

print("The route of the traveller is:", cycle)
plt.show()

Note: there's different Algorithms for your problem in networkX's docs

Formulation: Branch-And-Cut Algorithms For The Covering Salesman Problem

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.