Abstract: Concerning the problem that in the research of spatial crowdsourcing task allocation, the benefits of multiple participants and the global optimization of continuous task allocation are not considered, which leads to the problem of poor allocation effect, an online task allocation algorithm was proposed for the global optimization of tripartite comprehensive benefit. Firstly, the distribution of crowdsourcing objects (crowdsourcing tasks and workers) in the next time stamp was predicted based on online random forest and gated recurrent unit network. Then, a bipartite graph model was constructed based on the situation of crowdsourcing objects in the current time stamp. Finally, the optimal matching algorithm of weighted bipartite graph was used to complete the task allocation. The experimental results show that the proposed algorithm realize the global optimization of continuous task allocation. Compared with greedy algorithm, this algorithm improves the success rate of task allocation by 25.7%, the average comprehensive benefit by 32.2% and the average opportunity cost of workers by 37.8%; compared with random threshold algorithm, the algorithm improves the success rate of task allocation by 27.4%, the average comprehensive benefit by 34.7% and the average opportunity cost of workers by 40.2%.

Key words: spatial crowdsourcing, predictive analysis, online random forest, KM (Kuhn-Munkres) algorithm

摘要： 针对时空众包任务分配研究中未考虑多方参与对象的效益和连续任务分配的全局优化，导致分配效果不佳的问题，提出一种面向三方综合效益全局优化的在线任务分配算法。首先，基于在线随机森林和门控循环单元网络预测出下一时间戳内众包对象（众包任务和工人）的分布情况，进而结合当前时间戳内众包对象的情况构造二分图模型，最后采用带权二分图最优匹配算法完成任务分配。实验结果证明了所提算法在连续任务分配过程中实现了综合效益的全局优化。与贪心算法对比，该算法在任务分配成功率方面提升25.7%，在平均综合效益方面提升32.2%，在工人平均机会成本方面提升37.8%；与随机阈值算法对比，该算法在任务分配成功率方面提升27.4%，在平均综合效益方面提升34.7%，在工人平均机会成本方面40.2%。

关键词: 时空众包, 预测分析, 在线随机森林, KM算法