iSGTW Feature - Traveling salesman meets distributed computing


Feature - Traveling salesman meets distributed computing


The traveling salesman problem (TSP) is solved when the salesman travels through each of "n" cities while covering the least total distance. This shortest route is called a Hamiltonian circuit; however, there is no known general method for finding the TSP solution.
Image courtesy of Wolfram Mathworld

The traveling salesman problem (TSP) is a classic combinatorial problem: given a set of cities, what is the path that visits each city once and only once, while covering the minimum distance?

For a small set of cities, the solution is trivial and can be discovered by simple inspection; however, the solution for even a moderate number of cities is out of reach for most home computers. For example, to exhaustively check all possible paths for a 48 city instance-assuming you could check one million paths a second-would take approximately 1047 years.

Despite all the research, there is still no known general solution to the TSP.

Who cares about traveling salesmen?

Do we really need to know how to get a traveling salesman to our door in the shortest time? No, but generic forms of the TSP have been used in laying out circuit boards, cutting raw materials, clustering data arrays, analyzing crystal structures, scheduling and much more.

Distributed salesmen

The first goal of the TSP project is to do an exhaustive search of a 48 city TSP. Once the optimal paths are known, we will test the various search algorithms for their ability to find these optimal paths.

The next step will be to see if a combination of search algorithms and brute force tactics can produce an optimal result. Then it will be time to stress test any theories that come from this work by searching some really big TSPs.

In the beginning

The TSP project started out as a proof of concept. I just wanted to see if I could do it. I thought I would just put up this little project and have a few friends attach to it.

The TSP project's first task is to calculate the optimum solution to the TSP across 48 cities in the U.S. New solutions are constantly being computed using BOINC-powered volunteer distributed computing.
Images courtesy of TSP

Somehow word got out, and before I knew it, a group of alpha testers were in the forums providing encouragement. According to allprojectstats.com I have 1400 hosts and 600 users representing 50 countries: it's all thanks to the BOINC community.

Why TSP runs: a few thank yous

There are very few "killer apps" in this world and BOINC qualifies in every aspect.

Some of the most smart, friendly, unassuming and patient folks from around the world are always ready to help. The BOINC community provides help with every aspect of the project: code development, server configuration, advice on end user expectations, credit granting schemes, client setup, application development...

I may have written the software, but it's the BOINC community that keeps this project going. People have volunteered their time to build applications for different platforms, or to build optimized applications. All the graphics on the site were courtesy of a BOINC community member volunteering their time.

- Markus Weltin, TSP director