Feature - Traveling salesman meets distributed computing
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.
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.
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