SolveIt: Leveraging the "Wisdom of the Crowd" to Solve Complex Facility Location Problems

TL;DR

Locating the perfect spots for fire stations or polling booths is a classic NP-hard problem that usually requires heavy computation. This paper introduces SolveIt, a gamified platform that turns these "p-median" problems into a simple drag-and-drop game. By tapping into human visual perception, the crowd can reach 98.5% accuracy—often outperforming standard mathematical heuristics.

Background: The Geometry of Efficiency

The "p-median" problem—finding $p$ locations to serve $n$ customers most efficiently—has roots going back to Pierre de Fermat in the 17th century. In modern terms, it’s the backbone of urban design. However, as the number of facilities increases, the "search space" for the optimal location on a continuous plane becomes infinite, making it a nightmare for traditional algorithms.

Why Algorithms Struggle Where Humans Shine

Most computer solvers reduce a continuous map to a discrete grid to save time. But what happens when the map includes "obnoxious" areas like lakes, rivers, or restricted zones?

• Algorithmic Blindness: Modeling every bridge and coastline into a Genetic Algorithm is data-exhausting.
• Human Intuition: Humans can glance at a map of a lake-filled region (like the Manicouagan Reservoir) and immediately "see" where clusters form.

Methodology: The SolveIt Framework

The researchers developed a three-layer architecture (Presentation, Logic, Data) to facilitate this "Human Intelligence Task."

System Architecture

The core innovation is the Configuration Collection Component, which tracks every move a player makes and updates the "Overall Distance" score in real-time.

Gamification Elements

To ensure high-quality contributions, SolveIt uses:

• Real-time Feedback: Players see their current score and rank instantly.
• Competition: A global scoreboard highlights the winners.
• The "Best State" Anchor: Players can jump back to their personal best configuration, encouraging risk-taking without the fear of losing progress.

Experiments: Crowd vs. Machines

The authors tested SolveIt against Genetic Algorithms (GA) (the gold standard) and the Cooper Method (a popular iterative heuristic).

Performance Metrics

The study used 40 students and 2 experts to solve 16 different problem configurations (e.g., C30F8: 30 customers, 8 facilities).

• Accuracy: The crowd consistently stayed within a 1.5% - 2% error rate relative to the GA gold standard.
• Superiority: As the problems grew more complex, SolveIt significantly outperformed the Cooper Method in total cost reduction.

Critical Insight: The Convergence of Play

Interestingly, the researchers tracked player behavior over time. Most players' "error rates" dropped sharply within the first few moves as they identified visual clusters. This suggests that the human brain effectively performs a "mental clustering" that approximates complex spatial division of labor much faster initiallly than a computer starting from a random distribution.

Limitations and Future Work

While SolveIt is powerful for small-to-medium datasets, the "visual clutter" of hundreds of facilities might overwhelm a human player. Future iterations could explore Hybrid AI-Human Systems, where a machine handles the bulk of the calculation while the human "nudges" facilities around complex geographic obstacles.

Conclusion

SolveIt proves that N-P Hard doesn't always have to mean "Human-Hard." By gamifying spatial optimization, we can solve critical infrastructure problems with the same engagement we bring to mobile games, turning "the crowd" into a massive, distributed computer for urban planning.