InteractiveMap of Operations Research
Back to Networks, Games & Systems
MethodIntermediate04.10
Networks, Games & Systems

Traveling Salesperson Problem

Find a minimum-cost tour visiting each location once.

Overview

The Traveling Salesperson Problem asks for the least-cost tour that visits each location once and returns to the start. It is one of the central textbook examples in combinatorial optimization.

TSP is more than a routing puzzle: it introduces subtour elimination, branch-and-cut, approximation, local search, and benchmark-driven algorithm engineering used across routing and sequencing problems.

Core ideas

Hamiltonian tours

Hamiltonian tours visit every node exactly once and return to the origin.

Subtour elimination

Subtour elimination constraints prevent disconnected smaller cycles from masquerading as a valid tour.

Branch-and-cut

Branch-and-cut combines enumeration with cutting planes to solve difficult TSP instances exactly.

Local search

Local search improves tours by moves such as 2-opt, 3-opt, swaps, and larger neighborhoods.

Approximation

Approximation algorithms give performance guarantees for structured TSP variants such as metric TSP.

How to use it

  1. 1Define nodes, travel costs, symmetry, and whether the route must return to the start.
  2. 2Choose a formulation or heuristic based on instance size and whether exact optimality matters.
  3. 3Eliminate subtours explicitly in exact models or use a solver designed for routing structure.
  4. 4Benchmark against simple nearest-neighbor or insertion heuristics before trusting complex methods.
  5. 5Extend to VRP when capacity, multiple vehicles, time windows, pickups, or depots enter.

Applications

RoutingSequencingCircuit layoutWarehousingTour planning
  • Routing: design short tours for service, inspection, or delivery stops.
  • Sequencing: order jobs, tools, or tasks when changeover cost depends on sequence.
  • Circuit layout: reduce travel or wiring distance in manufacturing and design settings.
  • Warehousing: optimize picker paths and visit sequences.
  • Tour planning: create efficient itineraries across locations.

Common pitfalls

  • Treating a VRP with capacity or time windows as a plain TSP.
  • Forgetting subtour elimination in integer programming formulations.
  • Comparing heuristics without consistent benchmark instances or cost definitions.
  • Optimizing distance while ignoring service time, driver rules, or operational feasibility.

Resources