Enhancing Spatial Crowdsourcing: A Decision Tree Approach to Multitask Assignment

TL;DR

In the booming sharing economy (Uber, Meituan, etc.), the efficiency of matching workers to tasks is paramount. This paper proposes a novel framework that moves beyond "one worker, one task" by using Location Entropy to identify urgent tasks and a Decision Tree to intelligently bundle multiple tasks for a single worker, significantly boosting income while slashing travel costs.

Problem & Motivation: The "Idle Worker" Dilemma

Spatial crowdsourcing relies on workers moving to specific physical locations to complete tasks. Typical algorithms assign one task at a time, but this often leaves workers idle or results in inefficient "detour" paths when new tasks appear nearby.

The challenge is balancing heterogeneous constraints:

• Spatial: Workers must be within a specific range.
• Temporal: Tasks have strict deadlines.
• Economic: Workers need a profit incentive to take on extra work, and platforms need to minimize total travel distances.

Authors notice that "popular" locations (high entropy) naturally attract workers, while remote areas (low entropy) are neglected. They argue that by prioritizing these "hard" tasks and then intelligently adding "along-the-way" tasks, they can optimize the entire system balance.

Methodology: Entropy Priority meets Hierarchical Filtering

1. Worker Selection via LEMP

The algorithm first calculates Location Entropy, which quantifies the probability of a task being completed based on historical worker patterns in that area.

• Insight: By assigning tasks in low-entropy areas first, the platform reduces the risk of task expiration.
• Distance Metric: The system uses Manhattan distance—the "taxicab geometry"—to find the closest worker for these priority tasks.

2. The Multitask Screening Decision Tree (MTADT)

Once a worker is on their way to a primary task, the MTADT algorithm filters potential secondary tasks using a four-layer decision process:

1. Time Difference: Can the worker reach the new task's start point before its deadline?
2. Travel Cost Ratio: Is the detour distance reasonable compared to the original trip?
3. Coincidence Rate of Route: How well does the new task align with the existing trajectory? This uses a Modified Hausdorff Distance (MHD) weighted by the cosine of the travel angle to ensure the worker isn't going in the opposite direction.
4. Income Growth Rate: Does the additional work actually result in a net profit for the worker after considering the "detour" discount?

Note: The system acts as a real-time filter, ensuring that only tasks beneficial to both the worker and the platform are assigned.

Experiments & Results: Real-World Feasibility

The researchers tested their approach against standard Greedy algorithms and pure MHD (Hausdorff) matching using both simulated data and real-world Uber NYC records.

• Travel Cost: MTADT showed a significantly lower growth in average travel cost as the number of tasks increased. This proves the "carpooling" effect is working—tasks are bundled so efficiently that the extra mileage is minimized.
• Efficiency: With a time complexity of $O(m+n)$, the algorithm is suitable for real-time applications, though it requires slightly more memory than simpler greedy approaches to maintain the decision tree state.

Comparison of MTADT, MHD, and Greedy algorithms across task sizes.

Critical Analysis & Conclusion

Takeaway

The core value of this work is the explicit modeling of worker profit within the assignment logic. By including an "Income Growth Rate" node in the decision tree, the algorithm ensures that multitasking is economically viable for the human element of the crowdsourcing loop.

Limitations & Future Work

One notable omission in the current methodology is predictive modeling. The current system reacts to tasks as they appear. The authors suggest that future iterations will incorporate SVM-based prediction to anticipate where tasks might appear, allowing the platform to "pre-position" workers in a proactive manner. Furthermore, extending this from "single-worker multitasks" to "multi-worker cooperative tasks" remains an open challenge.

In conclusion, the MTADT algorithm offers a scalable, logically transparent way to manage the complexities of modern spatial logistics, turning every "empty seat" or "empty trunk" into a potential profit center.