30-City Traveling Salesman Problem

Try to find the shortest route that visits all 30 cities exactly once

Instructions

You start at city #1 (green dot)
Click on cities in the order you want to visit them
Try to find the shortest possible route that visits all cities exactly once
After visiting all cities, the route will automatically connect back to city #1
The total distance of your route will be displayed below the map

Click on the next city to start building your route.

About the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is one of the most famous problems in computer science and optimization. It asks: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

Despite its simple description, the TSP is notoriously difficult to solve optimally. It belongs to a class of problems known as NP-hard, which means that as the number of cities increases, the computational effort required to find the optimal solution grows exponentially.

For small instances (like 10-15 cities), exact algorithms can find the optimal solution. But for larger instances, heuristic methods are typically used to find good, but not necessarily optimal, solutions in a reasonable amount of time.

This interactive demo allows you to manually solve a 30-city TSP instance, giving you an intuitive understanding of the challenge. Can you find a route that's close to optimal?

Mathematical Formulation

The TSP can be formulated as an integer programming problem. Below is an AMPL model that solves the 30-city TSP instance shown in this demo:

AMPL Model (tsp.mod)

# Traveling Salesman Problem (TSP) AMPL Model

set CITIES;                      # Set of cities
param dist{CITIES, CITIES};      # Distance between cities

# Binary decision variables: 1 if we travel from i to j, 0 otherwise
var x{CITIES, CITIES} binary;

# Subtour elimination variable
var u{CITIES} >= 0;

# Objective: Minimize the total distance traveled
minimize TotalDistance:
    sum {i in CITIES, j in CITIES} dist[i, j] * x[i, j];

# Constraints: Ensure each city is visited exactly once
subject to VisitOnce{i in CITIES}:
    sum {j in CITIES} x[i, j] == 1;

subject to LeaveOnce{j in CITIES}:
    sum {i in CITIES} x[i, j] == 1;

# Subtour elimination constraints (MTZ formulation)
subject to SubtourElim{i in CITIES diff {1}, j in CITIES diff {1}}:
    u[i] - u[j] + card(CITIES) * x[i, j] <= card(CITIES) - 1;

Data File (tsp.dat)

set CITIES := 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30;
param dist : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 :=
1 0.00 50.17 82.42 32.76 33.20 35.45 86.88 79.11 43.17 66.20 84.52 59.01 18.45 47.02 93.01 81.42 30.95 60.80 85.59 59.71 52.08 34.27 31.06 43.52 78.50 62.04 56.77 22.52 80.71 70.68
2 50.17 0.00 72.64 72.51 17.06 80.25 39.92 68.93 43.41 42.96 47.46 49.74 33.31 53.90 56.96 44.59 75.33 31.40 65.85 16.55 61.87 76.37 47.75 42.76 45.34 29.60 36.16 34.99 75.91 73.92
3 82.42 72.64 0.00 71.69 70.92 82.51 67.88 3.76 39.74 30.73 45.61 25.06 69.71 36.09 44.99 45.18 79.81 103.98 15.96 59.98 34.09 76.31 51.68 39.60 39.18 102.24 107.69 88.42 7.85 20.24
4 32.76 72.51 71.69 0.00 56.56 11.03 101.35 69.39 42.09 68.58 91.36 55.19 40.61 37.94 97.85 88.65 8.30 90.94 80.71 75.73 37.65 4.92 28.59 42.91 83.84 91.60 88.19 54.27 67.09 54.10
5 33.20 17.06 70.92 56.56 0.00 63.68 54.71 67.16 34.89 44.99 56.87 46.07 16.43 44.58 66.17 53.76 58.77 37.81 67.86 28.05 52.43 60.14 34.54 34.51 52.60 37.45 38.65 21.38 72.46 67.49
6 35.45 80.25 82.51 11.03 63.68 0.00 111.04 80.29 52.78 79.36 101.94 66.18 47.30 48.96 108.62 99.17 4.92 95.87 91.73 84.92 48.55 6.21 38.89 53.58 94.51 96.88 92.20 57.93 77.69 64.51
7 86.88 39.92 67.88 101.35 54.71 111.04 0.00 65.13 61.37 40.82 23.23 56.18 68.54 70.11 29.18 22.88 106.37 61.08 54.01 27.18 76.46 105.96 72.92 60.49 28.71 57.93 69.08 74.73 74.41 79.53
8 79.11 68.93 3.76 69.39 67.16 80.29 65.13 0.00 36.26 27.24 43.23 21.36 66.13 33.13 43.28 42.59 77.43 100.25 14.98 56.42 31.75 74.07 48.53 36.08 36.49 98.52 103.93 84.76 9.42 19.70
9 43.17 43.41 39.74 42.09 34.89 52.78 61.37 36.26 0.00 26.62 49.30 15.89 30.14 10.51 55.84 46.63 48.69 71.96 42.71 38.93 18.46 46.98 14.51 0.88 41.75 71.09 73.52 49.39 39.32 32.69
10 66.20 42.96 30.73 68.58 44.99 79.36 40.82 27.24 26.62 0.00 23.54 15.87 49.45 32.20 29.27 21.31 75.31 74.32 23.17 29.30 37.10 73.49 40.97 25.85 15.65 72.33 78.86 65.21 35.64 38.82
11 84.52 47.46 45.61 91.36 56.87 101.94 23.23 43.23 49.30 23.54 0.00 39.20 66.42 55.71 9.51 3.13 97.68 75.67 31.01 30.92 60.53 96.23 63.10 48.47 7.94 72.94 82.33 78.25 52.64 59.63
12 59.01 49.74 25.06 55.19 46.07 66.18 56.18 21.36 15.89 15.87 39.20 0.00 44.98 17.44 43.88 37.13 62.52 80.56 26.90 39.90 21.34 60.10 29.80 15.49 31.26 79.12 83.57 63.41 26.55 25.03
13 18.45 33.31 69.71 40.61 16.43 47.30 68.54 66.13 30.14 49.45 66.42 44.98 0.00 37.30 75.12 63.30 42.39 51.01 70.40 41.36 44.24 43.96 23.23 30.19 60.71 51.36 49.57 19.70 69.45 61.66
14 47.02 53.90 36.09 37.94 44.58 48.96 70.11 33.13 10.51 32.20 55.71 17.44 37.30 0.00 61.08 53.34 45.50 82.05 42.96 49.02 7.99 42.83 15.96 11.22 47.85 81.29 83.20 56.99 33.71 24.40
15 93.01 56.96 44.99 97.85 66.17 108.62 29.18 43.28 55.84 29.27 9.51 43.88 75.12 61.08 0.00 12.50 104.52 84.84 29.23 40.43 65.01 102.76 70.06 55.06 14.58 82.05 91.66 87.54 52.56 61.42
16 81.42 44.59 45.18 88.65 53.76 99.17 22.88 42.59 46.63 21.31 3.13 37.13 63.30 53.34 12.50 0.00 94.88 73.15 31.16 28.03 58.41 93.51 60.31 45.79 6.25 70.47 79.67 75.14 51.97 58.32
17 30.95 75.33 79.81 8.30 58.77 4.92 106.37 77.43 48.69 75.31 97.68 62.52 42.39 45.50 104.52 94.88 0.00 91.15 88.43 80.14 45.73 5.01 34.57 49.47 90.32 92.11 87.61 53.35 75.33 62.39
18 60.80 31.40 103.98 90.94 37.81 95.87 61.08 100.25 71.96 74.32 75.67 80.56 51.01 82.05 84.84 73.15 91.15 0.00 97.06 46.35 89.99 93.67 72.17 71.47 75.12 3.35 9.03 38.48 106.98 103.95
19 85.59 65.85 15.96 80.71 67.86 91.73 54.01 14.98 42.71 23.17 31.01 26.90 70.40 42.96 29.23 31.16 88.43 97.06 0.00 51.13 43.74 85.54 56.67 42.25 25.73 94.93 101.91 87.48 23.74 34.51
20 59.71 16.55 59.98 75.73 28.05 84.92 27.18 56.42 38.93 29.30 30.92 39.90 41.36 49.02 40.43 28.03 80.14 46.35 51.13 0.00 56.49 80.15 48.01 38.10 29.00 44.00 52.14 48.94 64.38 64.92
21 52.08 61.87 34.09 37.65 52.43 48.55 76.46 31.75 18.46 37.10 60.53 21.34 44.24 7.99 65.01 58.41 45.73 89.99 43.74 56.49 0.00 42.33 21.61 19.13 52.60 89.26 90.99 63.92 30.11 18.64
22 34.27 76.37 76.31 4.92 60.14 6.21 105.96 74.07 46.98 73.49 96.23 60.10 43.96 42.83 102.76 93.51 5.01 93.67 85.54 80.15 42.33 0.00 33.36 47.79 88.73 94.48 90.52 56.37 71.54 58.41
23 31.06 47.75 51.68 28.59 34.54 38.89 72.92 48.53 14.51 40.97 63.10 29.80 23.23 15.96 70.06 60.31 34.57 72.17 56.67 48.01 21.61 33.36 0.00 15.20 55.77 71.97 71.93 42.69 49.66 39.91
24 43.52 42.76 39.60 42.91 34.51 53.58 60.49 36.08 0.88 25.85 48.47 15.49 30.19 11.22 55.06 45.79 49.47 71.47 42.25 38.10 19.13 47.79 15.20 0.00 40.94 70.56 73.11 49.33 39.35 33.01
25 78.50 45.34 39.18 83.84 52.60 94.51 28.71 36.49 41.75 15.65 7.94 31.26 60.71 47.85 14.58 6.25 90.32 75.12 25.73 29.00 52.60 88.73 55.77 40.94 0.00 72.61 81.14 73.88 45.84 52.08
26 62.04 29.60 102.24 91.60 37.45 96.88 57.93 98.52 71.09 72.33 72.94 79.12 51.36 81.29 82.05 70.47 92.11 3.35 94.93 44.00 89.26 94.48 71.97 70.56 72.61 0.00 12.34 39.96 105.44 102.80
27 56.77 36.16 107.69 88.19 38.65 92.20 69.08 103.93 73.52 78.86 82.33 83.57 49.57 83.20 91.66 79.67 87.61 9.03 101.91 52.14 90.99 90.52 71.93 73.11 81.14 12.34 0.00 34.27 110.12 106.02
28 22.52 34.99 88.42 54.27 21.38 57.93 74.73 84.76 49.39 65.21 78.25 63.41 19.70 56.99 87.54 75.14 53.35 38.48 87.48 48.94 63.92 56.37 42.69 49.33 73.88 39.96 34.27 0.00 88.68 81.32
29 80.71 75.91 7.85 67.09 72.46 77.69 74.41 9.42 39.32 35.64 52.64 26.55 69.45 33.71 52.56 51.97 75.33 106.98 23.74 64.38 30.11 71.54 49.66 39.35 45.84 105.44 110.12 88.68 0.00 13.64
30 70.68 73.92 20.24 54.10 67.49 64.51 79.53 19.70 32.69 38.82 59.63 25.03 61.66 24.40 61.42 58.32 62.39 103.95 34.51 64.92 18.64 58.41 39.91 33.01 52.08 102.80 106.02 81.32 13.64 0.00
;

The optimal solution has a total distance of 451.77, which is the shortest possible route for this 30-city TSP instance. The model uses the Miller-Tucker-Zemlin (MTZ) formulation for subtour elimination, which prevents the formation of disconnected cycles in the solution.