关键词: 众包, 空间众包, 任务分配, 定向问题, 混合整数规划, 禁忌搜索

Abstract: With the development of mobile internet, spatial crowdsourcing has become a highly regarded business model. In spatial crowdsourcing, there is a category of crowd workers with their preplanned destinations. Assigning tasks to these workers with destination autonomy can not only reduce task completion costs but also make full use of workers’ idle time and resources. However, compared to traditional spatial crowdsourcing workers, these workers have a significantly different range of tasks they can accept. Therefore, how to effectively assign tasks to these workers poses a challenging problem.
This article discusses the spatial crowdsourcing task assignment problem considering workers’ planned destinations and proposes a mathematical model based on mixed integer programming. Firstly, the problem scenario and relevant concepts are described, and modeled as a graph theory problem. Then, the basic model for the task assignment problem is established, including decision variables, constraints, and an objective function. The model aims to maximize the total number of completed tasks while considering time window constraints and aconstraint of not exceeding the latest arrival time at the destination.
To improve the solver’s speed, a necessary condition is proven to narrow down the search space for solving. Furthermore, to accommodate different types of spatial crowdsourcing task assignment problems, the scalability and practicality of the model are explored. It is suggested that the model can be adapted to other types of spatial crowdsourcing task assignment problems by adjusting the constraints or objective function. Two optimization strategies are discussed as model improvements: optimizing task assignment based on worker travel costs and optimizing task assignment based on redundant tasks. For the first strategy, a two-stage approach can be used to solve the model. For the second strategy, task service constraints can be relaxed in the model.
Then, to address large-scale scenarios, a heuristic algorithm based on tabu search is designed. The algorithm uses random insertion for neighborhood operations and progressively improves solution quality through iterative searching and updating, aiming to obtain satisfactory solutions within a shorter time.
Finally, three instances are presented to test the proposed model and algorithm. These instances test the impact of conditions that improve the solver speed, the effects of using crowdsourcing workers versus hired workers on mileage, the performance and speed of the proposed search algorithm in large-scale environments, and the influence of the number of workers on task completion rate. The experiments reveal that using appropriately crowdsourcing workers with planned destinations significantly reduces travel distances compared to employing hired workers. This indicates that crowdsourcing workers with planned destinations can greatly reduce travel distances, leading to reduced carbon emissions and consumption of non-renewable resources from a social welfare perspective. From a business standpoint, reduced distances generally correspond to lower costs, and the additional mileage traveled by crowdsourcing workers can serve as a basis for task pricing.
In conclusion, the proposed mathematical model for spatial crowdsourcing task assignment considering workers’ planned destinations has both theoretical and practical value. Future research can further explore methods to improve the computational efficiency and accuracy of this model to adapt to a wider range of spatial crowdsourcing scenarios.

Key words: crowdsourcing, spatial crowdsourcing, task allocation, orienteering problem, mixed integer programming, tabu search