Depth First Search (Brute Force)

This is an exhaustive, brute-force algorithm. It is guaranteed to find the best possible path, however depending on the number of points in the traveling salesman problem it is likely impractical. For example,

With 10 points there are 181,400 paths to evaluate.
With 11 points, there are 1,814,000.
With 12 points there are 19,960,000.
With 20 points there are 60,820,000,000,000,000, give or take.
With 25 points there are 310,200,000,000,000,000,000,000, give or take.

This is factorial growth, and it quickly makes the TSP impractical to brute force. That is why heuristics exist to give a good approximation of the best path, but it is very difficult to determine without a doubt what the best path is for a reasonably sized traveling salesman problem.

This is a recursive, depth-first-search algorithm, as follows:

From the starting point
For all other points not visited
If there are no points left return the current cost/path
Else, go to every remaining point and

Mark that point as visited
"recurse" through those paths (go back to 1. )

Implementation

const dfs = async (points, path = [], visited = null, overallBest = null) => {
  if (visited === null) {
    // initial call
    path = [points.shift()];
    points = new Set(points);
    visited = new Set();
  }

  // figure out what points are left from this point
  const available = setDifference(points, visited);

  if (available.size === 0) {
    // this must be a complete path
    const backToStart = [...path, path[0]];

    // calculate the cost of this path
    const cost = pathCost(backToStart);

    // return both the cost and the path where we're at
    return [cost, backToStart];
  }

  let [bestCost, bestPath] = [null, null];

  // for every point yet to be visited along this path
  for (const p of available) {
    // go to that point
    visited.add(p);
    path.push(p);

    // RECURSE - go through all the possible points from that point
    const [curCost, curPath] = await dfs(points, path, visited, overallBest);

    // if that path is better, keep it
    if (bestCost === null || curCost < bestCost) {
      [bestCost, bestPath] = [curCost, curPath];

      if (overallBest === null || bestCost < overallBest) {
        // found a new best complete path
        overallBest = bestCost;
      }
    }

    // go back up and make that point available again
    visited.delete(p);
    path.pop();
  }
  return [bestCost, bestPath];
};

Nearest Neighbor

This is a heuristic, greedy algorithm also known as nearest neighbor. It continually chooses the best looking option from the current state.

From the starting point
sort the remaining available points based on cost (distance)
Choose the closest point and go there
Chosen point is no longer an "available point"
Continue this way until there are no available points, and then return to the start.

Implementation

const nearestNeighbor = async points => {
  const path = [points.shift()];

  while (points.length > 0) {
    // sort remaining points in place by their
    // distance from the last point in the current path
    points.sort(
      (a, b) =>
        distance(path[path.length - 1], b) - distance(path[path.length - 1], a)
    );

    // go to the closest remaining point
    path.push(points.pop());
  }

  // return to start after visiting all other points
  path.push(path[0]);
  const cost = pathCost(path);
};

Two-Opt inversion

This algorithm is also known as 2-opt, 2-opt mutation, and cross-aversion. The general goal is to find places where the path crosses over itself, and then "undo" that crossing. It repeats until there are no crossings. A characteristic of this algorithm is that afterwards the path is guaranteed to have no crossings.

While a better path has not been found.
For each pair of points:
Reverse the path between the selected points.
If the new path is cheaper (shorter), keep it and continue searching. Remember that we found a better path.
If not, revert the path and continue searching.

Implementation

const twoOptInversion = async path => {
  path.push(path[0]);
  let best = pathCost(path);
  let swapped = true;

  while (swapped) {
    swapped = false;
    for (let pt1 = 1; pt1 < path.length - 1; pt1++) {
      for (let pt2 = pt1 + 1; pt2 < path.length - 1; pt2++) {
        // section of the path to reverse
        const section = path.slice(pt1, pt2 + 1);

        // reverse section in place
        section.reverse();

        // replace section of path with reversed section in place
        path.splice(pt1, pt2 + 1 - pt1, ...section);

        // calculate new cost
        const newPath = path;
        const cost = pathCost(newPath);

        if (cost < best) {
          // found a better path after the swap, keep it
          swapped = true;
          best = cost;
          self.setBestPath(newPath, best);
        } else {
          // un-reverse the section
          section.reverse();
          path.splice(pt1, pt2 + 1 - pt1, ...section);
        }
      }
    }
  }
};

Random

This is an impractical, albeit exhaustive algorithm. It is here only for demonstration purposes, but will not find a reasonable path for traveling salesman problems above 7 or 8 points.

I consider it exhaustive because if it runs for infinity, eventually it will encounter every possible path.

From the starting path
Randomly shuffle the path
If it's better, keep it
If not, ditch it and keep going

Implementation

const random = async points => {
  let best = Infinity;

  while (true) {
    // save off the starting point
    const start = points.shift();

    // sort the remaining points
    const path = points.sort(() => Math.random() - 0.5);

    // put the starting point back
    path.unshift(start);

    // return to the starting point
    path.push(start);

    // calculate the new cost
    const cost = pathCost(path);

    if (cost < best) {
      // we found a better path
      best = cost;
    }

    // get rid of starting point at the end
    path.pop();
  }
};

Arbitrary Insertion

This is a heuristic construction algorithm. It select a random point, and then figures out where the best place to put it will be.

From the starting point
First, go to the closest point
Choose a random point to go to
Find the cheapest place to add it in the path
Chosen point is no longer an "available point"
Continue from #3 until there are no available points, and then return to the start.

Implementation

const arbitraryInsertion = async points => {
  // from the starting point
  const path = [points.shift()];

  //
  // INITIALIZATION - go to the nearest point
  //
  points.sort((a, b) => distance(path[0], b) - distance(path[0], a));
  path.push(points.pop());

  // randomly sort points - this is the order they will be added
  // to the path
  points.sort(() => Math.random() - 0.5);

  while (points.length > 0) {
    //
    // SELECTION - choose a next point randomly
    //
    const nextPoint = points.pop();

    //
    // INSERTION -find the insertion spot that minimizes distance
    //
    let [bestCost, bestIdx] = [Infinity, null];
    for (let i = 1; i < path.length; i++) {
      const insertionCost = pathCost([path[i - 1], nextPoint, path[i]]);
      if (insertionCost < bestCost) {
        [bestCost, bestIdx] = [insertionCost, i];
      }
    }
    path.splice(bestIdx, 0, nextPoint);
  }

  // return to start after visiting all other points
  path.push(path[0]);
};

Two-Opt Reciprocal Exchange

This algorithm is similar to the 2-opt mutation or inversion algorithm, although generally will find a less optimal path. However, the computational cost of calculating new solutions is less intensive.

The big difference with 2-opt mutation is not reversing the path between the 2 points. This algorithm is not always going to find a path that doesn't cross itself.

It could be worthwhile to try this algorithm prior to 2-opt inversion because of the cheaper cost of calculation, but probably not.

While a better path has not been found.
For each pair of points:
Swap the points in the path. That is, go to point B before point A, continue along the same path, and go to point A where point B was.
If the new path is cheaper (shorter), keep it and continue searching. Remember that we found a better path.
If not, revert the path and continue searching.

Implementation

const twoOptReciprocalExchange = async path => {
  path.push(path[0]);
  let best = pathCost(path);
  let swapped = true;

  self.setBestPath(path, best);

  while (swapped) {
    swapped = false;
    for (let pt1 = 1; pt1 < path.length - 1; pt1++) {
      for (let pt2 = pt1 + 1; pt2 < path.length - 1; pt2++) {
        // swap current pair of points
        [path[pt1], path[pt2]] = [path[pt2], path[pt1]];

        // calculate new cost
        const cost = pathCost(path);

        if (cost < best) {
          // found a better path after the swap, keep it
          swapped = true;
          best = cost;
        } else {
          // swap back - this one's worse
          [path[pt1], path[pt2]] = [path[pt2], path[pt1]];
        }
      }
    }
  }
};

Branch and Bound on Cost

This is a recursive algorithm, similar to depth first search, that is guaranteed to find the optimal solution.

The candidate solution space is generated by systematically traversing possible paths, and discarding large subsets of fruitless candidates by comparing the current solution to an upper and lower bound. In this case, the upper bound is the best path found so far.

While evaluating paths, if at any point the current solution is already more expensive (longer) than the best complete path discovered, there is no point continuing.

For example, imagine:

A -> B -> C -> D -> E -> A was already found with a cost of 100.
We are evaluating A -> C -> E, which has a cost of 110. There is no point evaluating the remaining solutions.
Instead of continuing to evaluate all of the child solutions from here, we can go down a different path, eliminating candidates not worth evaluating:
- A -> C -> E -> D -> B -> A
- A -> C -> E -> B -> D -> A

Implementation is very similar to depth first search, with the exception that we cut paths that are already longer than the current best.

Implementation

const branchAndBoundOnCost = async (
  points,
  path = [],
  visited = null,
  overallBest = Infinity
) => {
  if (visited === null) {
    // initial call
    path = [points.shift()];
    points = new Set(points);
    visited = new Set();
  }

  // figure out which points are left
  const available = setDifference(points, visited);

  // calculate the cost, from here, to go home
  const backToStart = [...path, path[0]];
  const cost = pathCost(backToStart);

  if (cost > overallBest) {
    // we may not be done, but have already traveled further than the best path
    // no reason to continue
    return [null, null];
  }

  // still cheaper than the best, keep going deeper, and deeper, and deeper...

  if (available.size === 0) {
    // at the end of the path, return where we're at
    return [cost, backToStart];
  }

  let [bestCost, bestPath] = [null, null];

  // for every point yet to be visited along this path
  for (const p of available) {
    // go to that point
    visited.add(p);
    path.push(p);

    // RECURSE - go through all the possible points from that point
    const [curCost, curPath] = await branchAndBoundOnCost(
      points,
      path,
      visited,
      overallBest
    );

    // if that path is better and complete, keep it
    if (curCost && (!bestCost || curCost < bestCost)) {
      [bestCost, bestPath] = [curCost, curPath];

      if (!overallBest || bestCost < overallBest) {
        // found a new best complete path
        overallBest = bestCost;
        self.setBestPath(bestPath, bestCost);
      }
    }

    // go back up and make that point available again
    visited.delete(p);
    path.pop();
  }

  return [bestCost, bestPath];
};

Furthest Insertion

This is a heuristic construction algorithm. It selects the closest point to the path, and then figures out where the best place to put it will be.

From the starting point
First, go to the closest point
Choose the point that is nearest to the current path
Find the cheapest place to add it in the path
Chosen point is no longer an "available point"
Continue from #3 until there are no available points, and then return to the start.

Implementation

const nearestInsertion = async points => {
  // from the starting point
  const path = [points.shift()];

  //
  // INITIALIZATION - go to the nearest point first
  //
  points.sort((a, b) => distance(path[0], b) - distance(path[0], a));
  path.push(points.pop());

  while (points.length > 0) {
    //
    // SELECTION - nearest point to the path
    //
    let [selectedDistance, selectedIdx] = [Infinity, null];
    for (const [freePointIdx, freePoint] of points.entries()) {
      for (const pathPoint of path) {
        const dist = distance(freePoint, pathPoint);
        if (dist < selectedDistance) {
          [selectedDistance, selectedIdx] = [dist, freePointIdx];
        }
      }
    }

    // get the next point to add
    const [nextPoint] = points.splice(selectedIdx, 1);

    //
    // INSERTION - find the insertion spot that minimizes distance
    //
    let [bestCost, bestIdx] = [Infinity, null];
    for (let i = 1; i < path.length; i++) {
      const insertionCost = pathCost([path[i - 1], nextPoint, path[i]]);
      if (insertionCost < bestCost) {
        [bestCost, bestIdx] = [insertionCost, i];
      }
    }
    path.splice(bestIdx, 0, nextPoint);
  }

  // return to start after visiting all other points
  path.push(path[0]);
};

Branch and Bound (Cost, Intersections)

This is the same as branch and bound on cost, with an additional heuristic added to further minimize the search space.

While traversing paths, if at any point the path intersects (crosses over) itself, than backtrack and try the next way. It's been proven that an optimal path will never contain crossings.

Implementation is almost identical to branch and bound on cost only, with the added heuristic below:

Implementation

const counterClockWise = (p, q, r) => {
  return  (q[0] - p[0]) * (r[1] - q[1]) <
          (q[1] - p[1]) * (r[0] - q[0])
}

const intersects = (a, b, c, d) => {
  return counterClockWise(a, c, d) !== counterClockWise(b, c, d) &&
         counterClockWise(a, b, c) !== counterClockWise(a, b, d)
}

const branchAndBoundOnCostAndCross = async (...) => {
  //
  // .....
  //

  if (path.length > 3) {
    // if this newly added edge crosses over the existing path,
    // don't continue. It's been proven that an optimal path will
    // not cross itself.
    const newSegment = [
      path[path.length-2], path[path.length-1]
    ]
    for (let i=1; i<path.length-2; i++) {
      if (intersects(path[i], path[i-1], ...newSegment)) {
        return [null, null]
      }
    }
  }

  //
  // .....
  //
}

Furthest Insertion

This is a heuristic construction algorithm. It selects the furthest point from the path, and then figures out where the best place to put it will be.

From the starting point
First, go to the closest point
Choose the point that is furthest from any of the points on the path
Find the cheapest place to add it in the path
Chosen point is no longer an "available point"
Continue from #3 until there are no available points, and then return to the start.

Implementation

const furthestInsertion = async points => {
  // from the starting point
  const path = [points.shift()];

  //
  // INITIALIZATION - go to the nearest point first
  //
  points.sort((a, b) => distance(path[0], b) - distance(path[0], a));
  path.push(points.pop());

  while (points.length > 0) {
    //
    // SELECTION - furthest point from the path
    //
    let [selectedDistance, selectedIdx] = [0, null];
    for (const [freePointIdx, freePoint] of points.entries()) {
      // find the minimum distance to the path for freePoint
      let [bestCostToPath, costToPathIdx] = [Infinity, null];
      for (const pathPoint of path) {
        const dist = distance(freePoint, pathPoint);
        if (dist < bestCostToPath) {
          [bestCostToPath, costToPathIdx] = [dist, freePointIdx];
        }
      }

      // if this point is further from the path than the currently selected
      if (bestCostToPath > selectedDistance) {
        [selectedDistance, selectedIdx] = [bestCostToPath, costToPathIdx];
      }
    }
    const [nextPoint] = points.splice(selectedIdx, 1);

    //
    // INSERTION - find the insertion spot that minimizes distance
    //
    let [bestCost, bestIdx] = [Infinity, null];
    for (let i = 1; i < path.length; i++) {
      const insertionCost = pathCost([path[i - 1], nextPoint, path[i]]);
      if (insertionCost < bestCost) {
        [bestCost, bestIdx] = [insertionCost, i];
      }
    }
    path.splice(bestIdx, 0, nextPoint);
  }

  // return to start after visiting all other points
  path.push(path[0]);
};

Convex Hull

This is a heuristic construction algorithm. It starts by building the convex hull, and adding interior points from there. This implmentation uses another heuristic for insertion based on the ratio of the cost of adding the new point to the overall length of the segment, however any insertion algorithm could be applied after building the hull.

There are a number of algorithms to determine the convex hull. This implementation uses the gift wrapping algorithm.

In essence, the steps are:

Determine the leftmost point
Continually add the most counterclockwise point until the convex hull is formed
For each remaining point p, find the segment i => j in the hull that minimizes cost(i -> p) + cost(p -> j) - cost(i -> j)
Of those, choose p that minimizes cost(i -> p -> j) / cost(i -> j)
Add p to the path between i and j
Repeat from #3 until there are no remaining points

Implementation

const convexHull = async points => {
  const sp = points[0];

  // Find the "left most point"
  let leftmost = points[0];
  for (const p of points) {
    if (p[1] < leftmost[1]) {
      leftmost = p;
    }
  }

  const path = [leftmost];

  while (true) {
    const curPoint = path[path.length - 1];
    let [selectedIdx, selectedPoint] = [0, null];

    // find the "most counterclockwise" point
    for (let [idx, p] of points.entries()) {
      if (!selectedPoint || orientation(curPoint, p, selectedPoint) === 2) {
        // this point is counterclockwise with respect to the current hull
        // and selected point (e.g. more counterclockwise)
        [selectedIdx, selectedPoint] = [idx, p];
      }
    }

    // adding this to the hull so it's no longer available
    points.splice(selectedIdx, 1);

    // back to the furthest left point, formed a cycle, break
    if (selectedPoint === leftmost) {
      break;
    }

    // add to hull
    path.push(selectedPoint);
  }

  while (points.length > 0) {
    let [bestRatio, bestPointIdx, insertIdx] = [Infinity, null, 0];

    for (let [freeIdx, freePoint] of points.entries()) {
      // for every free point, find the point in the current path
      // that minimizes the cost of adding the point minus the cost of
      // the original segment
      let [bestCost, bestIdx] = [Infinity, 0];
      for (let [pathIdx, pathPoint] of path.entries()) {
        const nextPathPoint = path[(pathIdx + 1) % path.length];

        // the new cost minus the old cost
        const evalCost =
          pathCost([pathPoint, freePoint, nextPathPoint]) -
          pathCost([pathPoint, nextPathPoint]);

        if (evalCost < bestCost) {
          [bestCost, bestIdx] = [evalCost, pathIdx];
        }
      }

      // figure out how "much" more expensive this is with respect to the
      // overall length of the segment
      const nextPoint = path[(bestIdx + 1) % path.length];
      const prevCost = pathCost([path[bestIdx], nextPoint]);
      const newCost = pathCost([path[bestIdx], freePoint, nextPoint]);
      const ratio = newCost / prevCost;

      if (ratio < bestRatio) {
        [bestRatio, bestPointIdx, insertIdx] = [ratio, freeIdx, bestIdx + 1];
      }
    }

    const [nextPoint] = points.splice(bestPointIdx, 1);
    path.splice(insertIdx, 0, nextPoint);
  }

  // rotate the array so that starting point is back first
  const startIdx = path.findIndex(p => p === sp);
  path.unshift(...path.splice(startIdx, path.length));

  // go back home
  path.push(sp);
};

Simulated Annealing

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem.

For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms

Implementation

const simulatedAnnealing = async points => {
  const sp = points[0];
  const path = points;

  const tempCoeff =
    path.length < 10
      ? 1 - 1e-4
      : path.length < 15
      ? 1 - 1e-5
      : path.length < 25
      ? 1 - 1e-6
      : 1 - 5e-7;

  const deltaDistance = (aIdx, bIdx) => {
    const aPrev = (aIdx - 1 + path.length) % path.length;
    const aNext = (aIdx + 1 + path.length) % path.length;
    const bPrev = (bIdx - 1 + path.length) % path.length;
    const bNext = (bIdx + 1 + path.length) % path.length;
    let diff =
      distance(path[bPrev], path[aIdx]) +
      distance(path[aIdx], path[bNext]) +
      distance(path[aPrev], path[bIdx]) +
      distance(path[bIdx], path[aNext]) -
      distance(path[aPrev], path[aIdx]) -
      distance(path[aIdx], path[aNext]) -
      distance(path[bPrev], path[bIdx]) -
      distance(path[bIdx], path[bNext]);

    if (bPrev === aIdx || bNext === aIdx) {
      diff += 2 * distance(path[aIdx], path[bIdx]);
    }
    return diff;
  };

  const changePath = temperature => {
    // 2 random points
    const a = 1 + Math.floor(Math.random() * (path.length - 1));
    const b = 1 + Math.floor(Math.random() * (path.length - 1));

    const delta = deltaDistance(a, b);
    if (delta < 0 || Math.random() < Math.exp(-delta / temperature)) {
      // swap points
      [path[a], path[b]] = [path[b], path[a]];
    }
  };

  const initialTemp = 100 * distance(path[0], path[1]);
  let i = 0;

  for (
    let temperature = initialTemp;
    temperature > 1e-6;
    temperature *= tempCoeff
  ) {
    changePath(temperature);
    if (i % 10000 == 0) {
      self.setEvaluatingPaths(() => ({
        paths: [{ path, color: EVALUATING_PATH_COLOR }],
        cost: pathCost(path)
      }));
      await self.sleep();
    }
    if (i % 100000 == 0) {
      path.push(sp);
      self.setBestPath(path, pathCost(path));
      path.pop();
    }
    i++;
  }

  // rotate the array so that starting point is back first
  rotateToStartingPoint(path, sp);

  // go back home
  path.push(sp);
  const cost = pathCost(path);

  self.setEvaluatingPaths(() => ({
    paths: [{ path }],
    cost
  }));
  self.setBestPath(path, cost);
};

makeSolver(simulatedAnnealing);

TSP-Salatiga-Map

Visualize algorithms for the traveling salesman problem. Use the controls below to plot points, choose an algorithm, and control execution.
(Hint: try a construction alogorithm followed by an improvement algorithm)

Current Best:

Evaluating:

Running For:

Algorithm

Controls

Show Best Path

Show Evaluated Paths

Show Evaluated Steps

Points

Traveling Salesman Problem

This project

Heuristic algorithms

Exhaustive algorithms

Dependencies

Contributing

Depth First Search (Brute Force)

Implementation

Nearest Neighbor

Implementation

Two-Opt inversion

Implementation

Random

Implementation

Arbitrary Insertion

Implementation

Two-Opt Reciprocal Exchange

Implementation

Branch and Bound on Cost

Implementation

Furthest Insertion

Implementation

Branch and Bound (Cost, Intersections)

Implementation

Furthest Insertion

Implementation

Convex Hull

Implementation

Simulated Annealing

Implementation

TSP-Salatiga-Map

Visualize algorithms for the traveling salesman problem. Use the controls below to plot points, choose an algorithm, and control execution.
(Hint: try a construction alogorithm followed by an improvement algorithm)

TSP-Salatiga-Map

Visualize algorithms for the traveling salesman problem. Use the controls below to plot points, choose an algorithm, and control execution.(Hint: try a construction alogorithm followed by an improvement algorithm)

Visualize algorithms for the traveling salesman problem. Use the controls below to plot points, choose an algorithm, and control execution.
(Hint: try a construction alogorithm followed by an improvement algorithm)