Cross Online Assignment of Hybrid Task in Spatial Crowdsourcing

Task assignment is a fundamental problem in spatial crowdsourcing. In many spatial crowdsourcing platforms, such as Didi, AMAP, and Uber, there are hybrid tasks, including real-time and reservation-type tasks, which are with different constraints and unevenly distributed in spatial and temporal. For these hybrid tasks, most existing studies suffer from low task completion rate and low profit for two reasons: firstly, they focus on homogeneous tasks with uniform constraints, and assign hybrid tasks separately; secondly, they cannot effectively address the uneven distribution of hybrid tasks. Inspired by this, we delve into the problem of online hybrid task assignment (HyTAO) with the goal of maximizing total revenue by simultaneously assigning both real-time and reservation-type tasks online for the first time. We prove the NP-hardness of the offline version of the HyTAO problem. To solve HyTAO effectively, we utilize a cross-platform cooperation model to tackle the challenge of non-uniform distribution. Following this, we design a binary tree-based search algorithm, namely BTS, which is capable of uniformly processing various types of tasks and quickly searching for available workers. Additionally, we discuss the parallel optimization strategies of BTS. To further enhance performance, we develop TBTS, which identifies tasks with high increased revenue based on a threshold. Finally, we conduct a comprehensive analysis of the complexity and competitive ratio of both BTS and TBTS. Extensive experiments are performed to demonstrate the efficiency of our approaches.