科研之友
微信
新浪微博
Facebook
分享链接
摘要
任务调度问题是空间众包的核心问题之一。现有工作主要针对欧式空间中的个人任务，忽略了群组任务以及底层的路网信息，实用性有待提高。有鉴于此，本文研究路网场景下群组任务匹配和调度问题，提出了基于网格索引的群组任务匹配和调度算法框架。该框架由网格索引、搜索有效工人集算法和组建团队算法组成。该框架首先通过网格索引存储的路网信息和工人信息快速过滤掉不满足时间或预算约束的工人，避免大量无效的最短路径计算。然后利用基于剪枝策略的搜索算法搜索到满足任务约束的有效工人集。最后通过组建团队算法迭代地在有效工人集中选择最小成本覆盖比的工人加入团队完成任务。最后通过实验验证本文提出方法的有效性和高效性。
- 单位
