第15卷第6期 智能系统学报 Vol.15 No.6 2020年11月 CAAI Transactions on Intelligent Systems Nov.2020 D0L:10.11992tis.202006055 基于禁忌搜索的时空众包任务分配算法 潘庆先2，般增轩2，董红斌'，高照龙3，童向荣2 (1.哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001,2.烟台大学计算机与控制工程学院，山 东烟台264005,3.德拉萨大学达斯玛里纳斯校区科学与计算机学院，甲米地达斯玛里纳斯999005) 摘要：为了在时空众包任务分配过程中减少移动成本、缩短任务完成时间，本文将时空众包和路径规划问题 结合起来，提出了一种基于自适应阈值的禁忌搜索算法，该算法通过在线学习的方式，进行路径规划设计，计 算出每个任务合理的预估等待时间，匹配区域内的众包任务，并在最短的时间内完成任务。通过实验对比，本 文所提算法在任务耗费时间上平均比Adaptive RT算法降低I3%,比ASPT算法降低23.3%。在移动成本上比 Adaptive RT算法降低了6.99%.比ASPT算法降低了25.9%。 关键词：时空众包：任务分配；路径规划；禁忌搜索算法；自适应阈值：3类对象；服务质量；报酬 中图分类号：TP311文献标志码：A 文章编号：1673-4785(2020)06-1040-09 中文引用格式：潘庆先，殷增轩，董红斌，等.基于禁忌搜索的时空众包任务分配算法.智能系统学报，2020,15(6)： 1040-1048. 英文引用格式：PAN Qingxian,.YIN Zengxuan,DONG Hongbin,etal.Spatiotemporal crowdsourcing task assignment algorithm based on tabu search[Jl.CAAI transactions on intelligent systems,2020,15(6):1040-1048. Spatiotemporal crowdsourcing task assignment algorithm based on tabu search PAN Qingxian,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) Abstract:To reduce the moving cost and task completion time of the distribution process in a spatiotemporal crowd- sourcing 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 pa- per 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. Keywords:spatiotemporal crowdsourcing;task assignment;route planning;tabu search;adaptive threshold;three types of objects;service quality;reward 随着移动互联网的飞速发展，众包任务山开 模式一时空众包应运而生。VRP(vehicle route 始出现时间上和空间上的约束，一种新型的众包 planning)路径规划是一个经典问题，其目的是寻 找一条从起点到目标终点能满足各种时间、空间 收稿日期：2020-06-30. 基金项目：国家自然科学基金项目(60903098.61502140. 约束的行驶路线，与时空众包中的任务分配问题 61572418,61472095):黑龙江自然科学基金项目 具有很多相似性，因此本文考虑将两者结合起 (LH2020F023). 通信作者：殷增轩.E-mail:yzxytu@163.com 来，以解决任务分配问题。DOI: 10.11992/tis.202006055 基于禁忌搜索的时空众包任务分配算法 潘庆先1,2，殷增轩2 ，董红斌1 ，高照龙3 ，童向荣2 （1. 哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001; 2. 烟台大学 计算机与控制工程学院，山 东 烟台 264005; 3. 德拉萨大学达斯玛里纳斯校区 科学与计算机学院，甲米地 达斯玛里纳斯 999005） 摘 要：为了在时空众包任务分配过程中减少移动成本、缩短任务完成时间，本文将时空众包和路径规划问题 结合起来，提出了一种基于自适应阈值的禁忌搜索算法，该算法通过在线学习的方式，进行路径规划设计，计 算出每个任务合理的预估等待时间，匹配区域内的众包任务，并在最短的时间内完成任务。通过实验对比，本 文所提算法在任务耗费时间上平均比 Adaptive RT 算法降低 13%，比 ASPT 算法降低 23.3%。在移动成本上比 Adaptive RT 算法降低了 6.99%，比 ASPT 算法降低了 25.9%。 关键词：时空众包；任务分配；路径规划；禁忌搜索算法；自适应阈值；3 类对象；服务质量；报酬 中图分类号：TP311 文献标志码：A 文章编号：1673−4785(2020)06−1040−09 中文引用格式：潘庆先, 殷增轩, 董红斌, 等. 基于禁忌搜索的时空众包任务分配算法 [J]. 智能系统学报, 2020, 15(6): 1040–1048. 英文引用格式：PAN Qingxian, YIN Zengxuan, DONG Hongbin, et al. Spatiotemporal crowdsourcing task assignment algorithm based on tabu search[J]. CAAI transactions on intelligent systems, 2020, 15(6): 1040–1048. Spatiotemporal crowdsourcing task assignment algorithm based on tabu search PAN Qingxian1,2 ，YIN Zengxuan2 ，DONG Hongbin1 ，GAO Zhaolong3 ，TONG Xiangrong2 (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) Abstract: To reduce the moving cost and task completion time of the distribution process in a spatiotemporal crowd￾sourcing 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 pa￾per 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. Keywords: spatiotemporal crowdsourcing; task assignment; route planning; tabu search; adaptive threshold; three types of objects; service quality; reward 随着移动互联网的飞速发展，众包任务[1] 开 始出现时间上和空间上的约束，一种新型的众包 模式−时空众包应运而生。VRP(vehicle route planning) 路径规划是一个经典问题，其目的是寻 找一条从起点到目标终点能满足各种时间、空间 约束的行驶路线，与时空众包中的任务分配问题 具有很多相似性，因此本文考虑将两者结合起 来，以解决任务分配问题。 收稿日期：2020−06−30. 基金项目：国家自然科学基金项 目 (60903098， 61502140， 61572418， 61472095)；黑龙江自然科学基金项目 (LH2020F023). 通信作者：殷增轩.E-mail：yzxytu@163.com. 第 15 卷第 6 期 智 能 系 统 学 报 Vol.15 No.6 2020 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2020