面向路网的空间众包群组任务匹配和调度算法  

Group Task Matching and Scheduling Algorithm in Spatial Crowdsourcing for Road Network

作　　者：钱勤红 刘安[1] 孙玉娥 QIAN Qin-hong;LIU An;SUN Yu-e(School of Computer Science and Technology,Soochow University,Suzhou 215006,China;School of Rail Transportation,Soochow University,Suzhou 215137,China)

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006 [2]苏州大学轨道交通学院,江苏苏州215137

出　　处：《小型微型计算机系统》2022年第3期490-497,共8页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61572336)资助;江苏高校优势学科建设工程资助项目(PAPD)资助。

摘　　要：任务调度问题是空间众包的核心问题之一.现有工作主要针对欧式空间中的个人任务,忽略了群组任务以及底层的路网信息,实用性有待提高.有鉴于此,本文研究路网场景下群组任务匹配和调度问题,提出了基于网格索引的群组任务匹配和调度算法框架.该框架由网格索引、搜索有效工人集算法和组建团队算法组成.该框架首先通过网格索引存储的路网信息和工人信息快速过滤掉不满足时间或预算约束的工人,避免大量无效的最短路径计算.然后利用基于剪枝策略的搜索算法搜索到满足任务约束的有效工人集.最后通过组建团队算法迭代地在有效工人集中选择最小成本覆盖比的工人加入团队完成任务.最后通过实验验证本文提出方法的有效性和高效性.Task scheduling problem is one of the core problems of spatial crowdsourcing.The existing work mainly focuses on individual tasks in European space,neglecting group tasks and the underlying road network information,so its practicability needs to be improved.In view of this,this paper studies the group task matching and scheduling problem based on road network,and proposes group task matching and scheduling based on gird index algorithm framework.The framework is composed of grid index,search effective worker set algorithm and team formulation algorithm.Firstly,the grid index is used to store the information of road network and worker,and the workers who do not meet the deadline or budget constraints are quickly filtered out to avoid a large number of invalid shortest path calculation.Then,an efficient set of workers satisfying the task constraints is found by using the search algorithm based on pruning strategy.Finally,the team formulation algorithm is used to select the workers with the minimum cost coverage ratio to join the team to complete the task iteratively.Finally,the effectiveness and efficiency of the proposed method are verified by experiments.

关 键 词：空间众包 任务调度 群组任务 网格索引 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]