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?".

- The goal of this site is to be an
**educational**resource to help visualize, learn, and develop different algorithms for the traveling salesman problem in a way that's easily accessible - As you apply different algorithms, the current best path is saved and used as input to whatever you run next. (e.g. shortest path first -> branch and bound). The order in which you apply different algorithms to the problem is sometimes referred to the meta-heuristic strategy.

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)

- Shortest Path
- Arbitrary Insertion
- Furthest Insertion
- Nearest Insertion
- Convex Hull Insertion*

**Improvement** - Attempt to take an existing constructed path and improve on it

- 2-Opt Inversion
- 2-Opt Reciprcal Exchange*

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:

- Random Paths
- Depth First Search (Brute Force)
- Branch and Bound (Cost)
- Branch and Bound (Cost, Intersections)*

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 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.

```
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, 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.

```
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 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. )

```
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 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.

```
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 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.

```
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 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

```
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 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.

```
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 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.

```
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 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.

- 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.

```
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:

- 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

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

Current Best:

kmEvaluating:

kmRunning For:

sAlgorithm

Convex Hull

Controls

Delay

Show Best Path

Show Evaluated Paths

Show Evaluated Steps

Points

Number of random points

Possible Paths:

0 x 10