Trajectory-Aware Task Coalition Assignment in Spatial Crowdsourcing
- 29 November 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 36 (11) , 7201-7216
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.Keywords
Funding Information
- National Key R&D Program of China (2021ZD40303)
- National Natural Science Foundation of China (62321003)
- Programs of NSFC (62172146)
- Natural Science Foundation of Hunan Province (2022JJ30009, 2023JJ10016, 2023JJ30083)
- Singapore Ministry of Education Academic Research Fund Tier 2 (T2EP20221-0023)
This publication has 51 references indexed in Scilit:
- Satisfaction-aware Task Assignment in Spatial CrowdsourcingInformation Sciences, 2022
- Multi-stage complex task assignment in spatial crowdsourcingInformation Sciences, 2022
- Spatial crowdsourcing: a surveyThe VLDB Journal, 2019
- Online delivery route recommendation in spatial crowdsourcingWorld Wide Web, 2018
- Online mobile Micro-Task Allocation in spatial crowdsourcing2016
- T-share: A large-scale dynamic taxi ridesharing service2013
- In-Route Nearest Neighbor QueriesGeoInformatica, 2005
- The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms4OR, 2003
- Approximation Algorithms2003
- The budgeted maximum coverage problemInformation Processing Letters, 1999