Docs
  • Solver
  • Models
    • Field Service Routing
    • Employee Shift Scheduling
  • Platform
Try models
  • Timefold Solver 0.8.42
  • Traveling salesman (TSP - traveling salesman problem)
  • Edit this Page
  • 0.8.x
    • latest
    • 0.8.x

Timefold Solver 0.8.42

    • Timefold introduction
    • Quickstart
      • Overview
      • Hello world Java quick start
      • Quarkus Java quick start
      • Spring Boot Java quick start
    • Use cases and examples
    • Timefold configuration
    • Score calculation
    • Constraint streams score calculation
    • Shadow variable
    • Optimization algorithms
    • Move and neighborhood selection
    • Exhaustive search
    • Construction heuristics
    • Local search
    • Evolutionary algorithms
    • Hyperheuristics
    • Partitioned search
    • Benchmarking and tweaking
    • Repeated planning
    • Integration
    • Design patterns
    • Development
    • Release Notes

Traveling salesman (TSP - traveling salesman problem)

Problem description

Given a list of cities, find the shortest tour for a salesman that visits each city exactly once.

The problem is defined by Wikipedia. It is one of the most intensively studied problems in computational mathematics. Yet, in the real world, it is often only part of a planning problem, along with other constraints, such as employee shift rostering constraints.

Problem size

dj38     has  38 cities with a search space of   10^43.
europe40 has  40 cities with a search space of   10^46.
st70     has  70 cities with a search space of   10^98.
pcb442   has 442 cities with a search space of  10^976.
lu980    has 980 cities with a search space of 10^2504.

Problem difficulty

Despite TSP’s simple definition, the problem is surprisingly hard to solve. Because it is an NP-hard problem (like most planning problems), the optimal solution for a specific problem dataset can change a lot when that problem dataset is slightly altered:

tspOptimalSolutionVolatility
  • © 2025 Timefold BV
  • Timefold.ai
  • Documentation
  • Changelog
  • Send feedback
  • Privacy
  • Legal
    • Light mode
    • Dark mode
    • System default