Maximizing Productivity in Spatial Crowdsourcing: The MTS Framework

TL;DR

In the world of spatial crowdsourcing (e.g., Gigwalk, TaskRabbit), workers often choose their own tasks. This paper formalizes the Maximum Task Scheduling (MTS) problem: how can a worker plan a route to finish the maximum number of tasks given that each task has a specific location and a ticking clock? The authors prove this is NP-hard and offer a "Progressive Algorithm" that gives workers the best of both worlds—instant responses and optimized long-term plans.

The Core Challenge: Why is MTS Hard?

Most job scheduling problems assume that "setup time" is constant. In spatial crowdsourcing, the "setup time" is the travel cost, which changes depending on where you are coming from. This sequence-dependency, combined with task expiration times, transforms a simple list into a complex combinatorial explosion.

Existing Server-Assigned Task (SAT) models assume a central authority knows everyone’s location, which is a privacy nightmare. The Worker Selected Tasks (WST) mode studied here respects worker privacy but shifts the computational burden of optimization to the worker's mobile device.

Methodology: From Exact to Heuristic

The authors approach the problem through three lens:

1. Exact Algorithms: They developed a specialized Branch-and-Bound (B&B) algorithm. By calculating a "Candidate Task Set" for each branch (filtering tasks that are already unreachable), they can prune massive sections of the search tree.
2. Beam Search Heuristic (BSH): To handle larger task sets, BSH keeps only the $k$ most promising partial sequences (the "beam width") at each step, preventing the exponential growth of calculations.
3. The Progressive Paradigm: This is the paper's "Aha!" moment. An approximation algorithm (like Nearest Neighbor) picks the first task immediately so the worker can start moving. While the worker is walking, the phone calculates the optimal schedule for the remaining tasks in the background.

Figure 1: Comparison of scheduling flows between different modes.

Experimental Insights

The researchers didn't just stay in the lab; they tested using real-world data from Yelp (Phoenix/Mesa) and Gowalla.

• The Mobile Bottleneck: On an Android device, the B&B algorithm took over a minute for just 20 tasks in dense areas—totally impractical for a snappy mobile app.
• The Heuristic Hero: The Nearest Neighbor Heuristic (NNH) performed surprisingly well for quick-and-dirty scheduling, but BSH was more stable across skewed data distributions.
• Preemption Risk: A key contribution is the Guided-Pro model. If other workers are likely to "steal" tasks while your phone is calculating in the background, the system intelligently reverts to a simpler, faster heuristic to lock in tasks immediately.

Figure 2: Performance comparison showing the exponential rise of exact algorithms vs. the efficiency of BSH.

Critical Analysis & Conclusion

The Progressive Algorithm is a brilliant application of "latency hiding." By acknowledging that a human worker takes minutes to reach a location, the authors reclaim that time for heavy-duty computation.

Limitations: The model currently assumes travel costs are static. In a city like Los Angeles, traffic is a dynamic variable that could invalidate a schedule mid-trip. Future work adding real-time traffic data would make this even more robust.

Final Takeaway: This work bridges the gap between high-level combinatorial optimization and the practical constraints of mobile computing, providing a blueprint for the next generation of "gig economy" apps.