软件学报

作者：王府鑫，王宁，曾奇雄

单位：王府鑫，北京交通大学 计算机与信息技术学院, 北京 100044;交通数据分析与挖掘北京市重点实验室 (北京交通大学), 北京 10004411,王宁，北京交通大学 计算机与信息技术学院, 北京 100044;交通数据分析与挖掘北京市重点实验室 (北京交通大学), 北京 10004402,曾奇雄，北京交通大学 计算机与信息技术学院, 北京 100044;交通数据分析与挖掘北京市重点实验室 (北京交通大学), 北京 10004403

关键词：时空众包;任务分配;张量分解;偏好预测

基金：国家重点研发计划(2018YFC0809800)

近年来, 随着移动设备的计算能力和感知能力的提高, 基于位置信息的时空众包应运而生, 任务分配效果的提升面临许多挑战, 其中之一便是如何给工人分配他们真正感兴趣的任务. 现有的研究方法只关注工人的时间偏好而忽略了空间因素对偏好的影响, 仅关注长期偏好却忽略了短期偏好, 同时面临历史数据稀疏导致的预测不准的问题. 研究基于长短期时空偏好的任务分配问题, 从长期和短期两个角度以及时间和空间两个维度全面考虑工人的偏好, 进行时空众包任务分配, 提高任务的成功分配率和完成效率. 为提升时空偏好预测的准确性, 提出分片填充的张量分解算法(SICTD)减小偏好张量的空缺值占比, 提出时空约束下的ST-HITS算法, 综合考虑工人短期活跃范围, 计算短期时空偏好. 为了在众包任务分配中最大化任务总收益和工人偏好, 设计基于时空偏好的贪心与Kuhn-Munkres (KM)算法, 优化任务分配的结果. 在真实数据集上的大量实验结果表明, 提出的分片填补张量分解算法对时间和空间偏好的RMSE预测误差较基线算法分别下降22.55%和24.17%; 在任务分配方面, 提出的基于偏好的KM算法表现出色, 对比基线算法, 在工人总收益和工人完成任务平均偏好值上分别提升40.86%和22.40%.

来源：2024年第10期

《软件学报》期刊编辑部

查看软件学报杂志2024年第10期