Lune

ICDE2024Top-tier venue

Cross Online Assignment of Hybrid Task in Spatial Crowdsourcing

Zhao Liu, Guoqing Xiao, Xu Zhou, Yunchuan Qin, Yunjun Gao, Kenli Li

Abstract

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.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Efficient Cross Dynamic Task Assignment in Spatial CrowdsourcingTianyue Ren, Xu Zhou, Kenli Li, Yunjun Gao et al.ICDE 2023 · 23 citations
  2. Batch-Based Cooperative Task Assignment in Spatial CrowdsourcingYi Yang, Yurong Cheng, Yeru Yang, Ye Yuan et al.ICDE 2023 · 21 citations
  3. Real-Time Cross Online Matching in Spatial CrowdsourcingYurong Cheng, Boyang Li, Xiangmin Zhou, Ye Yuan et al.ICDE 2020 · 66 citations
  4. Fair Task Assignment in Spatial CrowdsourcingZhao Chen, Peng Cheng, Lei Chen, Xuemin Lin et al.VLDB 2020 · 60 citations
  5. Bilateral Preference-aware Task Assignment in Spatial CrowdsourcingXu Zhou, Shiting Liang, Kenli Li, Yunjun Gao et al.ICDE 2022 · 24 citations
Dusk over the sea between two cliffs drawn in fine vertical lines