Skip to content
ENExplore Calculators

Travelling Salesman Estimate Calculator

Work out travelling salesman estimate instantly with clear inputs, formula shown and shareable results.

About Travelling Salesman Estimate Calculator

For n points spread randomly over a square of side L, the optimal tour length approaches 0.7124·√(nL²). The minimum spanning tree gives a hard lower bound, and doubling it gives a constructive upper bound via the double-tree heuristic.

Formulas

BHH asymptotic

L_opt ≈ 0.7124 · √(n · A) for n points in an area A

Tour count

(n − 1)! / 2 distinct tours on n cities

Worked example

With the default values below, Travelling Salesman Estimate Calculator returns Beardwood-Halton-Hammersley estimate of 225.2807. Change any input above and every figure here is recalculated in your browser.

Inputs used

Number of citiesaccepts 2–40
10
Side of the square regionminimum 0
100
Known minimum spanning tree weightminimum 0
250

Results

Beardwood-Halton-Hammersley estimate
225.2807
Lower bound (spanning tree weight)
250.0000
Upper bound (twice the tree weight)
500.0000
Distinct tours to check by brute force
181,440

Step by step

  1. 1Values used
  2. 2BHH asymptotic
  3. 3Tour count
  4. 4Beardwood-Halton-Hammersley estimate= 225.2807
  5. 5Lower bound (spanning tree weight)= 250.0000
  6. 6Upper bound (twice the tree weight)= 500.0000
  7. 7Distinct tours to check by brute force= 181,440

Assumptions and limits

  • The result is derived only from the 3 inputs listed above. Anything not among them is not part of the calculation.
  • In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
  • Figures are rounded for display to 4 decimal places, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.

How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.

Frequently Asked Questions

For 10 cities in a 100 × 100 square?

The estimate is 0.7124 × √100000 ≈ 225.3 units, and there are 181440 distinct tours.

Why is twice the spanning tree an upper bound?

Walking each tree edge twice visits every city and returns home, and shortcutting repeated visits can only shorten it.

Related Calculators

Travelling Salesman Estimate Calculator | Calcrivo