(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111502271.3 (22)申请日 2021.12.09 (71)申请人 王彬 地址 443100 湖北省宜昌市 夷陵区黄金路 10号 (72)发明人 王彬　 (51)Int.Cl. G06F 30/20(2020.01) G06F 16/29(2019.01) G06F 119/02(2020.01) (54)发明名称 随机GIS网络驱动的交通 最短可靠路径方法 (57)摘要 针对现有技术的最短路径问题和交通N最短 路径问题是考虑行程时间确定的场景， 但拥堵的 城市交通网络中， 行程时间具有高度的不确定 性， 出行者在行程时间不确定的情况下更倾向于 选择可靠度高的路径， 本申请提出随机交通网络 中的最短可靠路径问题和最短可靠路径扩展问 题的解决方法， 通过减小最短可靠路径计算的规 模， 高效查找大型GIS交通网络中的最短可靠路 径； 并针对一般有环网络， 求解前N条最 短可靠路 径， 改进优势明显， 一是行程时间确定性限制少， 机动性大， 灵活方便； 二是高效求解前N条最 短可 靠路径， 强化最短可靠路径的可靠性和可用性； 三是GIS网型交互性强， 精度高， 算法复杂 度相对 小， 有力的促进ITS和ATIS的发展和推广运用。 权利要求书5页 说明书16页 附图6页 CN 114186410 A 2022.03.15 CN 114186410 A 1.随机GIS网络驱动的交通最短可靠路径方法， 其特征在于， 提出随机交通网络 中的最 短可靠路径问题和最短可靠路径扩展问题的解决方法， 通过减小最短可靠路径计算的规 模， 高效查找大型GIS交通网络中的最短可靠路径； 并针对一般有环网络， 求解前N条最短可 靠路径； 第一， 针对大型GIS网络， 提出基于交通层级收敛的最短可靠路径方法： 基于层级收敛 方法对大型交通网络进行预处理， 按照结点的重要性进行排序， 基于网络结点的重要性对 网络结点进行收敛操作， 进行反复层级压缩， 采用添加快速边的方式保持原始交通网络拓 扑结构不变， 根据多目标支配条件,确定支配路径,然后用最短可靠路径算法进行检索查 询， 并构建新的网络， 在新的网络中求解最短可靠路径问题； 层级收敛的最短可靠路径方法 实现包括拟定结点 顺序和结点收敛； 第二， 针对有环一般交通网络， 提出基于自适应去 除的N最短可靠路径方法： 在行程时 间不确定的场景下， 寻找一般有环网络中的交通N最短可靠路径， 通过不断去除求得的最短 可靠路径， 在新网络图上求解最短可靠路径； 根据随机交通网络行程时间的不确定性， 基于 去除路径自适应方法， 在新网络图上求解最短可靠路径就是原始图的次最短可靠路径， 如 此不断迭代， 达到求解N最短可靠路径的目标， 通过扩展结点的方式保持网络拓扑结构不 变； 在一般有环网络中优化寻找最短可靠路径， 采用一个启发式函数， 通过优先考虑距离目 标地近的结点进行检索进一 步改善性能。 2.根据权利要求1所述的随机GIS网络驱动的交通最短可靠路径方法， 其特征在于， 交 通GIS最短可靠路径问题定义： 定义一个有向图F(M,D)， M表示结点， D表示弧边， 每条弧边d ∈D有一个尾结点， 有一个头结点， 和一个随机行程时间， 结点k∈M及结点a∈M表 示K‑A结点 对， 一条路径表示为qv在K‑A结点对之间， 给定的路径qv包含h个结点 和h‑ 1条弧边 路径行程时间用Rv表示， 计算整条路径上的弧边行程时间的总和： 是路径qv上第i条边弧 上的行程时间分布， 这条路径上的行程时间Rv是一个随机 变量， 它的行程时间的平均值和标准差分别用rv和bv表示， 在z可靠度下按时到达的路径表 示为qv， 在z置信水平下所需时间用累计概率密度函数的相反数 表示， z∈[0,1]， 假 定每条路径上 的行程时间符合正态分布， 每条路径上 的路段相互独立， 行程时间符合正态 分布， 另外边弧的行程时间分布相互独立， 采用层级网络模型来优化查询效率， 路径的行程 时间的平均值和标准差分别表示 为： 和 分别表示 边行程时间 的均值和标准差,所需的行程时间预算用式4表示：权　利　要　求　书 1/5 页 2 CN 114186410 A 2Xz是在置信水平z下正态分布的分布， 累计概率密度函数的相反数对应一个常数， 通过 查表或计算得到； 每一对结点(u， k)∈M ×M存在确定的最短可靠路径,若两点之间存在至少一条路径,两 结点之间存在两条路径q1和q2， 路径的行程时间的均值和标准差分别是用 和 和 和 表示， 则采用多标准模型 添加快速边： 1)如果 并且 则保留路径q1； 2)如果 并且 或 并且 则保留两条路径q1和q2； 3)如果 并且 则保留路径q2。 3.根据权利要求1所述的随机GIS网络驱动的交通最短可靠路径方法， 其特征在于， 层 级收敛的最短可靠路径方法架构： 基于层级收敛的最短可靠路径法最重要的部 分是对网络 进行预处理过程， 对所有结点进行排序， 执 行的程序如下 所示： 方法步骤： F＝(M,D) 循环u∈M排序迭代do 循环(u,v)∈D如果u＞v  do 循环(v,k)∈D如果 k＞v do 如果＜u,v,k＞从u到k可能存在唯一 一条最短路径 然后D： ＝D∪( (u,k)}(采用多标准模型M ‑V进行判断) 收敛结点 时添加的边弧即快速边， 它们仅表示在当前网络图中， 如果结点v和它邻 接边 被从图中移除,用来保存现有图中的最短路径的， 若边(u,k)已经存在图F中， 但它的权重比 新添加的快速边(u,k)的权 重还大， 则仅改变已存在边的权 重值； 路径q＝＜u, …,k＞≠＜u,v,k＞， 如果k(q)≤k(u,v,k)， 则q＜u, …,k＞为验证路径， 这条验证路径不是最短路径或不是唯一 最短路径， 它的存在 省略一条 结点之间的快速边； 以上方法整个步骤是为结点v寻找验证路径和添加快速边， 这个过程就是收敛结点v， 图F的起始点和目标地 （k ‑a） 所有最短路径， k,a＞v， 结点v是他们的中间结点， 当结点v不是 他们的中间结点， 在图F 中起始点和目标地 （k ‑a） 之间存在 一条路径q*， 递归应用这个步骤， 仅当结点v＞结点u并且结点v在 起始点和目标地之间最短路径q*的内部， v才收敛， 边(u,v) ∈D定义为结点v的传入边， 边(u,v)定义为结点v的传出边， 当结点u＞结点v 时， 结点u为保 留结点， 边的邻接边为保留边， 含有保留结点的图称为保留图， 压缩之后的新的网络图包含 上面方法步骤的得到的结果， 被压缩之后的结点就是层级收敛， 按照结点的重要性进行排 序。 4.根据权利要求1所述的随机GIS网络驱动的交通最短可靠路径方法， 其特征在于， 拟 定结点顺序： 采用启发式可扩展的优 先队列存储 结点， 压缩 结点v时， 仅需要知道结点u满足 条件u＞v即可， 结点压缩从最低的结点开始， 用优先队列存储不断被压缩的结点， 将新压缩 的结点加入到优先队列中， 当进行结点选择时， 也是从优先队列中选择， 结点v的优先级与 优先参数和被压缩的结点的吸引度线性相关， 结点的优先项是一个特定的属 性， 并且与已 收敛的结点和剩余的结点相关， 在结点被压缩之后， 相应的优先条件也要改变， 需要被更权　利　要　求　书 2/5 页 3 CN 114186410 A 3