空间众包中在线路径规划算法

发布时间：2024-03-23 17:48

　　工作者的路径规划问题是空间众包中一个重要的研究内容。当前路径规划问题的研究主要集中在离线情形下,然而在线情形下的路径规划更符合现实需求。因此,该文从众包物流和共享巴士等典型空间众包平台中提取出了一个在线路径规划问题——空间众包中终点固定的在线路径规划问题。首先研究了Euclidean空间上的路径规划问题,提出了基于粒子群的在线粒子群路径规划算法,该算法通过在线追踪最优解来进行路径规划,同时,提出了基于k近邻的在线局部粒子群路径规划算法。还研究了面向路网的路径规划问题,提出了加权最短路径边界索引和路网上的在线局部粒子群路径规划算法。最后,通过真实数据上的大量实验验证了上述算法的有效性和高效性,其中在线局部粒子群路径规划算法拥有更好的效果。

【文章页数】：11 页

【部分图文】：

图3离线路径规划图

图2在线粒子群路径规划算法过程2.2在线局部粒子群路径规划算法

图4请求r′的k近邻与孤立点

本文把请求r′的近邻分为2种类型:一种是不产生孤立点的近邻集合N,另一种是产生孤立点的近邻集合Ν～。若请求r′的所有近邻请求在原路径p中是连续的,则称r′的近邻是不产生孤立点的近邻集合N;否则称r′的近邻是产生孤立点的近邻集合Ν～。事实上,孤立点也是一个....

图6路网索引建立图

区域划分:首先顶点v与其距离至多为δ的邻居顶点构成一个区域,对路网进行区域覆盖,其中顶点v为中心点。为了尽量减少区域的数量,将顶点按度排序,以顶点作为中心点开始广度优先遍历进行区域划分。图6a中的路网可以按δ=5划分为如图所示的3个区域。首先对顶点按度排序得到顶点....

图10参数对算法结果的影响

在4个数据集上对算法结果与执行时间进行比较。采取控制变量的方式对参数进行选择,其中组合1、组合2、组合3用来比较参数m不同取值的影响;组合1、组合4、组合5用来比较参数n不同取值的影响;组合1、组合6、组合7用来比较参数k不同取值的影响。实验结果如图10和1....

本文编号：3936267