Trajectory-Aware Task Coalition Assignment in Spatial Crowdsourcing (Extended Abstract)
Yuan Xie, Fan Wu, Xu Zhou, Wensheng Luo, Yifang Yin, Roger Zimmermann, Keqin Li, Kenli Li · 2024
With the popularity of GPS-equipped smart devices, spatial crowdsourcing (SC) techniques have attracted growing attention in both academia and industry. In existing trajectory-aware task assignment approaches, tasks assigned to a worker may be far apart from each other, resulting in a higher detour cost as the worker needs to deviate from the original trajectory more often than necessary. Motivated by the above observations, we investigate a trajectory-aware task coalition assignment (TCA) problem and prove it to be NP-hard. The goal is to maximize the number of assigned tasks by assigning task coalitions to workers based on their preferred trajectories. To tackle the TCA problem, we develop a batch-based three-stage framework consisting of task grouping, planning, and assignment. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed algorithms.