A Two-Stage Genetic Algorithm based Task Allocation Approach for Dependency-aware Spatial Crowdsourcing

The widespread use of smart devices and efficient wireless network transmission has fostered the development of crowdsourcing systems, providing vast data for the advancement of digital twins and parallel intelligence. For a crowdsourcing system, the task allocation has been proven to have a crucial influence on the overall performance of the system. However, there are few previous works addressing the allocation of complex tasks, resulting in inadequate capacity for such tasks in crowd-sourcing systems. This paper aims to solve the allocation problem of complex tasks by dividing complex tasks into several subtasks with dependency relationships among them and employing a two-stage genetic algorithm to optimize the allocation of each subtask. Specifically, the optimization process contains two iterative stages : the subtask sequence optimization stage and the user-subtask matching optimization stage. The former stage uses the genetic algorithm to explore different subtask sequences, while the latter stage employs a sequential decision-making approach to assign appropriate users to each subtask based on the subtask sequence. To further improve the efficiency of user-subtask matching and obtain a better allocation scheme, we combine the tabu search algorithm and simulated annealing algorithm to form two variant algorithms: GA2S-TS and GA2S-SA. The experimental results verify the effectiveness of our proposed algorithms.