The Traveling Salesman Problem

Computer science and mathematics have a wonderful problem called the Traveling Salesman Problem or TSP. There are variants, too, the Canadian Traveler Problem and the Chinese Postman Problem. All three problems are attempts to use math to solve ancient problems faced by people and their societies.

Imagine your name is Og and you have rocks to sell in nearby towns and villages. Your rocks are heavy and you do not want to be away from home longer than needed to sell all your rocks. Given the number of towns and villages, and the distances between each pair of villages, what would be the shortest route to visit each town or village once and return to your home?

Here is the easiest possible route if all the destinations are neatly laid out in a circle:

Example of traveling salesman path — The Perfect Route for Og, Traveling Salesman

In this ideal world, Og can travel in a circle from A-Town to B-Town to C-Town. Or the reverse on days he (or she) gets bored.

However, this arrangement of villages is more likely:

More realistic traveling salesman path — A More Likely Map of Towns and Villages

If each dot represents a village or town, what is the shortest route Og can take to sell rocks? It’s not at all clear, is it?

Here is one way to describe the traveling salesman problem and narrow down the range of possible solutions:

In mathematical terms, the Traveling Salesman problem is a graph problem. While algorithms exist to help solve this problem, the ideal solution is difficult to find. There are so many possible alternate routes to be evaluated then compared to other routes.

Learn More

Learn More

Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem

Canadian Traveler Problem

Chinese Postman Problem