空间众包中隔离敏感的任务匹配算法

来源：计算机工程与应用杂志2024年第17期北京时间：

作者：刘俊岭, 高新宇, 孙焕良, 许景科

单位：1.沈阳建筑大学 计算机科学与工程学院，沈阳 110168；2.辽宁省城市建设大数据管理与分析重点实验室，沈阳 110168；3.国家特种计算机工程技术研究中心沈阳分中心，沈阳 110168

摘要：随着移动互联网接入普及和共享经济的增长，空间众包平台得到广泛普及。存在一类众包应用尽量使得众包任务在空间局部范围内完成，即在执行空间任务时减少人员在空间区域间的流动。基于此需求，提出了空间隔离敏感的任务匹配问题，给定具有所属空间区域位置的工人集和任务集，在所有任务均可完成的前提下，使得所有匹配任务的工人移动所产生的跨区域代价之和最小。在线平台中高效的空间隔离敏感的任务匹配算法是研究目标。提出了基于空间层次合并分组的匹配算法，将分布在空间区域中的任务与工人转换到区域邻接图节点，提出了[δ]-clique概念用于将区域节点分组，对分组的节点进行整体匹配，较大程度上提高了匹配算法的效率。在真实数据集上进行充分对比实验，结果表明，与现有的算法相比提出的空间层次合并分组的匹配算法在跨区域代价方面平均减少近16%，在匹配效率方面平均提升近5倍，验证了所提出算法的有效性。

关键词：空间众包,区域划分,跨区域代价,KM算法