作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (9): 27-34,43. doi: 10.19678/j.issn.1000-3428.0057768

• 热点与综述 • 上一篇    下一篇

基于预测算法的在线空间众包任务分配策略

邢虎, 陈荣, 唐文君   

  1. 大连海事大学 信息科学与技术学院, 辽宁 大连 116026
  • 收稿日期:2020-03-17 修回日期:2020-04-21 发布日期:2020-04-21
  • 作者简介:邢虎(1995-),男,硕士研究生,主研方向为空间众包任务分配;陈荣(通信作者),教授、博士、博士生导师;唐文君,博士研究生。
  • 基金资助:
    国家自然科学基金(61672122);中央高校基本科研业务费专项资金(3132019355)。

Online Task Allocation Strategy for Spatial Crowdsourcing Based on Prediction Algorithm

XING Hu, CHEN Rong, TANG Wenjun   

  1. College of Information Science and Technology, Dalian Maritime University, Dalian, Liaoning 116026, China
  • Received:2020-03-17 Revised:2020-04-21 Published:2020-04-21

摘要: 根据空间众包任务类型的多样化特点,构建空间众包任务分配模型并提出基于预测算法的在线任务分配策略。在批处理模式下,将最大分数任务分配问题转化为寻找二分图最大权匹配问题,通过匈牙利算法对其进行求解得到每个时间片的最大分数,并利用预测算法使得工人在完成该任务后尽可能处于任务密集区域,避免出现工人没有合适任务可执行的情况发生,实现模型的最优在线任务分配。在滴滴快车数据集上的实验结果表明,与BASIC、LLEP和CDP策略相比,该策略在整个时间段内的总任务分配数量最多能提高10%,具有更高的任务分配效率与质量。

关键词: 空间众包, 任务分配, 预测算法, 匈牙利算法, 约束求解

Abstract: Based on the diversity of Spatial Crowdsourcing(SC) tasks,this paper constructs a task allocation model for SC,and proposes an online task allocation strategy based on the prediction algorithm.In the batch processing mode,the problem of Maximum Score Assignment(MSA) is transformed into the problem of searching for the maximum weighted bipartite graph matching.The Hungarian algorithm is used to solve the problem to obtain the maximum score of each time interval,and the prediction algorithm is used to ensure workers that have completed the task are in the task-intensive regions as far as possible,so the possibility of workers finding no suitable task to execute is reduced,and the optimal online task allocation of the model is implemented.Experimental results on the real dataset provided by Didi show that compared with the BASIC,LLEP and CDP strategies,the proposed strategy can improve the total number of task assignment in the whole time interval by up to 10%,and has a higher task allocation efficiency and quality.

Key words: Spatial Crowdsourcing(SC), task allocation, prediction algorithm, Hungarian algorithm, constraint solving

中图分类号: