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

Spatiotemporal crowdsourcing task assignment algorithm based on tabu search

作　　者：潘庆先 殷增轩 董红斌[1] 高照龙 童向荣 PAN Qingxian;YIN Zengxuan;DONG Hongbin;GAO Zhaolong;TONG Xiangrong(College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China;College of Computer and Control Engineering,Yantai University,Yantai 264005,China;College of Science and Computer Studies,DE la Salle University-Dasmarinas,Dasmarinas 999005,Philippines)

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

出　　处：《智能系统学报》2020年第6期1040-1048,共9页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学基金项目(60903098,61502140,61572418,61472095);黑龙江自然科学基金项目(LH2020F023).

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]