The Travelling Salesman Problem

The Travelling Salesman Problem can be solved by determining the quickest route that visits each provided plot and returns to where it started. For example, here are five plots with the optimal route and one of many suboptimal routes:

Visually, it is easy to tell what the optimal route is for this field of plots; I can solve this thing with my eyes! Who needs computers? Programmatically, this cannot be truly solved without using permutation in an algorithm. Exact algorithms use different optimizations to reduce permutations, but no one has actually solved it. There are many heuristic algorithms that calculate suboptimal paths much quicker than exact algorithms, but cannot prove they are the most efficient path and are often far from it.

Here is an example of what is considered an “easy” solution generated by an exact algorithm:

...and here's the best we’ve ever achieved (is within 0.024% of optimal) for the unsolved problem of all Chinese cities:

I have chosen to play with the Travelling Salesman Problem in my spare time over the past two years and continue to have fun with it today. This post is not going to present anything more than my currently incomplete thoughts. If I waited until I solved the problem before blogging about it, there would be an infinitesimally small chance I would ever blog about it at all. That is why I’m here rambling about incomplete ideas regarding an impossible thing.

Why I'm doing it

When I learned that this problem exists, it excited me; not because I think I can actually solve it, but because I could interact with something unknown. Unknown things have few rules. It is like shooting a ball into a hoop without the game of basketball being invented yet. Not having a background in computer science always “kept me off the monkey bars” on these sorts of playgrounds. But if Michael Faraday reinforced any ideology, it is that amazing things can come from thinking outside of convention.

Some might see this process as sisyphean— relentlessly unending and repetitive. I see it is as an opportunity to think for myself. How would I go about solving this problem? It is an opportunity to explore uncharted land. Perhaps I will land somewhere interesting and discover a new heuristic or optimization...I probably won’t. At this point, neither outcome matters much to me. The one thing I do know is that throwing yourself into something for the sake of exploration is never a bad thing thing if you are passionate about it—and I am passionate about the TSP.

Observation 1
“It is a difficult problem”

This is probably my greatest realization to date...

One of many reasons why the TSP is so difficult is because of a complexity that is observable in an extremely simple case. Although it seems like the best thing to do, connecting close plots to each other isn’t always the best thing to do. Here we have an optimal path. We’re going to focus on purplebluegreen. We have two paths, one without and one with plot brown.

When we add brown in the upper right, purplebluegreen becomes purplegreenblue. This gives us the logic, “If brown exists, then do purplegreenblue, otherwise do purplebluegreen”. But look what happens if we remove the bottom right yellow:

What happens is that we lose the “closest” association between the three plots purplebluegreen. brown has replaced green in the group purpleblueWHATEVER even though green is so damn close to both purple and blue. All this from removing yellow. So how the hell do you determine whether or not you should go to green from plot purple? In this sense, purple needs to know the “future” of the path (whether or not yellow exists) in order to make a decision in the “present”. This is a simple example of something that only gets more complicated the more plots you have.

Observation 2
“There is a center”

When I learned this problem exists two years ago, I grabbed a legal pad, drew some dots, and asked myself, “How would I naturally connect these?” My first observation was that there was a center. This groundbreaking revelation is probably treated as obvious in smarter people’s work (it’s called a centroid), but I think it is the most implicative observation I have made to date. If there is a center, you can determine what is on the perimeter, what is central, and what is in-between. This is crucial, because the behavior of a path clearly changes based on where plots lie in relation to it.

Observation 3
“Furthest first”

The first assumption I made after realizing there was a center was that the further a plot is from the center of the field, the more important it seems that they are attached to nearby plots. In a way, outer plots take priority over inner plots. Let’s look again at our last example:

Here I have added a white point that is in the center, or centroid of the set. Any future visualization in this post will visualize the centroid this way. This is the order of plots, furthest from centroid to the closest:

orange brown red blue green purple

This path could be seen as being drawn in that order with the following logic:

  • orange to its closest green
  • brown to its closest blue
  • red to its closest purple
  • blue to its closest purple
  • green to its next closest brown (blue and purple are already connected)
  • purple to nothing since it already has two connections
  • orange to red to close the path

One of the first pens I made about TSP used this reasoning in a heuristic to help me get some surprisingly accurate results. Since I did not think I would be creating any more pens related to the TSP, I just called it The Travelling Salesman Problem:

See the Pen The Travelling Salesman Problem by Jake Albaugh (@jakealbaugh) on CodePen.

My solution is the generated topmost image in that pen and the preexisting optimal path is the last image. This solver solves to 5-25% longer paths and takes significantly less time. This example took 9% the time of the world record to hit a 6% longer path! It has run over other larger problems and had great results, like a 20% longer path in 0.26% of the time. Not to mention it uses JavaScript in a browser. Take that, super computer.

Creating this pen made me feel confident that this pursuit wasn’t a complete waste of time.

Observation 4
“Round, Divide, and Conquer”

After losing myself in “Furthest first” thought for six months, I took a break. When I returned to the problem, I started thinking about the problem differently. Clearly, proximity to center is meaningful but in order to find the “closest” plot for a given plot, I would have to calculate the distance between it and all other plots. These permutations would get more and more computationally expensive the more plots in the set. That is when I realized that if I could group plots based on their location, my permutations would be significantly reduced. I have since learned that this is called “Divide and Conquer” in the world of algorithms. But how would I group them? After some time it finally clicked— I could round plot positions.

For example, lets say I have four plots with x and y coordinates between 0 and 1.

  let plots = [
  { x: 0.00, y: 0.00}, { x: 0.15, y: 0.20},
  { x: 0.85, y: 0.80}, { x: 1.00, y: 1.00}
];

That would look something like this:

Clearly, the two groups are redpurple and bluegreen. But how do we express that in a program? We simply round the positions at a scale. In this case, we will round each plot coordinate to the closest 0.5 and group by that value.

  let plots = [
  { x: 0.00, y: 0.00}, { x: 0.15, y: 0.20},
  { x: 0.85, y: 0.80}, { x: 1.00, y: 1.00}
];

let groups = {};
plots.forEach(({ x, y }) => {
  // rounding to closest 0.5
  let roundedX = Math.round(x * 2) / 2,
      roundedY = Math.round(y * 2) / 2;
  // group name is the values dash separated
  let group = `${roundedX}-${roundedY}`;
  // set group to an array if it doesnt exist
  if (!groups[group]) groups[group] = [];
  // add the plot to the group
  groups[group].push({ x, y });
});

This will yield a new object with two groups.

  {
  "0-0": [{ x: 0, y: 0 }, { x: 0.15, y: 0.2 }],
  "1-1": [{ x: 0.85, y: 0.8 }, { x: 1, y: 1 }]
}

[0.15, 0.2] is closer to [0, 0] than it is to [0.5, 0.5]. The same is true for [0, 0]. That is why they are in group 0-0. I took a TSP set of plots and animated this idea in a pen. I group at different scales in sequence from a very small group size to a very large one (eg. 0.0625, 0.125, 0.25, 0.5). All plots move towards whatever group they are being rounded into. At the time, I thought of the group size as a “scope” hence the title, “Cubic Scoping”.

See the Pen Travelling Salesman Sketches: Cubic Scoping by Jake Albaugh (@jakealbaugh) on CodePen.

This evolved into my “Hamilton Range” pen which shows each scope group as a square for each generated plot at six different scales. Use the slider to change the quantity of plots:

See the Pen Travelling Salesman Sketches: Hamiltonian Range by Jake Albaugh (@jakealbaugh) on CodePen.

The cool thing about rounding everything to a grid is that you have known coordinates and known distances. I don’t need to calculate the distance between plots if I already knew the distances between their groups. For example, if I moved every plot its closest corner of the square field, I would have at most four groups, know the distance between the corners, and easily path around them. If I applied the same logic inside each group at the next smallest scale, I could do this recursively until there were no more groups. I have yet to use this to build a solid heuristic, but frequently use the principles of it in my sketches.

Observation 5
“Triangles are simple”

Triangles only have one path— the optimal path. abc, acb, bac, bca, cab, cba all yield the same path (shown below). The same is true with groups of two points ab, ba or one point a. I know this is mind-blowing. If only there were only three or less cities in the world.

This realization made me think, “What if everything could be grouped in groups of three or less, then those groups grouped in groups of three or less and so on?” The optimal path would already known, you would just connect the dots. This thought combined with the idea of proximal grouping led me to some work visualized in my pen “Triangular Proximal Grouping”:

See the Pen Travelling Salesman Sketches: Triangular Proximal Grouping by Jake Albaugh (@jakealbaugh) on CodePen.

This pen groups plots in threes, then those groups in threes, then those groups in threes and so on. The thinking being that you would connect each group and solve the problem. It is an incomplete idea, but definitely has some room for exploration.

Observation 6
“Radial Bias”

Let’s say we have four plots, each in a corner of a square. Where do we start drawing the path? We could use “Furthest first” to determine a priority, but in the case of this square all the plots have the same distance from the centroid.

Westerners may choose the top left red simply because of how they read words, others may start at the top right purple, contrarians may choose the bottom right blue, anarchists might flip two coins. No one would be wrong starting from any plot.

Exact algorithms cannot afford free will. We need to establish a rule to break ties. This led to my handy concept of Radial Bias. I would assign each point a radial value based on its relative position to the centroid. If it shared proximity from the center with another plot, preference would be determined by this radial position. Two plots can live at the same distance and they can share the same radial degree, but they cannot share both.

As soon as I started programming with this bias, I discovered it gave me a starting point. Once you establish a starting point and a bias, you create the idea of direction. When you have a start and a direction, you have a future. For example, our square above is easily solved by starting at a point then rotating either clockwise or counter clockwise (just choose one). That chosen direction of rotation is your bias. If there is a solution for the TSP, I am fairly confident it requires a radial bias and will work in either clock direction.

Using this radial bias, you can easily create a complete path for any set. You just connect each plot after sorting by radial position from the centroid. With small amounts of plots, you get some fairly efficient paths. With large amounts of data however, it totally falls apart. My pen “Radial Position” showcases this approach. Drag the slider to change the quantity of randomly generated plots:

See the Pen Travelling Salesman Sketches: Radial Position by Jake Albaugh (@jakealbaugh) on CodePen.

Observation 7
“Hidden Dimensions”

Throughout this post, there have been a handful of references to the future of a path. It is easy to understand what I mean when I say, “future” when you look at a completed path because we travel along a path while we observe it. Inside of a program, future ends up being a fairly evasive concept. One parallel I found in science is Fermat’s Principle of Least Time which applies to how light travels. I hardly know what I am talking about, but I will attempt to convey here, starting with this very crude drawing (whose eraser marks showcase my ignorance):

I am drowning in the ocean and there is a lifeguard who is deciding the quickest way to get to me. The lifeguard can run on sand quicker than they can swim in water. Path A is the direct route, which would be the optimal path if this were all on land. Path B reduces the lifeguard’s time spent swimming as much as possible, but adds the most distance to travel. Path C is the optimal path as it reduces time in the water as much as it can without adding so much distance that it will take more time.

In terms of sheer distance, shortest path would be A, the least swimming time would be B, but the quickest path to get to me (the one that saves my life) is C. Fermat’s Principle of Least Time implies that beams of light do the same thing. It is a controversial topic and ends up being more philosophical than scientific because light can’t possibly know where it is going. I am not drowning at the end of a light beam. And yet, a light beam’s path is remarkably the optimal path B when it is reflected. Does a light beam have a destination? Does it choose where it lands? Apparently ants (of all things) know the answer.

Ants use Fermat’s principle to travel to a food source efficiently and that fact alone should blow your mind. Quite literally, ant colonies are smart enough to solve math problems without understanding math. Take that, society. I knew I was on the right path of thought when I learned my observations of Fermat’s similarity to the TSP were confirmed by pathing heuristics found in existing Ant Colony Optimzation Algorithms. Ok, so we use ant logic to solve math problems. Is there then a link between Fermat’s lifeguard and the TSP? I started fiddling around, and the pieces started to fit together.

What if our two-dimensional TSP plot set was actually hiding a dimension? The three-dimensional lifeguard analogy uses the fourth dimension time (speed on sand and in water) to solve a three-dimensional problem. What if my little two-dimensional canvas illustrations needed a third dimension? What would speed be in two-dimensional sets? I have come to refer to it as altitude and use the proximity from centroid as the factor for altitude. I visualized this idea in my pen “Two-dimensional Altitude”

See the Pen Travelling Salesman Sketches: Two-dimensional Altitude by Jake Albaugh (@jakealbaugh) on CodePen.

This pen visualizes a two-dimensional set taken from math.uwaterloo.ca/tsp (the image below it). It assigns an altitude that is higher the closer you get to the centroid of the set. This puts plots further from the center further from each other, and plots closer to the center, closer to each other. Distance is now calculated three-dimensionally because each plot is measured by an x, y, z instead of simply x, y. If we were solving a three-dimensional TSP set, this extra altitude would be replaced by something that influences time like friction or gravity.

If you can bear with me, let’s not stop there. Let’s suppose that two-dimensional proximity is actually best calculated in three dimensions and theorize that there is a three-dimensional mass inside of them. To illustrate, let’s compare our two-dimensional sets from earlier cast in three dimensions with this mass. Again, pay attention to purplebluegreen.

This three-dimensional view is what I am currently calling the “Centroid Cone”. Each plot is assigned an altitude based on its proximity to the “peak” centroid of the polygon. At which point, proximity is actually seen not just as a straight line between two plots, but as distance one would have to travel around the cone to reach the point.

Now we will again add brown and get purplegreenblue. Notice how green has moved to the opposite side of the cone but is very close to the peak so it is still close to purple and blue.

Finally, removing yellow we add brown and get the brain-bending purplebluebrown. Observe how green has moved much further away from purple and blue on the opposite side of the cone.

I am proposing that in the same way that water “slows” a lifeguard, altitude and position around the cone increase distance. If you and I were standing at the base of a cone on opposite sides, the distance between us would be half the circumference of the base of the cone (assuming I sucked at climbing). If we were on opposite sides at the narrower top, that distance would be significantly less. Forgive another crude drawing:

At the base, getting around the cone at x is much greater than getting around the cone at the top at y. The higher you are on the cone, the closer you are to the other side. We can visualize these cones again from a bird’s eye view compared again to our original two-dimensional sets:

Here we are visualizing Fermat’s velocity (the “extra” effort) by adding a radially-based midpoint (the smaller colored dots) between the plots and bending the path with a quadratic curve. Think of these as the “unwrapped” version of the three-dimensional cones above. Because of this curve, the distances between plots are increased. This extra distance would only be used to calculate a virtual proximity between plots, not the actual proximity. That actual distance is still the sum of the straight lines between plots. ...Or is it?

And that brings us up to date with where I am currently at in my attempts at solving this problem. If you aren’t asking, “Are we done yet?” you may be asking, “What next?”

Future

First of all, I need to put the thoughts above into one cohesive heuristic so that I can test them. I am also curious if the altitude discussed above requires a gravitational bias (after all, going downhill is easier than uphill). After I do that, I have one thing I’d like to explore.

After thinking over the connections between Fermat’s thoughts on light and the TSP, I have started wondering if there are any connections to another mysterious problem that also involves light. The Double-slit experiment demonstrates that matter and light can behave like both waves and particles. If you haven’t heard of it already, please please please look it up. It is incredible, even to not-scientists and not-mathematicians like me. A video to make it easy.

I want to apply the proportions of distribution in interference patterns created by photons in the Double Slit Experiment (below) to a heuristic for the TSP. The thought is that these patterns might be a mechanism by which light beams presumably explore in Fermat’s Principle of Least Time in an attempt to end in the most optimal path. Think of it as trying to hit a single rasin by throwing a 3,000 grains of sand at it instead of throwing a single grain of sand 3,000 times.

If there is a solution for the TSP and if light and ants somehow “intuit” optimal pathing, my guess is that there is a principle being applied that would be connected to the mysteries found in our understanding of quantum mechanics.

I’ll end with this. If the TSP exists in a dimensional form and we could theoretically prove that it requires a superior dimensional perspective to solve it, in which dimension does it stop existing? If we successfully applied the TSP to four dimensions, does it necessitate a fifth in order to model a solution? If so, at which dimension does it stop necessitating the next?


If you are interested and want to see more work like this, check out my Travelling Salesman Problem Collection on CodePen or feel free to reach out to me.


4,255 3 16