Getting There

Let's say there's a traveling salesman trying to hit a certain group of towns during a week. (I know, I know: eCommerce is eclipsing the traveling salesman these days, but I’m Old School, so bear with me.) To save time, this traveling salesman wants to calculate the best possible route between all the cities—the route with the absolute shortest possible distance—before he returns to the starting city.

Sounds easy: just add up all the shortest distances between cities. Right?

Wrong.

In fact, if you tried the calculations on a home computer, the sun would have already devoured the Earth in its death-throes, billions of years in the future, by the time your computer finished the calculations. (The problem is actually what they call an NP-complete problem, and it’s really complicated, and it makes my head spin, and good luck.)

That's why Google Maps only optimizes routes with no more than ten waypoints in them because going beyond that just requires too much time and computing power. For those of us without the patience to wait billions of years, there are workarounds to the Traveling Salesman Problem.

A Solution to the Problem

One of the best ways is to use something called a genetic algorithm, which begins with a handful of random solutions to the problem…and usually ends up being terrible. So, it then tinkers slowly with each one, discarding all but the best solutions. Eventually, after enough cycles of this, the algorithm produces a route that, while not the absolute best, seems reasonable enough.

The practical applications of the Traveling Salesman problem should be obvious. To shipping companies alone, it represents a ton of time and money. Other industries that are concerned with it include semiconductor manufacturers and paper mills.

We also have a large number of variants in this challenge, including the appropriately named Traveling Politician Problem.