Human TSP Solver: Crowdsourcing the Travelling Salesman Problem

Home

Author

Jason Brownlee

Description

A web application to collect and manage crowdsourced user contributions for the solving of the Traveling Salesman Problem (TSP)

Quick Start

1. Acquire a copy of the code base (download the zip or clone the git repository).
   1. Download: Human TSP Solver
2. Load the provided collected crowdsourced database (user emails have been stripped)
   1. gunzip db/data/dump.sql.gz
   2. mysql -u root < db/data/dump.sql
3. Start the server: script/server
4. Access the website: http://localhost:3000

History

This project was conceived and constructed between April 2008 and May 2008. The web application was launched on the domain humantspsolver.com and was made publicly available between May 2008 and April 2009. The application was then decommissioned and the database of user contributions captured. The codebase and collected user data was then open sourced on github in August 2009.

Details

The project was an experiment to test the idea of collecting multiple user-defined partial solutions to large TSP instances. Data was collected via a web application that encouraged user participation via a competitive game and leader board environment. Although the data has been collected, it has not yet been analyzed or exploited and is now provided as open source for interested parties.

A given TSP instance is selected for solving over an extended period (1 week) by an administrator. All users that access the website during that period are exposed to puzzles of dots that they must connect in efficient ways. Each puzzle represents a partial contiguous field of points from the current TSP. All edge contributions are captured and stored in a database, the aggregation of which is presented to interested users as a solution. User scoring is based on the number of edge contributions provided, and a game score is displayed based on how the users contribution compares to a naive nearest neighbor solution.

All TSP instances are symmetrical, drawn and loaded from files from the TSPLIB project.

For full details on the project, see the about page in the web application (/about) or see the wiki for codebase on github.

Technology

The web application was programmed in Ruby on Rails 2.0.2. The user game was programmed in Java as an applet and compiled against a Java 1.2 compiler for general compatibility. Although I am a seasoned developer, this was my first Rails project so the code is a little rough in places.

Development

The code is presented as a Rails application. The applet source code is provided under the /applet directory and may be compiled using the provided ant script (build.xml). The compiled applet is included in the rails application and is expected in the /public/java directory with the name solver.jar.

To access the administration console you must be logged in as the admin user (jasonb:jasonb) and then type the URL /admin (for example: http://localhost:3000/admin). The admin console allows one to specify the current TSP for the crowd to work on (Manage Problem Instances) as well as the problems/solutions available to the system (Manage Problem Uploads).

Reports

As this was an experiment, I wrote a number of technical reports in the early stages of the project and presented the premise for the project to my then research group. All reports are provided as PDF in the /reports directory. The following provides a summary of the reports:

• Solver Project: Overview, Jason Brownlee, Technical Report 20080505A
  • Provides a summary of the general project including the technical concerns of solving the TSP from partial solutions and the user experience for making the a game as the solver interface.
• Solver Experiment: Sub-Problem Generation, Jason Brownlee, Technical Report 20080505A
  • An experiment to assess two different TSP subproblem generation schemes: random and spatial sub-problem generation.
• Solver Experiment: Sub-Problem Solvers, Jason Brownlee, Technical Report 20080505A
  • An experiment to assess the effect of different human-based solving strategies. An attempt at evaluating the viability of the general approach based on some assumptions as to the way humans may or may not solve sub-tours.
• Solver Experiment: Sub-Solution Visualisation, Jason Brownlee, Technical Report 20080505A
  • An experiment into the preparation, visualization, and assessment of the visualization of aggregate partial solutions.
• Crowdsourcing NP-Complete Problems on the Web!?, Jason Brownlee and Daniel Angus, Presentation to the Complex Intelligent Systems Lab, Swinburne University of Technology
  • A presentation of the premise for the project and results of early experimentation.

Further Reading

• Crowdsourcing NP-Complete Problems, Jason Brownlee, April 28, 2008
• Considering User Experience in Crowdsourced Problem Solving, Jason Brownlee, April 29, 2008
• Connect The Dots: A Human-Based TSP Solver, Jason Brownlee, April 30, 2008
• Human TSP Solver, Jason Brownlee, May 17, 2008
• Human TSP Solvers and the Convex Hull Hypothesis, Jason Brownlee, May 24, 2008
• A Human TSP Solver in Rails, One Month On, Jason Brownlee, May 26, 2008

Screenshots

License

(The MIT License)

Copyright © 2008-2009, Jason Brownlee

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the “Software”), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.