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

Songhao Shen

doi:10.1111/itor.70134

2025-12-01

PRE

Songhao Shen

Zhibin Wu *

DOI：10.1111/itor.70134

原文链接

原文求助

摘要

En 中文

本文针对空间众包中的任务分配优化问题进行研究，重点关注城市管理和交通监控等应用场景，在这些场景中，工作者必须在严格的时间约束下沿预定义路线完成任务。我们将该挑战表述为带时间窗的多起点多终点团队导向问题，这是带时间窗的团队导向问题的扩展。所提出的模型考虑了多个工作者，且每个工作者具有不同的预定义起点和终点，并融入了任务特定的时窗限制。为解决这一NP难问题，我们提出了一种考虑相关性（correlation）的混合自适应邻域搜索算法（HANS-CC）。该元启发式算法的关键创新在于其相关性机制，该机制基于工作者可达任务集合的重叠情况识别工作者之间的关系。该机制有效剪枝了搜索空间，并引导邻域算子朝更优且可行的交换方向进行。通过在合成数据集和真实数据集上与基线方法（包括独立的禁忌搜索、简化的贪心算法变种以及领先的商业求解器）进行严格对比，评估了该算法的性能。计算结果表明，HANS-CC始终优于基线方法，尤其在商业求解器无法在合理时间内找到可行解的大规模实例中表现突出。这些发现验证了HANS-CC是解决此类具有挑战性的现实优化问题的一种稳健且可扩展的方法。

Keyword:

spatial crowdsourcing

task allocation

orienteering problem

meta-heuristic algorithm

crowdsensing