Trajectory-aware Task Coalition Assignment in Spatial Crowdsourcing

Page view(s)
5
Checked on Feb 15, 2025
Trajectory-aware Task Coalition Assignment in Spatial Crowdsourcing
Title:
Trajectory-aware Task Coalition Assignment in Spatial Crowdsourcing
Journal Title:
IEEE Transactions on Knowledge and Data Engineering
Keywords:
Publication Date:
06 December 2023
Citation:
Xie, Y., Wu, F., Zhou, X., Luo, W., Yin, Y., Zimmermann, R., Li, K., & Li, K. (2024). Trajectory-aware Task Coalition Assignment in Spatial Crowdsourcing. IEEE Transactions on Knowledge and Data Engineering, 1–15. https://doi.org/10.1109/tkde.2023.3336642
Abstract:
With the popularity of GPS-equipped smart devices, spatial crowdsourcing (SC) techniques have attracted growing attention in both academia and industry. A fundamental problem in SC is assigning location-based tasks to workers under spatial-temporal constraints. In many real-life applications, workers choose tasks on the basis of their preferred trajectories. However, by 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. For tackling the TCA problem, we develop a batch-based three-stage framework consisting of task grouping, planning, and assignment. First, we design greedy and spanning grouping approaches to generate task coalitions. Second, to gain candidate task coalitions for each worker efficiently, we design task-based and trajectory-based pruning strategies to reduce the search space. Furthermore, a 2-approximate algorithm, termed MST-Euler, is proposed to obtain a route among each worker and task coalition with a minimal detour cost. Third, the MST-Euler Greedy (MEG) algorithm is presented to compute an assignment that results in the maximal number of tasks assigned and a parallel strategy is introduced to boost its efficiency. Extensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed algorithms.
License type:
Publisher Copyright
Funding Info:
The research is partially funded by the National Key R&D Program of China, the Creative Research Groups Program of the National Natural Science Foundation of China, and the Programs of NSFC.

The research is also partially funded by Natural Science Foundation of Hunan Province.

This research is in part supported by the Singapore Ministry of Education Academic Research Fund Tier 2
Description:
© 2023 IEEE.  Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
ISSN:
1041-4347
1558-2191
2326-3865
Files uploaded:

File Size Format Action
tkde-main.pdf 5.85 MB PDF Open