The Travelling Salesman Problem (TSP) asks for the minimum-cost tour that starts at one location, visits every other location exactly once, and returns to the starting point.

Despite its simple definition, TSP is one of the most important problems in combinatorial optimization because the number of possible tours grows extremely quickly.

What does TSP solve?

Given a set of cities and a cost between pairs of cities, find the cheapest tour that:

1. starts at a chosen city,
2. visits every city exactly once,
3. returns to the start,
4. minimizes total cost.

A tour such as:

A → B → D → C → A

is valid only if every required city is visited exactly once before returning.

Graph model

TSP is usually modeled as a weighted graph:

• cities or locations are vertices,
• possible moves are edges,
• distance, travel time, or monetary cost is the edge weight.

The classical form often assumes a complete graph, although real systems may contain unavailable routes.

TSP vs shortest path

Shortest-path algorithms answer questions such as:

What is the cheapest path from A to B?

TSP asks a different global optimization question:

What is the cheapest closed tour that visits every required vertex?

Therefore Dijkstra or A* does not directly solve TSP.

TSP vs Hamiltonian Cycle

A Hamiltonian Cycle visits every vertex exactly once and returns to the start.

The Hamiltonian Cycle decision problem asks whether such a cycle exists.

TSP adds weights and optimization:

Among all valid Hamiltonian cycles, which has the lowest total cost?

A small numerical example

Consider:

      A   B   C   D
A     0  10  15  20
B    10   0  35  25
C    15  35   0  30
D    20  25  30   0

Tour:

A → B → C → D → A

costs:

10 + 35 + 30 + 20 = 95

while:

A → B → D → C → A

costs:

10 + 25 + 30 + 15 = 80

So the second tour is better.

Brute-force solution

The simplest exact approach generates every permutation of the non-starting cities, calculates each complete tour, and keeps the minimum.

With the start fixed, the search space is approximately:

(n - 1)!

This becomes impractical quickly.

JavaScript brute-force implementation

function permutations(arr) {
  if (arr.length <= 1) return [arr];

  const result = [];

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];

    for (const perm of permutations(remaining)) {
      result.push([current, ...perm]);
    }
  }

  return result;
}

function solveTSPBruteForce(dist) {
  const n = dist.length;
  const cities = Array.from({ length: n - 1 }, (_, i) => i + 1);

  let bestCost = Infinity;
  let bestTour = null;

  for (const order of permutations(cities)) {
    const tour = [0, ...order, 0];
    let cost = 0;

    for (let i = 0; i < tour.length - 1; i++) {
      cost += dist[tour[i]][tour[i + 1]];
    }

    if (cost < bestCost) {
      bestCost = cost;
      bestTour = tour;
    }
  }

  return { cost: bestCost, tour: bestTour };
}

Held–Karp dynamic programming

Held–Karp reduces repeated work by storing the best cost for states of the form:

dp[visitedSet][lastCity]

The meaning is:

minimum cost to start at city 0, visit exactly the cities in visitedSet, and finish at lastCity.

The visited set is usually encoded as a bitmask.

Transition:

nextMask = mask | (1 << v)

dp[nextMask][v] =
min(
  dp[nextMask][v],
  dp[mask][u] + dist[u][v]
)

At the end, add the cost of returning to city 0.

JavaScript Held–Karp implementation

function tspHeldKarp(dist) {
  const n = dist.length;
  const size = 1 << n;

  const dp = Array.from(
    { length: size },
    () => Array(n).fill(Infinity)
  );

  dp[1][0] = 0;

  for (let mask = 1; mask < size; mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue;
      if (dp[mask][u] === Infinity) continue;

      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue;

        const nextMask = mask | (1 << v);

        dp[nextMask][v] = Math.min(
          dp[nextMask][v],
          dp[mask][u] + dist[u][v]
        );
      }
    }
  }

  const fullMask = size - 1;
  let answer = Infinity;

  for (let last = 1; last < n; last++) {
    answer = Math.min(
      answer,
      dp[fullMask][last] + dist[last][0]
    );
  }

  return answer;
}

Complexity

Brute force:

O(n!)

Held–Karp:

Time:  O(n² × 2^n)
Space: O(n × 2^n)

Held–Karp is dramatically better than factorial search but is still exponential.

Why TSP is difficult

The optimization version of TSP is NP-hard. No known general polynomial-time exact algorithm solves arbitrary TSP instances.

For large instances, practical systems often use:

• branch and bound,
• nearest-neighbor heuristics,
• 2-opt and 3-opt,
• simulated annealing,
• genetic algorithms,
• ant-colony methods,
• specialized routing solvers.

Nearest-neighbor heuristic

A simple heuristic repeatedly chooses the nearest unvisited city.

It is fast and easy to implement, but it does not guarantee an optimal tour.

2-opt local search

2-opt improves an existing tour by removing two edges and reconnecting the tour in a different way.

If the new arrangement is cheaper, it replaces the old one.

This simple idea can significantly improve poor initial tours.

Symmetric and asymmetric TSP

In symmetric TSP:

cost(A, B) = cost(B, A)

In asymmetric TSP:

cost(A, B) ≠ cost(B, A)

Asymmetry appears naturally with one-way streets, traffic, tolls, or direction-specific travel times.

Metric TSP

Metric TSP satisfies the triangle inequality:

d(A, C) ≤ d(A, B) + d(B, C)

This property matters because some approximation algorithms provide quality guarantees for metric instances.

Real-world applications

Delivery routing

A vehicle must visit a set of delivery points and return to a depot.

With one vehicle and simple constraints this can resemble TSP. Multiple vehicles, capacities, and time windows usually lead to the Vehicle Routing Problem.

Technician visits

A technician may need an efficient order for visiting customer locations.

Warehouse robots

A picking robot may need to visit many shelves while minimizing total movement.

Sales and CRM

A sales representative may need an efficient sequence for visiting customer locations in a region.

CNC and manufacturing

A machine tool may need to visit many drill or cutting points while minimizing non-productive movement.

PCB manufacturing

The order in which a tool visits board locations can affect production time.

TSP vs Vehicle Routing Problem

Classical TSP usually assumes one traveler and one tour.

Vehicle Routing Problem may add:

• multiple vehicles,
• capacities,
• time windows,
• pickups and deliveries,
• multiple depots,
• driver working-hour constraints.

So many practical routing problems are not pure TSP.

Important edge cases

• one city,
• two cities,
• unreachable edges,
• asymmetric costs,
• invalid or missing distances,
• open tours that do not return to the start.

The last case belongs to variants such as Open TSP.

When should you use TSP?

Use the TSP model when:

• one agent must visit all required locations,
• visit order matters,
• each location is normally visited once,
• the route usually returns to the start,
• minimizing total route cost is the primary objective.

When is TSP not a good fit?

Use shortest-path algorithms if you only need to travel from one point to another.

Use VRP when multiple vehicles or capacity constraints exist.

Use Hamiltonian Cycle if only the existence of a full cycle matters.

Use another routing or scheduling model when visits are optional, constrained by time windows, priorities, or other business rules.

Summary

TSP asks for the cheapest complete tour through all required locations.

Brute force is conceptually simple but factorial. Held–Karp uses dynamic programming and bitmasks to reduce the complexity to O(n²2^n), which is still exponential.

For large real-world routing problems, exact optimization is often replaced or combined with heuristics and specialized solvers.

The most important engineering step is not memorizing a TSP implementation. It is determining whether the real problem is actually TSP or a richer model such as VRP, Open TSP, or a constrained routing problem.