[1]潘庆先,殷增轩,董红斌,等.基于禁忌搜索的时空众包任务分配算法[J].智能系统学报,2020,15(6):1040-1048.[doi:10.11992/tis.202006055]
 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.[doi:10.11992/tis.202006055]
点击复制

基于禁忌搜索的时空众包任务分配算法(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第15卷
期数:
2020年6期
页码:
1040-1048
栏目:
学术论文—智能系统
出版日期:
2020-11-05

文章信息/Info

Title:
Spatiotemporal crowdsourcing task assignment algorithm based on tabu search
作者:
潘庆先12 殷增轩2 董红斌1 高照龙3 童向荣2
1. 哈尔滨工程大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001;
2. 烟台大学 计算机与控制工程学院, 山东 烟台 264005;
3. 德拉萨大学达斯玛里纳斯校区 科学与计算机学院, 甲米地 达斯玛里纳斯 999005
Author(s):
PAN Qingxian12 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
关键词:
时空众包任务分配路径规划禁忌搜索算法自适应阈值3类对象服务质量报酬
Keywords:
spatiotemporal crowdsourcingtask assignmentroute planningtabu searchadaptive thresholdthree types of objectsservice qualityreward
分类号:
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.

参考文献/References:

[1] LAW E, VON AHN L. Human computation[J]. Synthesis lectures on artificial intelligence and machine learning, 2011, 5(3): 1-121.
[2] 童咏昕, 袁野, 成雨蓉, 等. 时空众包数据管理技术研究综述[J]. 软件学报, 2017, 28(1): 35-58
TONG Yongxin, YUAN Ye, CHENG Yurong, et al. Survey on spatiotemporal crowdsourced data management techniques[J]. Journal of software, 2017, 28(1): 35-58
[3] 刘辉. 时空众包环境下在线任务分配策略的研究[D]. 济南: 山东建筑大学, 2018.
LIU Hui. Research of online task allocation strategy in spatio-temporal crowdsourcing environment[D]. Jinan: Shandong Jianzhu University, 2018.
[4] KAZEMI L, SHAHABI C. Geocrowd: enabling query answering with spatial crowdsourcing[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, USA, 2012: 189-199.
[5] TONG Yongxin, SHE Jieying, DING Bolin, et al. Online mobile micro-task allocation in spatial crowdsourcing[C]//2016 IEEE 32nd International Conference on Data Engineering (ICDE). Helsinki, Finland, 2016: 49-60.
[6] LI Yu, YIU M L, XU Wenjian. Oriented online route recommendation for spatial crowdsourcing task workers[C]//Proceedings of the 14th International Symposium on Spatial and Temporal Databases. Hong Kong, China, 2015: 137-156.
[7] LI Guoliang, WANG Jiannan, ZHENG Yudian, et al. Crowdsourced data management: a survey[J]. IEEE transactions on knowledge and data engineering, 2016, 28(9): 2296-2319.
[8] PAN Qingxian, DONG Hongbin, WANG Yingjie, et al. Recommendation of crowdsourcing tasks based on word2vec semantic tags[J]. Wireless communications and mobile computing, 2019, 2019: 2121850.
[9] BOUTSIS I, KALOGERAKI V. On task assignment for real-time reliable crowdsourcing[C]//2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS). Madrid, Spain, 2014: 1-10.
[10] 宋天舒, 童咏昕, 王立斌, 等. 空间众包环境下的3类对象在线任务分配[J]. 软件学报, 2017, 28(3): 611-630
SONG Tianshu, TONG Yongxin, WANG Libin, et al. Online task assignment for three types of objects under spatial crowdsourcing environment[J]. Journal of software, 2017, 28(3): 611-630
[11] 刘辉, 李盛恩. 时空众包环境下基于统计预测的自适应阈值算法[J]. 计算机应用, 2018, 38(2): 415-420
LIU Hui, LI Shengen. Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment[J]. Journal of computer applications, 2018, 38(2): 415-420
[12] HASSAN U U, CURRY E. Efficient task assignment for spatial crowdsourcing: a combinatorial fractional optimization approach with semi-bandit learning[J]. Expert systems with applications, 2016, 58: 36-56.
[13] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W. H. Freeman & Co., 1979: 79-87.
[14] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management science, 1959, 6(1): 80-91.
[15] 毕国通. 车辆路径问题及其优化算法研究综述[J]. 物流科技, 2016, 39(6): 95-97
BI Guotong. The review of vehicle routing problem and its optimization algorithm[J]. Logistics sci-tech, 2016, 39(6): 95-97
[16] 苏畅, 徒君. 一种自适应最大最小蚁群算法[J]. 模式识别与人工智能, 2007, 20(5): 688-691
SU Chang, TU Jun. An adaptive max-min ant colony algorithm[J]. Pattern recognition and artificial intelligence, 2007, 20(5): 688-691
[17] BAI Jie, YANG Genke, CHEN Yuwang, et al. A model induced max-min ant colony optimization for asymmetric traveling salesman problem[J]. Applied soft computing, 2013, 13(3): 1365-1375.
[18] YU Jiapeng, WANG Chengen. A max-min ant colony system for assembly sequence planning[J]. The international journal of advanced manufacturing technology, 2013, 67(9/10/11/12): 2819-2835.
[19] REN Chunyu. Solving min-max vehicle routing problem[J]. Journal of software, 2011, 6(9): 1851-1856.
[20] 李阳, 李文芳, 马骊, 等. 混合退火算法求解旅行商问题[J]. 计算机应用, 2014, 34(S1): 110-113
LI Yang, LI Wenfang, MA Li, et al. Hybrid annealing algorithm for solving travellling salesman problem[J]. Journal of computer applications, 2014, 34(S1): 110-113
[21] 刘霞, 齐欢. 最小-最大车辆路径问题的禁忌搜索算法[J]. 系统工程, 2007, 25(1): 49-52
LIU Xia, QI Huan. Tabu search algorithm of min-max vehicle routing problems[J]. Systems engineering, 2007, 25(1): 49-52
[22] 刘霞, 杨超. 最小-最大车辆路径问题的蚁群算法[J]. 解放军理工大学学报(自然科学版), 2012, 13(3): 336-341
LIU Xia, YANG Chao. Min-max vehicle routing problem based on ant colony algorithm[J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2012, 13(3): 336-341
[23] 苏欣欣, 秦虎, 王恺. 禁忌搜索算法求解带时间窗和多配送人员的车辆路径问题[J]. 重庆师范大学学报 (自然科学版), 2020, 37(1): 22-30
SU Xinxin, QIN Hu, WANG Kai. Tabu search algorithm for the vehicle routing problem with time windows and multiple deliverymen[J]. Journal of Chongqing Normal University (Natural Science Edition), 2020, 37(1): 22-30
[24] PAN Qingxian, PAN Tingwei, DONG Hongbin, et al. An online task assignment based on quality constraint for spatio-temporal crowdsourcing[J]. IEEE access, 2019, 7: 170292-170303.
[25] CHEN Zhao, FU Rui, ZHAO Ziyuan, et al. gMission: a general spatial crowdsourcing platform[J]. Proceedings of the VLDB endowment, 2014, 7(13): 1629 -1632.

相似文献/References:

[1]郭红康,赵军.基于多Agent的面向订单的离散制造系统建模与仿真研究[J].智能系统学报,2016,11(2):233.[doi:10.11992/tis.201506008]
 GUO Hongkang,ZHAO Jun.Modeling and simulation of order-oriented discrete manufacturing system based on multi-Agent[J].CAAI Transactions on Intelligent Systems,2016,11(6):233.[doi:10.11992/tis.201506008]
[2]肖人彬,王英聪.一种面向时间分配问题的群智能劳动分工新方法[J].智能系统学报,2019,14(3):438.[doi:10.11992/tis.201807014]
 XIAO Renbin,WANG Yingcong.A new approach to labor division in swarm intelligence for time allocation problem[J].CAAI Transactions on Intelligent Systems,2019,14(6):438.[doi:10.11992/tis.201807014]
[3]齐小刚,李博,范英盛,等.多约束下多无人机的任务规划研究综述[J].智能系统学报,2020,15(2):204.[doi:10.11992/tis.201811018]
 QI Xiaogang,LI Bo,FAN Yingsheng,et al.A survey of mission planning on UAVs systems based on multiple constraints[J].CAAI Transactions on Intelligent Systems,2020,15(6):204.[doi:10.11992/tis.201811018]
[4]吴虎胜,肖人彬.群智能新研究:角色?匹配的狼群劳动分工[J].智能系统学报,2021,16(1):125.[doi:10.11992/tis.202007043]
 WU Husheng,XIAO Renbin.A new approach to swarm intelligence: role-matching labor division of a wolf pack[J].CAAI Transactions on Intelligent Systems,2021,16(6):125.[doi:10.11992/tis.202007043]

备注/Memo

备注/Memo:
收稿日期:2020-06-30。
基金项目:国家自然科学基金项目(60903098,61502140,61572418,61472095);黑龙江自然科学基金项目(LH2020F023)
作者简介:潘庆先,副教授,博士研究生,主要研究方向为人工智能和机器学习;殷增轩,硕士研究生,主要研究方向为人工智能和机器学习;董红斌,教授,博士生导师,博士,中国计算机学会高级会员,主要研究方向为机器学习、人工智能、多智能体系统和数据挖掘。主持或参加国家级和省部级项目5项,其中,国家级3项,省级2项,曾获黑龙江省高校科学技术奖、黑龙江省优秀高等教育科学成果奖。发表学术论文90余篇,出版专著1部,主编教材2部
通讯作者:殷增轩.E-mail:yzxytu@163.com
更新日期/Last Update: 2020-12-25