摘要： 根据空间众包任务类型的多样化特点，构建空间众包任务分配模型并提出基于预测算法的在线任务分配策略。在批处理模式下，将最大分数任务分配问题转化为寻找二分图最大权匹配问题，通过匈牙利算法对其进行求解得到每个时间片的最大分数，并利用预测算法使得工人在完成该任务后尽可能处于任务密集区域，避免出现工人没有合适任务可执行的情况发生，实现模型的最优在线任务分配。在滴滴快车数据集上的实验结果表明，与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

中图分类号: 

• TP311