Multi‐start multi‐end team orienteering problem with time windows for task allocation in spatial crowdsourcing

Abstract This paper addresses the optimization of task allocation in spatial crowdsourcing, focusing on applications such as urban management and traffic monitoring, where workers must complete tasks along pre‐defined routes within strict time constraints. We formulate this challenge as the multi‐start multi‐end team orienteering problem with time windows, an extension of the team orienteering problem with time windows. The proposed model accommodates multiple workers with distinct, pre‐defined start and end points and incorporates task‐specific time windows. To address this NP‐hard problem, we propose a hybrid adaptive neighborhood search considering correlation (HANS‐CC) algorithm. A key innovation of this metaheuristic is its correlation mechanism, which identifies relationships between workers based on their overlapping sets of reachable tasks. This mechanism effectively prunes the search space and guides the neighborhood operators toward more promising and feasible exchanges. The algorithm's performance is rigorously evaluated against baseline methods, including a standalone Tabu search, a simplified greedy variant, and a leading commercial solver on both synthetic and real‐world datasets. Computational results demonstrate that HANS‐CC consistently outperforms the baselines, particularly for large‐scale instances where the commercial solver fails to find feasible solutions within a practical time limit. These findings validate HANS‐CC as a robust and scalable method for this challenging class of real‐world optimization problems.