Optimizing Dynamic Task Assignment in Spatial Crowdsourcing: Bilateral Preference-Aware Approaches

Task assignment is a crucial challenge in spatial crowdsourcing (SC). Most existing studies have two limitations: Firstly, only one-sided preferences of workers or tasks are taken into account, and the satisfaction of workers or tasks could be improved; Secondly, tasks are always assigned based on the current locations of workers, which is not suitable for many real-life applications, such as carpooling, where the trajectories of workers require to be taken into account. To this end, we investigate a new problem of <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</u>ilateral Preference-aware <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</u>ynamic <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</u>ask <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</u>ssignment (BDTA), which is proven to be NP-hard, to maximize overall satisfaction by incorporating worker-task bilateral preferences and assigns tasks using the trajectories of workers. For the BDTA problem, we first propose a hybrid batch processing framework to address uneven data distribution. After that, a task-initiated bidirectional select algorithm is proposed to mitigates the impact of task order on the matching results. Furthermore, we propose an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\alpha$</tex-math></inline-formula>-approximate task-initiated generalized deferred-acceptance algorithm and a reverse generalized deferred-acceptance algorithm to enhance the stability and overall satisfaction of task assignment results. Extensive experiments are conducted on both real and synthetic datasets to validate the effectiveness and efficiency of the proposed algorithms.