计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 231-240.doi: 10.11896/jsjkx.210400249
沈彪, 沈立炜, 李弋
SHEN Biao, SHEN Li-wei, LI Yi
摘要： 空间众包用于解决带时空约束的线下众包任务,近几年得到了快速发展。任务调度是空间众包的重要研究方向,难点在于调度过程中任务和工作者的动态不确定性。为了高效地进行任务路径动态调度,提出了同时考虑任务和工作者的不确定性的空间众包任务路径动态调度方法,该方法进行了3方面的改进。首先,扩展了调度需要考虑的因素,除了考虑新增任务的时空属性不确定性之外,还考虑了新增工作者的交通方式和时空属性的不确定性。其次,对调度策略进行改进,通过使用聚合调度策略,对动态新增任务先进行聚合处理,随后再进行任务分配和路径优化,相比传统非聚合调度计算时间显著减少。最后,对调度算法进行改进,基于传统遗传算法,将任务分配和路径优化操作迭代进行,相比先进行任务分配再进行路径优化的调度算法,提高了获取最优结果的准确性。此外,文中设计并实现了基于真实地图导航的空间众包任务路径动态调度模拟平台,并基于该平台验证了所提方法的有效性。
中图分类号:
| [1]FAN Z J,SHEN L W,PENG X,et al.Multi stage task allocation on constrained spatial crowdsourcing[J].Chinese Journal of Computers,2019,42(12):2722-2741. [2]WANG K,WANG Z J.Crowdsourcing Collaboration ProcessRecovery Method[J].Computer Science,2020,47(10):19-25. [3]GUMMIDI S R B,XIE X,PEDERSEN T B.A survey of spatial crowdsourcing[J].ACM Transactions on Database Systems,2019,44(2):1-46. [4]SUN D,XU K,CHENG H,etal.Online delivery route recommendation in spatial crowdsourcing[J].World Wide Web,2019,22(5):2083-2104. [5]TAO Q,ZENG Y,ZHOU Z,et al.Multi-worker-aware taskplanning in real-time spatial crowdsourcing[C]//International Conference on Database Systems for Advanced Applications.Springer,2018:301-317. [6]LIU G R.Study on express route optimization problem withsimultaneous delivery and pickup under dynamic demands[D].Chongqing :Chongqing University,2018. [7]LIU M,SHEN Y,SHI Y.A hybrid brain storm optimization algorithm for dynamic vehicle routing problem[C] //International Conference on Swarm Intelligence.Springer,2020:251-258. [8]LU X,TANG K,MENZEL S,et al.A competitive co-evolutio-nary optimizationmethod for the dynamic vehicle routing pro-blem[C]//Symposium Series on Computational Intelligence.IEEE,2020:305-312. [9]SBAI I,KRICHEN S.An adaptive genetic algorithm for dyna-mic vehicle routingproblem with backhaul and two-dimensional loa-ding constraints[C]//International Multi-Conference on Organization of Knowledge and Advanced Technologies.IEEE,2020:1-7. [10]TONG Y,ZHOU Z,ZENG Y,et al.Spatial crowdsourcing:asurvey[J].The VLDB Journal,2020,29(1):217-250. [11]DENG D,SHAHABI C,DEMIRYUREK U.Maximizing thenumber of worker's self-selected tasks in spatial crowdsourcing[C]//21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM,2013:324-333. [12]COSTA C F,NASCIMENTO M A.In-route task selection incrowdsourcing[C]//26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM,2018:524-527. [13]ZHANG J,YANG F,WENG X.An evolutionary scatter search particle swarm optimization algorithm for the vehicle routing problem with time windows[J].IEEE Access,2018,6:63468-63485. [14]YU D H,CHENG T,YUAN X.Software Crowdsourcing TaskRecommendation Algorithm Based on Learning to Rank[J].Computer Science,2020,47(12):106-113. [15]LI Y,YIU M L,XU W.Oriented online route recommendationfor spatial crowd sourcing task workers[C]//International Symposium on Spatial and Temporal Databases.Springer,2015:137-156. [16]COSLOVICH L,PESENTI R,UKOVICH W.A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem[J].European Journal of Operational Research,2006,175(3):1605-1615. [17]ASGHARI M,SHAHABI C.On on-line task assignment in spatial crowdsourcing[C]//International Conference on Big Data (Big Data).IEEE,2017:395-404. [18]HU Z H,SHEU J B,ZHAO L,et al.A dynamic closed-loop vehicle routingproblem with uncertainty and incompatible goods[J].Transportation Research Part C:Emerging Technologies,2015,55:273-297. [19]MU Q,FU Z,LYSGAARD J,et al.Disruption management ofthe vehicle routingproblem with vehicle breakdown[J].Journal of the Operational Research Society,2011,62(4):742-749. [20]GÜNER A R,MURAT A,CHINNAM R B.Dynamic routingunder recurrentand non-recurrent congestion using real-time its information[J].Computers & Operations Research,2012,39(2):358-373. [21]CHO E,MYERS S A,LESKOVEC J.Friendship and mobility:user movement inlocation-based social networks[C]//17th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.ACM,2011:1082-1090. [22]SUN Y,WANG J,TAN W.Dynamic worker-and-task assignment on uncertain spatial crowdsourcing[C]//22nd Internatio-nal Conference on Computer Supported Cooperative Work in Design.IEEE,2018:755-760. [23]FELDMAN J,MEHTA A,MIRROKNI V,et al.Online sto-chastic matching:Beating 1-1/e[C]//50th Symposium on Foundations of Computer Science.IEEE,2009:117-126. |
| [1] | 王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020 |
| [2] | 杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005 |
| [3] | 谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生. 海上风电场通用运维路径规划模型优化及仿真 Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms 计算机科学, 2022, 49(6A): 795-801. https://doi.org/10.11896/jsjkx.210400300 |
| [4] | 谭珍琼, 姜文君, 任演纳, 张吉, 任德盛, 李晓鸿. 基于二分图的个性化学习任务分配 Personalized Learning Task Assignment Based on Bipartite Graph 计算机科学, 2022, 49(4): 269-281. https://doi.org/10.11896/jsjkx.210500125 |
| [5] | 田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117 |
| [6] | 谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126 |
| [7] | 吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110 |
| [8] | 王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023 |
| [9] | 陈镜宇, 郭志军, 尹亚昆. 基于混合算法的智能割草机全遍历路径规划及其系统设计 Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm 计算机科学, 2021, 48(6A): 633-637. https://doi.org/10.11896/jsjkx.201100002 |
| [10] | 郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131 |
| [11] | 王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239 |
| [12] | 左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053 |
| [13] | 杜婉茹, 王潇茵, 田涛, 张越. 面向未知环境及动态障碍的人工势场路径规划算法 Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles 计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170 |
| [14] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
| [15] | 姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191 |
|
||
首页