Does TSP require geographical locations?

No. Vertices can represent tasks or machine positions when the transition costs fit the formulation.

Does computational difficulty make every instance unsolvable?

No. Particular instances can be solved exactly, and useful heuristics can handle others without proving optimality.

Can road travel be asymmetric?

Yes. One-way streets or directional travel times can make opposite journeys have different costs.

AI Glossary / Graphs and symbolic AI / Intermediate

Traveling salesperson problem

Definition

The traveling salesperson problem, or TSP, asks for a minimum-cost tour that visits each required location once and returns to the starting location. Costs may represent distance, time or another specified quantity. It is a classic problem in combinatorial optimization.

What it means

The difficulty is choosing the order of visits. Knowing the cheapest connection between each pair of locations does not immediately tell us which complete tour is cheapest. A locally attractive next stop can leave expensive connections near the end.

The standard tour includes the return journey. A route with different starting and ending locations is a related path variant. Multiple vehicles, delivery capacities and appointment windows introduce additional modeling requirements and are commonly handled as vehicle-routing variants.

In a symmetric TSP, traveling from A to B has the same cost as traveling from B to A. In an asymmetric version, the two directions can differ. The choice should follow the real cost information rather than a convenient visual map.

How it works

Represent locations as vertices and pairwise travel costs as weighted connections. A candidate solution orders the locations into a cycle. Add the costs of all its connections, including the final return, to evaluate it.

For a tiny instance, enumerate distinct tours and compare their totals. Larger instances require more sophisticated methods. Exact optimization combines search with mathematical bounds that can rule out whole groups of alternatives. Heuristics construct or improve promising tours within an available computing budget, but finding a good tour does not itself prove optimality.

When a valid lower bound and a feasible tour have the same cost, they establish an optimum. If they differ, the gap provides information about remaining uncertainty. These claims concern the stated mathematical model: an optimal tour under outdated travel costs can still perform poorly in practice.

Three practical examples

A circuit-board machine chooses an order for visiting drilling positions to reduce movement between them.
A field-service planner compares a single technician's round trip before adding appointment and working-time constraints.
An AI research team uses fixed TSP instances to compare learned routing proposals with established optimization methods under equal time limits.

Think of it this way

Think of planning a loop through every exhibit on a small museum checklist. The closest next exhibit may be tempting, but the whole sequence and the journey back to the entrance determine total walking.

The analogy assumes that every listed exhibit must be visited and that movement costs are known. Crowds, opening times and optional exhibits would change the model; the basic TSP does not automatically represent them.

Worked example

Comparing all distinct four-location tours

Take four locations A, B, C and D. Symmetric connection costs are AB=2, AC=9, AD=8, BC=6, BD=3 and CD=4. These are invented costs, not geometric distances, and they need not obey the triangle inequality.

Fix A as the starting point. Reversing a tour preserves its cost, leaving three distinct possibilities:

A - B - C - D - A costs 2+6+4+8=20.
A - B - D - C - A costs 2+3+4+9=18.
A - C - B - D - A costs 9+6+3+8=26.

The minimum is 18. Here the optimum is established because all distinct tours have been checked, not because a solver printed a plausible route. The final C-to-A cost of nine is part of the winning tour and cannot be omitted. With more locations, exhaustive enumeration grows rapidly and this classroom approach becomes impractical.

Illustrative case study

Fictional Cedar Visits plans an engineer's daily round trip using distances between customer sites. Its prototype produces a shorter tour than the order previously entered by a dispatcher.

During review, the team discovers that one customer accepts visits only in the morning. The distance-only tour reaches that customer last. The team adds the relevant scheduling constraints and compares feasible plans using the same cost definition.

It also changes its report from “optimal route” to “best route found within the search limit” unless the optimization method supplies a valid optimality certificate. The fictional improvement is in how the result is interpreted; no measured savings or solver performance are asserted.

Common misconceptions and mistakes

Nearest-next-stop selection guarantees the cheapest tour. Local choices can produce a poor overall cycle.
A returned tour is automatically optimal. Feasibility, improvement and proven optimality are different claims.
Every routing task is a plain TSP. Capacities, multiple vehicles, optional visits and time-dependent costs can require different formulations.

Business use

TSP thinking helps teams recognize when visit ordering matters and distinguish route quality from proof of optimality. Before choosing a method, define required stops, the return condition, cost units and operational constraints.

When comparing systems, report feasibility, tour cost, runtime and any justified bound or gap. Keep inputs and budgets comparable. A learned model may provide useful candidate tours, but its output still needs constraint checks and an appropriate comparison method. The business objective should determine the cost model rather than being inferred from whichever metric is easiest to calculate.

Check your understanding

A tour costs 120 and the solver has established a valid lower bound of 110. Has it proved that 120 is optimal?

Answer: No. The optimum is between 110 and 120 inclusive. Further evidence is needed to eliminate cheaper feasible tours.

Related terms

Heuristic search
Combinatorial optimisation
Hamiltonian cycle
vehicle routing problem
branch and bound
approximation algorithm
optimality gap

Learn next

Read branch and bound and vehicle routing. Recalculate the four-location example after changing one connection cost, then add an appointment constraint and identify which tours remain feasible.

Sources

Google OR-Tools, Traveling Salesperson Problem, including its explicit warning that the routing solver does not always return an optimum: https://developers.google.com/optimization/routing/tsp

University of Waterloo TSP project, problem description and explanation of finding and verifying a shortest tour: https://www.math.uwaterloo.ca/tsp/problem/index.html and https://www.math.uwaterloo.ca/tsp/methods/index.html

Relevant Google documentation and returned Waterloo source descriptions were reviewed. The four-location enumeration is original and checked directly; no software benchmark or real business outcome is claimed.

Previous: Transposition table Next: Traversed edges per second