基于禁忌搜索的时空众包任务分配算法

PDF下载HTML

Title:

Spatiotemporal crowdsourcing task assignment algorithm based on tabu search

作者:

潘庆先^1,2, 殷增轩², 董红斌¹, 高照龙³, 童向荣²

1. 哈尔滨工程大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001;
2. 烟台大学 计算机与控制工程学院, 山东 烟台 264005;
3. 德拉萨大学达斯玛里纳斯校区 科学与计算机学院, 甲米地 达斯玛里纳斯 999005

Author(s):

PAN Qingxian^1,2, YIN Zengxuan², DONG Hongbin¹, GAO Zhaolong³, TONG Xiangrong²

1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China;
2. College of Computer and Control Engineering, Yantai University, Yantai 264005, China;
3. College of Science and Computer Studies, DE la Salle University-Dasmarinas, Dasmarinas 999005, Philippines

关键词:

时空众包; 任务分配; 路径规划; 禁忌搜索算法; 自适应阈值; 3类对象; 服务质量; 报酬

Keywords:

spatiotemporal crowdsourcing; task assignment; route planning; tabu search; adaptive threshold; three types of objects; service quality; reward

分类号:

TP311

DOI:

10.11992/tis.202006055

摘要:

为了在时空众包任务分配过程中减少移动成本、缩短任务完成时间，本文将时空众包和路径规划问题结合起来，提出了一种基于自适应阈值的禁忌搜索算法，该算法通过在线学习的方式，进行路径规划设计，计算出每个任务合理的预估等待时间，匹配区域内的众包任务，并在最短的时间内完成任务。通过实验对比，本文所提算法在任务耗费时间上平均比Adaptive RT算法降低13%，比ASPT算法降低23.3%。在移动成本上比Adaptive RT算法降低了6.99%，比ASPT算法降低了25.9%。

Abstract:

To reduce the moving cost and task completion time of the distribution process in a spatiotemporal crowdsourcing task, in this paper, by combining spatiotemporal crowdsourcing and path planning, a tabu search algorithm based on adaptive threshold is proposed. This algorithm uses online learning for path planning and designs a reasonable estimated waiting time for each task by matching crowdsourcing tasks in the area, thus, completing tasks in the shortest time. Through experimental comparison, we concluded that the average task time of the algorithm proposed in this paper is 13% and 23.3% lower than that of the Adaptive RT and ASPT algorithms, respectively, and the moving cost of the proposed algorithm is 6.99% and 25.9% lower than that of the Adaptive RT and ASPT algorithms, respectively.