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);
};

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]);
};

Nearest 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]);
};

Farthest Insertion

This is a heuristic construction algorithm. It selects the farthest 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 farthest 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 farthestInsertion = 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 - farthest 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);

ID	0	1	2	3	4
0	0	253	504	476	421
1	253	0	609	353	387
2	504	609	0	457	307
3	476	353	457	0	150
4	421	387	307	150	0

The Branch and Bound Algorithm

Traveling Salesman Problem

This project

Initial Solution

Search Strategies

Bounding Strategies

Dependencies

Use

Nearest Neighbor

Implementation

No Initial Solution

Arbitrary Insertion

Implementation

Nearest Insertion

Implementation

Farthest Insertion

Implementation

Convex Hull

Implementation

Simulated Annealing

Implementation

Distance Matrix

Expanded Tree

SeeBnB

SeeBnB is a tool to help visualize the branch and bound algorithm for the traveling salesman problem. Use the controls below to customize the algorithm, control execution, and plot points.

Number of nodes explored:

Start the Branch and Bound algorithm to build the node tree.

ID	0	1	2	3	4
0	0	253	504	476	421
1	253	0	609	353	387
2	504	609	0	457	307
3	476	353	457	0	150
4	421	387	307	150	0

ID	0	1	2	3	4
0	0	253	504	476	421
1	253	0	609	353	387
2	504	609	0	457	307
3	476	353	457	0	150
4	421	387	307	150	0

ID	0	1	2	3	4
0	0	253	504	476	421
1	253	0	609	353	387
2	504	609	0	457	307
3	476	353	457	0	150
4	421	387	307	150	0