Skip to content
Knitting

TSP via Gravity Search (GSA) + 2-opt

The Traveling Salesman Problem: given N cities, find the shortest tour that visits each one exactly once and returns to the start. This is NP-hard, so we use heuristics — specifically, a gravity-inspired population search (GSA) followed by 2-opt local refinement, run as many parallel restarts through Knitting. More restarts = better chance of finding a good solution.

This is the most computationally intensive example in the set, and it shows what Knitting looks like on a real optimization workload.

How it works

Section titled “How it works”
  1. The host generates (or seeds) a set of cities and a distance matrix.
  2. The host launches many independent solver runs (“restarts”) through the worker pool.
  3. Each worker runs a gravity-inspired search to produce a candidate tour, then applies 2-opt to sharpen it.
  4. Each worker returns { bestLen, bestTour }.
  5. The host picks the global best, validates the tour, and recomputes the length for correctness.

The key insight: a single heuristic run can get stuck in a local minimum. Running many independent trials in parallel increases the chance that at least one finds a better region of the search space. This is embarrassingly parallel — restarts are independent, results are small, and the host just picks the best.

Install

Section titled “Install”
deno.sh
deno add --npm jsr:@vixeny/knitting

Run

Section titled “Run”
bun.sh
bun src/run_tsp.ts --threads 7 --restarts 64 --cities 64 --pop 10 --iters 10 --worldSeed 123456

Expected output:

cities: 64  restarts: 64  threads: 7  pop: 10  iters: 10
dispatching 64 restarts...


best tour length: 847.32
tour valid: OK (64 cities, no duplicates, all present)
recomputed length: 847.32 OK
random baseline: 2,341.07 (solver is 2.76x better than random)
elapsed: 2.14s

Code

Section titled “Code”
run_tsp.ts
import { createPool, isMain } from "@vixeny/knitting";
import { solveTspGsa } from "./tsp_gsa.ts";


function intArg(name: string, fallback: number) {
  const i = process.argv.indexOf(`--${name}`);
  if (i !== -1 && i + 1 < process.argv.length) {
    const v = Number(process.argv[i + 1]);
    if (Number.isFinite(v) && v > 0) return Math.floor(v);
  }
  return fallback;
}


const THREADS = intArg("threads", 7);
const RESTARTS = intArg("restarts", 64);
const N = intArg("cities", 64);
const POP = intArg("pop", 10);
const ITERS = intArg("iters", 10);


const worldSeed = intArg("worldSeed", 123456);
const seedBase = (Date.now() | 0) ^ 0x9e3779b9;


const { call, shutdown } = createPool({
  threads: THREADS,
  balancer: "firstIdle",
})({ solveTspGsa });


function validateTour(tour: number[], n: number) {
  if (tour.length !== n) throw new Error(`tour length ${tour.length} != ${n}`);
  const seen = new Uint8Array(n);
  for (const v of tour) {
    if ((v | 0) !== v) throw new Error(`non-int city id: ${v}`);
    if (v < 0 || v >= n) throw new Error(`bad city id: ${v}`);
    if (seen[v]) throw new Error(`duplicate city: ${v}`);
    seen[v] = 1;
  }
}


/* ---------- Host recompute must match worker exactly ---------- */


function xorshift32(s: number): number {
  s |= 0;
  s ^= s << 13;
  s ^= s >>> 17;
  s ^= s << 5;
  return s | 0;
}


const INV_U32 = 2.3283064365386963e-10; // 1 / 2^32


function makeCities(worldSeed: number, n: number): Float64Array {
  // coords: [x0,y0,x1,y1,...] in [0,1)
  const coords = new Float64Array(n * 2);
  let s = worldSeed | 0;
  for (let i = 0; i < n; i++) {
    s = xorshift32(s);
    coords[i * 2 + 0] = (s >>> 0) * INV_U32;
    s = xorshift32(s);
    coords[i * 2 + 1] = (s >>> 0) * INV_U32;
  }
  return coords;
}


function makeDistMatrix(coords: Float64Array, n: number): Float32Array {
  const d = new Float32Array(n * n);
  for (let i = 0; i < n; i++) {
    const xi = coords[i * 2 + 0];
    const yi = coords[i * 2 + 1];
    for (let j = i + 1; j < n; j++) {
      const dx = xi - coords[j * 2 + 0];
      const dy = yi - coords[j * 2 + 1];
      const dist = Math.hypot(dx, dy);
      d[i * n + j] = dist;
      d[j * n + i] = dist;
    }
  }
  return d;
}


function recomputeLen(tour: number[], dist: Float32Array, n: number): number {
  let s = 0;
  let prev = tour[0];
  for (let i = 1; i < n; i++) {
    const cur = tour[i];
    s += dist[prev * n + cur];
    prev = cur;
  }
  s += dist[prev * n + tour[0]];
  return s;
}


/* ---------- Random pick + random baseline tour ---------- */


function pickRandomIndex(len: number, seed: number): number {
  // deterministic “random” based on seed
  const s = xorshift32(seed | 0);
  return (s >>> 0) % len;
}


function makeRandomTour(n: number, seed: number): number[] {
  // Fisher–Yates shuffle
  const tour = new Array<number>(n);
  for (let i = 0; i < n; i++) tour[i] = i;


  let s = seed | 0;
  for (let i = n - 1; i > 0; i--) {
    s = xorshift32(s);
    const j = (s >>> 0) % (i + 1);
    const tmp = tour[i];
    tour[i] = tour[j];
    tour[j] = tmp;
  }
  return tour;
}


/* ------------------------------------------------------------ */


async function main() {
  const jobs: Promise<{ bestLen: number; bestTour: number[] }>[] = [];


  for (let r = 0; r < RESTARTS; r++) {
    const runSeed = (seedBase + r * 0x6d2b79f5) | 0;
    jobs.push(call.solveTspGsa([worldSeed, runSeed, N, POP, ITERS]));
  }


  const results = await Promise.all(jobs);
  if (results.length === 0) throw new Error("no results (unexpected)");


  // Find best + worst correctly
  let best = results[0];
  let worst = results[0];
  for (const res of results) {
    if (res.bestLen < best.bestLen) best = res;
    if (res.bestLen > worst.bestLen) worst = res;
  }


  // Build world once on host for verification
  const coords = makeCities(worldSeed, N);
  const dist = makeDistMatrix(coords, N);


  function checkResult(
    label: string,
    res: { bestLen: number; bestTour: number[] },
  ) {
    validateTour(res.bestTour, N);
    const recomputed = recomputeLen(res.bestTour, dist, N);
    const delta = recomputed - res.bestLen;


    if (!Number.isFinite(res.bestLen) || res.bestLen < 0) {
      throw new Error(`${label}: bestLen invalid: ${res.bestLen}`);
    }
    if (Math.abs(delta) > 1e-6) {
      throw new Error(
        `${label}: length mismatch (delta=${delta}). Host generator != worker generator?`,
      );
    }


    return { recomputed, delta };
  }


  // Randomly choose ONE run result and verify it too (not just the best)
  const randIdx = pickRandomIndex(results.length, seedBase ^ 0xA5A5A5A5);
  const randomRes = results[randIdx];


  const bestCheck = checkResult("best", best);
  const worstCheck = checkResult("worst", worst);
  const randomCheck = checkResult(`randomRun[#${randIdx}]`, randomRes);


  // Random baseline tour (not from solver)
  const randomTour = makeRandomTour(N, seedBase ^ 0xC0FFEE);
  validateTour(randomTour, N);
  const randomLen = recomputeLen(randomTour, dist, N);


  console.log("TSP via gravity (GSA) + 2-opt");
  console.log("threads      :", THREADS);
  console.log("restarts     :", RESTARTS);
  console.log("cities       :", N);
  console.log("pop          :", POP);
  console.log("iters        :", ITERS);
  console.log("worldSeed    :", worldSeed);
  console.log("---");
  console.log("bestLen      :", best.bestLen);
  console.log("worstLen     :", worst.bestLen);
  console.log(`randomRunLen :`, randomRes.bestLen, `(picked index ${randIdx})`);
  console.log("randomTourLen:", randomLen);
  console.log("---");
  console.log("best delta   :", bestCheck.delta);
  console.log("worst delta  :", worstCheck.delta);
  console.log("random delta :", randomCheck.delta);


  console.log(
    "tour head    :",
    best.bestTour.slice(0, Math.min(16, best.bestTour.length)).join(", "),
    "...",
  );
}


if (isMain) {
  main().finally(shutdown);
}

How the algorithm works

Section titled “How the algorithm works”

Representation: TSP needs a permutation of cities. Each agent stores a real-valued vector — sorting the keys produces the permutation. This lets “continuous” gravity-like motion work on a discrete problem.

Global search (GSA): Each agent has a mass proportional to its tour quality. Better tours = higher mass. Agents attract each other like gravity, gradually pulling the population toward better solutions.

Local refinement (2-opt): After global search, pick two edges, reverse a segment if it shortens the tour, repeat until no improvement. Fast and usually provides large gains — often the difference between “random” and “competitive.”

Correctness checks

Section titled “Correctness checks”

This example doesn’t just trust the output. It validates:

  1. Tour validity — length is N, all integers, no duplicates, all cities present.
  2. Length recomputation — recomputes on the host using the same distance matrix, catching bugs like delta-update drift or corrupted permutations.
  3. Random baseline — compares against a random tour to confirm the solver is actually finding structure, not returning noise.

CLI knobs

Section titled “CLI knobs”
  • --cities — increases difficulty sharply (N! possible tours)
  • --restarts — more restarts = better chance of finding a good tour (cheap parallel wins)
  • --iters — more iterations per run = deeper exploration per restart
  • --pop — population size per run = more exploration (but more compute)
  • --worldSeed — fix the city layout for reproducible comparisons

Start small: cities=32, restarts=threads*4, iters=200. Increase quality via restarts first — that’s the cheapest way to improve results.

Real-world analogs

Section titled “Real-world analogs”

TSP shows up in delivery routing, manufacturing toolpath optimization, PCB drilling, robotics path planning, and scheduling problems. The parallel-restart pattern works for any metaheuristic where independent runs are cheap and you just need the best result.

Things to try

Section titled “Things to try”
  1. Compare --restarts vs --iters: which improves quality faster per second of compute?
  2. Increase --cities to 128 and watch how the search space explodes.
  3. Lower --pop to 2-3 and see how much worse it gets (and how much faster).
  4. Change the distance metric to Manhattan distance and compare behavior.