[1]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]
Copy

Spatiotemporal crowdsourcing task assignment algorithm based on tabu search

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 15 Number of periods: 2020 6 Page number: 1040-1048 Column: 学术论文—智能系统 Public date: 2020-11-05
Title:
Spatiotemporal crowdsourcing task assignment algorithm based on tabu search
Author(s):
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
Keywords:
spatiotemporal crowdsourcing; task assignment; route planning; tabu search; adaptive threshold; three types of objects; service quality; reward
CLC:
TP311
DOI:
10.11992/tis.202006055
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.
Similar References:

Memo

-

Last Update: 2020-12-25

Copyright © CAAI Transactions on Intelligent Systems