A salesperson wishes to visit every city on a map and return to a starting point. They want to find a route that will let them do this with the shortest travel distance possible. How can they efficiently find such a route given any random map?

Well, if you can answer this, the Clay Mathematics Institute will give you a million dollars. It’s not as easy of a task as it sounds.

The problem summarized above is called the Traveling Salesman Problem, one of a category of mathematical problems called NP-complete. No known efficient algorithm to solve NP-complete problems exists. Finding a polynomial-time algorithm, or proving that one could not possibly exist, is a famous unsolved mathematical problem.

Over years of research, many advances have been made in algorithms that can solve the problem, not in perfectly-efficiently time, but quickly enough for many smaller examples that you can hardly notice. One of the most significant Traveling Salesman Problem solutions is the Concorde TSP Solver. This program can find optimal routes for maps with thousands of cities.

Traveling Salesman Problems can also be used outside of the context of visiting cities on a map. They have been used to generate gene mappings, microchip layouts, and more.

The power of the legendary Concorde TSP Solver is available in Maple. The TravelingSalesman command in the GraphTheory package can find the optimal solution for a given graph. The procedure offers a choice of the recently added Concorde solver or the original pure-Maple solver.

To provide a full introduction to the Traveling Salesman Problem, we have created an exploratory document in Maple Learn! Try your hand at solving small Traveling Salesman examples and comparing different paths. Can you solve the problems as well as the algorithm can?