Abstract
In Spatial Crowdsourcing (SC) systems, mobile users are enabled to perform spatio-temporal tasks by physically traveling to specified locations with the SC platforms. SC platforms manage the systems and recruit mobile users to contribute to the SC systems, whose commercial success depends on the profit attained from the task requesters. In order to maximize its profit, an SC platform needs an online management mechanism to assign the tasks to suitable workers. How to assign the tasks to workers more cost-effectively with the spatio-temporal constraints is one of the most difficult problems in SC. To deal with this challenge, we propose a novel Profit-driven Task Assignment (PTA) problem, which aims to maximize the profit of the platform. Specifically, we first establish a task reward pricing model with tasks' temporal constraints (i.e., expected completion time and deadline). Then we adopt an optimal algorithm based on tree decomposition to achieve the optimal task assignment and propose greedy algorithms to improve the computational efficiency. Finally, we conduct extensive experiments using real and synthetic datasets, verifying the practicability of our proposed methods.
Introduction
Spatial Crowdsourcing (SC) platforms, such as Uber or DoorDash, rely on mobile workers to perform location-based tasks. Traditionally, research in this field has focused on maximizing the number of completed tasks or minimizing worker travel distance. However, in a commercial setting, a platform’s success depends on profit.
Existing models often ignore the platform's bottom line or fail to account for the complex spatio-temporal constraints of real-world tasks—specifically, that a task's value often decreases the longer it takes to complete. The challenge lies in assigning the right workers to the right tasks to maximize total profit while dealing with an NP-hard optimization problem.
Methodology
The researchers tackle the Profit-driven Task Assignment (PTA) problem through three main components:
- Reward Pricing Model: They established a model where a task has an "expected completion time" ($s.e$) and a "deadline" ($s.d$). If a task is finished by $s.e$, the platform receives the maximum reward. If it finishes between $s.e$ and $s.d$, the reward decays linearly based on a penalty rate ($s.pr$). After the deadline, the reward is zero.
- Optimal Task Assignment (OTA): To find the theoretical maximum profit, the authors utilize an exact algorithm based on tree decomposition. While guaranteed to find the best solution, this method is computationally expensive and does not scale well to large numbers of tasks.
- GTA-RTO (Greedy Task Assignment with Random Tuning Optimization): This is the paper's primary algorithmic contribution. It works in three stages: a basic greedy assignment (GTA), a coarse tuning (CT) step that abandons low-value tasks to free up workers, and a fine-tuning (FT) step that reassigns workers within groups to find more efficient arrangements.
Key Results and Insights
The authors evaluated their approach using the real-world gMission dataset and various synthetic datasets to test scalability.
- The "Shortest Distance" Trap: Simply assigning the nearest worker to a task is often sub-optimal for profit. A nearby worker might be better "saved" for a high-value task appearing elsewhere, or their travel time might still result in a heavy delay penalty.
- Profit vs. Completion: Maximizing the number of tasks completed does not always maximize profit. Sometimes, it is more profitable to ignore a difficult, low-reward task to ensure high-value tasks are completed before their penalty window begins.
- Scalability and Performance: The proposed GTA-RTO algorithm improved total platform profit by up to 25.56% compared to standard greedy approaches. While the exact OTA algorithm struggled to return results once the number of tasks exceeded 400, GTA-RTO handled thousands of tasks in seconds while maintaining near-optimal profit ratios.
Conclusion
By shifting the focus from simple task completion to profit maximization, this research provides a more commercially viable framework for spatial crowdsourcing. The GTA-RTO algorithm offers a practical balance between computational efficiency and profit optimization, making it suitable for real-time applications in dynamic environments.
Summary updated