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