About

Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is a classical combinatorial problem that involves visiting each city once and minimising the overall tour length. The difficulty of the problem is that as the number of cities (n) increases, so does the number of possible tours from which the minimum must be selected (0.5*(n-1)!). (more...)

Computational problems are organised into common classes of difficulty. Those problems that cannot be solved in polynomial time are referred to as NP-hard and represent some of the hardest known computational problems. The TSP belongs to a sub-set of NP-hard called NP-complete, highlighting the innate difficulty of the problem (more...)

The TSP is a well studied problem in computer science and there are many specialised resources on the web dedicated to interested researches. TSPLIB provides a library of sample problems that may be used when empirically investigating instances of the general class of problem. This site selected common instances of the Euclidean TSP with known solutions from TSPLIB. (more...)

Crowdsourcing

Crowdsourcing is an outsourcing technique where a problem is partitioned into sub-problems and assigned to a crowd of people for solving. The sub-solutions are then collected and aggregated back into a holistic solution. The web provides an popular platform for this form of problem solving. (more...)

A powerful application of the crowdsourcing model involves harnessing problem solving capabilities of humans toward solving problems that are too difficult for computers. This approach has been used to address machine vision and pattern recognition problems and is referred to as Human Computation. (more...)

Human TSP Solver

The site was built to investigate the question:

The approach taken involves: (1) partitioning TSP instances into sub-problems, (2) allowing users to make contributions in the context of the sub-problems, and (3) aggregating the contributions into a holistic solution. A database of problems is maintained, and contributions are recorded against instances of those problems, where an instances are rotated periodically.

Sub-problems are selected randomly with re-selection of sub-problems. The process involves firstly the selection of a random city in the broader problem, then the selection of a limited number of cities with a minimum distance to the selected origin city.

Contributions are provided by users in the form of edges between cities in presented sub-problems. There is no discrimination of of contributions, meaning that users are free to contribute whatever they feel may be relevant or useful to the problem . Contributions are aggregated and stored as a frequency for each distinct edge in an incidence adjacency list.

The stored contributions provide a summary of those edges that are expected to be useful in solving the broader TSP (far fewer than the possible set of edges). These may be explored by a deterministic or probabilistic algorithm, or by the users themselves to provide a holistic solution to a problem instance.

A New Frontier

This is an exciting project as there is vast potential and many unknowns in harnessing the collectively intelligent web toward addressing hard computational problems.

We don't know what kind of contributions users will make, or what will emerge in terms of holistic solutions. For example, you may be interested in this set of papers on assessing human spatial intelligence toward solving instances of the TSP, highlighting the cognitive potential just waiting to be unlocked.

We don't even know the best way to use the collected data. This is an evolving application in an emerging field and we would appreciate any and all feedback and ideas you may have to offer!

Conversations

Conversations about the human TSP solver from my blog and around the web:

• Crowdsourcing NP-Complete Problems, April 2008
• Considering User Experience in Crowdsourced Problem Solving, April 2008
• Connect The Dots: A Human-Based TSP Solver, April 2008
• Human TSP Solver, May 2008
• William Cook and the TSP @ Georgia Tech, May 2008
• TSPLIB: A Library of Standard TSP Instances, May 2008
• Human TSP Solvers and the Convex Hull Hypothesis, May 2008
• A Human TSP Solver in Rails, One Month On, May 2008
• Human Powered Databases: Some Lessons Learned, June 2008
• More Lessons Regarding Crowdsourcing, June 2008