How to Solve the Traveling Salesman Problem Using Python & NetworkX

Traveling Salesman Problem

The Traveling Salesman Problem (TSP), also known as the salesman or routing problem, asks for the shortest possible route that visits each city exactly once and returns to the origin, given known distances between every pair of cities.

Given a salesman starting at city 1 who must visit cities 2, 3, …, n to sell goods and finally return to city 1, how should the optimal route be chosen when all inter‑city distances are known?

In graph‑theoretic terms, TSP is equivalent to finding a minimum Hamiltonian cycle. It was first studied by Euler and later formalized by Sir William Rowan Hamilton as a prize problem. Despite its simple description, TSP remains an unsolved world‑class challenge.

TSP has clear practical relevance, such as mail delivery routes and vehicle routing for distribution. It is proven to be NP‑hard, meaning that unless P = NP no efficient exact algorithm exists.

Mathematical Model

Assuming the distances between all vertices are known, the classic TSP can be expressed as a linear programming model that minimizes the total travel distance subject to:

Each city has exactly one incoming edge.

Each city has exactly one outgoing edge.

Subtour elimination constraints to prevent disconnected cycles.

If the distance matrix is symmetric, the problem is called symmetric TSP; otherwise it is asymmetric. When the distances satisfy the triangle inequality, the instance is referred to as a metric TSP.

Python Solution

We randomly generate 20 points as city coordinates and use the NetworkX library to construct a weighted graph and compute an approximate solution.

Import the required libraries, primarily NetworkX.

<code>import numpy as np
import matplotlib.pyplot as plt
from string import ascii_uppercase
import networkx as nx
</code>

Compute pairwise Euclidean distances and build the graph.

<code>np.random.seed(20)
cities = ascii_uppercase[:20]
locs = {cities[i]:(np.random.uniform(0,30), np.random.uniform(0,10)) for i in range(20)}  # generate city coordinates
for c in cities:
    plt.scatter(locs[c][0], locs[c][1])
    plt.text(locs[c][0], locs[c][1]+0.2, c)  # label points

dist_array = np.zeros((20,20))
for i in range(20):
    for j in range(20):
        x1, y1 = locs[cities[i]]
        x2, y2 = locs[cities[j]]
        dist_array[i,j] = np.sqrt((x1-x2)**2 + (y1-y2)**2)  # Euclidean distance
G = nx.from_numpy_array(dist_array)
</code>

Call the TSP approximation API.

<code>tsp = nx.approximation.traveling_salesman_problem(G, weight='weight')
</code>

The returned list, e.g. tsp=[0, 2, 8, 5, 18, 16, 9, 19, 3, 14, 11, 4, 7, 17, 12, 6, 10, 1, 15, 13, 0] , represents the order of city indices in the tour.

Visualize the tour.

<code>for i in range(len(tsp)-1):
    c1 = cities[tsp[i]]
    c2 = cities[tsp[i+1]]
    x1, y1 = locs[c1]
    x2, y2 = locs[c2]
    plt.plot([x1, x2], [y1, y2], 'r--')  # draw TSP path
for c in cities:
    plt.scatter(locs[c][0], locs[c][1])
    plt.text(locs[c][0], locs[c][1]+0.2, c)
</code>