The traveling salesman problem (TSP) asks the question, "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?".
Heuristic algorithms attempt to find a good approximation of the optimal path within a more reasonable amount of time.
Construction - Build a path (e.g. shortest path)
Improvement - Attempt to take an existing constructed path and improve on it
Exhaustive algorithms will always find the best possible solution by evaluating every possible path. These algorithms are typically significantly more expensive then the heuristic algorithms discussed next. The exhaustive algorithms implemented so far include:
These are the main tools used to build this site:
Pull requests are always welcome! Also, feel free to raise any ideas, suggestions, or bugs as an issue.
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,
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:
:
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];
};
This is a heuristic, greedy algorithm also known as nearest neighbor. It continually chooses the best looking option from the current state.
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);
};
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.
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);
}
}
}
}
};
This is a heuristic construction algorithm. It select a random point, and then figures out where the best place to put it will be.
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]);
};
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.
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();
}
};
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.
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]];
}
}
}
}
};
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:
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.
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];
};
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.
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]);
};
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:
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]
}
}
}
//
// .....
//
}
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.
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]);
};
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:
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 (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
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);