摘要
空间众包用于解决带时空约束的线下众包任务,近几年得到了快速发展。任务调度是空间众包的重要研究方向,难点在于调度过程中任务和工作者的动态不确定性。为了高效地进行任务路径动态调度,提出了同时考虑任务和工作者的不确定性的空间众包任务路径动态调度方法,该方法进行了3方面的改进。首先,扩展了调度需要考虑的因素,除了考虑新增任务的时空属性不确定性之外,还考虑了新增工作者的交通方式和时空属性的不确定性。其次,对调度策略进行改进,通过使用聚合调度策略,对动态新增任务先进行聚合处理,随后再进行任务分配和路径优化,相比传统非聚合调度计算时间显著减少。最后,对调度算法进行改进,基于传统遗传算法,将任务分配和路径优化操作迭代进行,相比先进行任务分配再进行路径优化的调度算法,提高了获取最优结果的准确性。此外,文中设计并实现了基于真实地图导航的空间众包任务路径动态调度模拟平台,并基于该平台验证了所提方法的有效性。
Space crowdsourcing is used to solve offline crowdsourcing tasks with time and space constraints,and it has developed rapidly in recent years.Task scheduling is an important research direction of space crowdsourcing.The difficulty lies in the dynamic uncertainty of tasks and workers in the scheduling process.In order to efficiently perform task scheduling,a dynamic task scheduling method for space crowdsourcing that considers the uncertainty of tasks and workers at the same time is proposed.The method has been improved in three aspects.First,the factors that need to be considered for scheduling are expanded.In addition to considering the uncertainty of the temporal and spatial attributes of the newly added tasks,it also considers the uncertainty of the transportation mode and temporal and spatial attributes of the newly added workers.Then,the scheduling strategy is improved.By using the aggregate scheduling strategy,the dynamically added tasks are aggregated first,and then the task allocation and path optimization are performed.Compared with the traditional non-aggregated scheduling,the calculation time is significantly reduced.The last aspect is to improve the scheduling algorithm.Based on the traditional genetic algorithm,the task allocation and path optimization operations are performed iteratively.Compared with the scheduling algorithm that first allocates tasks and then optimizes the path,it improves the accuracy of the optimal results.In addition,a simulation platform for dynamic scheduling of space crowdsourcing task paths based on real map navigation is designed and implemented,and the method is verified by this platform.
作者
沈彪
沈立炜
李弋
SHEN Biao;SHEN Li-wei;LI Yi(School of Computer Science,Fudan University,Shanghai 201203,China;Shanghai Key Laboratory of Data Science(Fudan University),Shanghai 201203,China)
出处
《计算机科学》
CSCD
北大核心
2022年第2期231-240,共10页
Computer Science
基金
国家高技术研究发展计划(863计划)(2018YB1004800)。
关键词
空间众包
任务分配
任务调度
路径规划
遗传算法
Space crowdsourcing
Task allocation
Task scheduling
Route planning
Genetic algorithm
