Approximate Stable Task Assignment With Coverage and Skill in Spatial Crowdsourcing

Spatial crowdsourcing (SC) aims to assign spatial tasks to mobile workers while balancing platform utility and matching stability. Existing studies typically focus on either utility maximization or strict stability, while often neglecting heterogeneous constraints such as workers' skills and spatial coverage. In this paper, we study the Approximate Stable Task Assignment with coverage and skill (ASTA) problem, which maximizes system utility under a relaxed stability constraint and is proven to be NP-hard. To address this problem, we propose a two-stage solution framework. In the first stage, we develop a Task-Driven Stability Construction (TDSC) algorithm to generate a feasible initial matching that satisfies stability requirements. In the second stage, we design two optimization algorithms. We first propose a Stability-Guided Revision (SGR) algorithm, which iteratively replaces matched workers with unmatched ones while maintaining stability. To address the limitation in the greedy nature of SGR, we further propose a Multi-Armed Bandit-based Adaptive Large Neighborhood Search (MAB-ALNS) algorithm, which adaptively selects destruction operators based on the Upper Confidence Bound (UCB) policy. We theoretically analyze the regret of the adaptive strategy and derive an upper bound. Finally, extensive experiments on one synthetic dataset and two real-world datasets demonstrate that our methods outperform baseline approaches.