Task Allocation in Spatial Crowdsourcing: An Efficient Geographic Partition Framework

Recent years have witnessed a revolution in Spatial Crowdsourcing (SC), in which people with mobile connectivity can perform spatio-temporal tasks that involve traveling to specified locations. In this paper, we identify and study in depth a new multi-center-based task allocation problem in the cont...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2024-09, Vol.36 (9), p.4943-4955
Main Authors: Zhao, Yan, Chen, Xuanlei, Ye, Guanyu, Guo, Fangda, Zheng, Kai, Zhou, Xiaofang
Format: Article
Language:English
Subjects:
Crowdsourcing
Geographic partition
Optimization
Partitioning algorithms
Reinforcement learning
Resource management
spatial crowdsourcing
task allocation
Task analysis
Training
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recent years have witnessed a revolution in Spatial Crowdsourcing (SC), in which people with mobile connectivity can perform spatio-temporal tasks that involve traveling to specified locations. In this paper, we identify and study in depth a new multi-center-based task allocation problem in the context of SC, where multiple allocation centers exist. In particular, we aim to maximize the total number of the allocated tasks while minimizing the allocated task number difference. To solve the problem, we propose a two-phase framework, called Task Allocation with Geographic Partition, consisting of a geographic partition and a task allocation phase. The first phase divides the whole study area based on the allocation centers by using both a basic Voronoi diagram-based algorithm and an adaptive weighted Voronoi diagram-based algorithm. In the allocation phase, we utilize a Reinforcement Learning method to achieve the task allocation, where a graph neural network with the attention mechanism is used to learn the embeddings of allocation centers, delivery points, and workers. To further improve the efficiency, we propose an early stopping optimization strategy for the adaptive weighted Voronoi diagram-based algorithm in the geographic partition phase and give a distance-constrained graph pruning strategy for the Reinforcement Learning method in the task allocation phase. Extensive experiments give insight into the effectiveness and efficiency of the proposed solutions.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2024.3374086