The traveling salesman problem (TSP) asks , Given a set of cities and the distances between them, what is the shortest possible route that visits every city exactly once and returns to the starting city?
This project is an interactive visualization platform for exploring and comparing different approaches to solving the Traveling Salesman Problem.
Users can:
A greedy algorithm that repeatedly visits the nearest unvisited city.
Advantages
Disadvantages
A local search optimization technique that improves an existing route by removing inefficient edge crossings.
Advantages
A metaheuristic optimization algorithm inspired by the annealing process in metallurgy.
Advantages
Disadvantages
This project demonstrates the tradeoff between:
and allows users to compare how different optimization strategies perform on the same set of cities.
These are the main tools used to build this site:
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);
}
}
}
}
};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);