(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111456613.2 (22)申请日 2021.12.02 (71)申请人 杭州衣科信息技 术股份有限公司 地址 311100 浙江省杭州市余杭区南苑街 道新城路108号 409室 (72)发明人 张永智　欧平均　徐克强　 (74)专利代理 机构 杭州天昊专利代理事务所 (特殊普通 合伙) 33283 代理人 赵志鹏 (51)Int.Cl. G06Q 10/04(2012.01) G06F 16/29(2019.01) G06Q 50/26(2012.01) G06Q 50/30(2012.01) (54)发明名称 一种基于动态路网信息的最优路径分析方 法 (57)摘要 本发明公开了一种基于动态路网信息的最 优路径分析方法， 具体步骤如下： 101)数据采集 步骤、 102)数据接入步骤、 103)缓存数据步骤、 104)数据分析步骤； 本发明提供参合了静态信息 和动态信息的数据， 并通过相应缓存处理， 来降 低运算量和快速找出最优路径的一种基于动态 路网信息的最优路径分析方法。 权利要求书2页 说明书8页 附图2页 CN 114418165 A 2022.04.29 CN 114418165 A 1.一种基于动态路网信息的最优路径分析 方法， 其特 征在于： 具体步骤如下： 101)数据采集步骤： 采集每个路径上路段的静态信息和动态信息， 静态信息包括路段 的长度、 路况、 地理位置等， 动态信息包括发生事故、 车流量大小、 指示灯状况、 大雾天气等 路况变化实时信息； 102)数据接入步骤： 将需要分析的起始地址和 终点地址接入， 获取两地址之间的所有 路段的静态信息和动态信息； 103)缓存数据步骤： 采用集中式缓存机制将步骤101)采集的数据进行缓存， 将各个服 务器共用一个缓存服务器， 当发生 缓存不够用时， 通过新增缓存服务器来解决； 即将新增的 缓存服务器与之前的缓存服 务器构成新的大空间的缓存服 务器； 104)数据分析步骤： 将缓存的数据通过分割并行计算进行运算分析处理， 分割并行计 算是将整个数据形成的有向图先分成若干区域， 然后先计算出各区域间的最优路径对， 形 成一个上层的主干网； 基于该主干网， 再分析两点间最优路径时， 只要 先分析出源点和终点 距自身所在区域边界点的最优路径， 然后结合源区域和终点区域之间的主干最优路径， 快 速得出最终的最优路径。 2.根据权利要求1所述的一种基于动态路网信 息的最优路径分析方法， 其特征在于： 静 态信息包括权重属性参数和极值属性参数， 路段的权重属性参数通过累计叠加获得整合后 路段的权重属性参数， 权重属性参数包括路段的长度、 路段的收费额等； 路段的极值属性参 数只获取整合后路段中的其中一段的最大值或最小值。 3.根据权利要求1所述的一种基于动态路网信 息的最优路径分析方法， 其特征在于： 采 集每个路径上路段的静态信息采用定时人工现场采集， 动态信息采用人工采集、 GPS位置采 集、 视频监控识别采集的方式进行。 4.根据权利要求1所述的一种基于动态路网信 息的最优路径分析方法， 其特征在于： 集 中式缓存机制包括数据构造方法； 数据构造方法， 其定义以一个节点为源点， 到其余各节点最优路径的缓存内容； 若到某 点的最优路径还未求出， 则其点集标志为false； 具体通过类DijCacheItem实现， 类 DijCacheItem内部有Dij方法、 ad dOneStati on方法、 ad dToRedSet方法和ad dBlueSet方法； DijData方法， 用于存放各顶点的最短路径权值； addOneStation方法， 实现在一个源点的cache项中， 动态追加一个站点， 并对该站点的 cache值作初始化； addToRedSet方法， 把蓝点集 中的一个点移动 到红点集中， 红点集中的点为已经找到最 优路径的点， 蓝点 集中的点 为未找到最优路径的点； addToBlueSet方法， 把红点集中的点取消撤回到蓝点集中， 常用于动态站点移除的场 合。 5.根据权利要求1所述的一种基于动态路网信 息的最优路径分析方法， 其特征在于： 集 中式缓存机制包括缓存 命中方法； 缓存命中方法在进行路径数据分析之前， 先根据起始地址和终点地址的索引号、 权重 类型参数， 从缓存池中查找有无对应的缓存项； 若没有找到， 则新建一个缓存项， 并加入缓 存池； 若找到 了， 则在这个缓存项的基础上继续进行最优路径分析； 若目标点的最优路径在上述缓存项中已经进行过相同分析， 则可以直接命中返回； 否权　利　要　求　书 1/2 页 2 CN 114418165 A 2则需要在已有的路径分析基础上继续按常规的方法进行路径分析， 直至找到目标点为止； 同时把结果作为 新的缓存内容加入到原有缓存中； 若进行路径数据分析时附带了分析条件， 则此时缓存机制 失效， 只能按常规路径分析 方法进行。 6.根据权利要求1所述的一种基于动态路网信 息的最优路径分析方法， 其特征在于： 集 中式缓存机制包括缓存失效方法； 缓存失效方法， 在路径上路段的静态信息和动态信息改变的情况发生时， 原来位于缓 存中的计算好的最优路径将会部分失效， 为了减少缓存重建消 耗， 应设法确保只把那部分 失效的分析结果清除， 而不是把所有结果都清除； 具体处理策略包括边权重增大、 边断路、 边权重减少、 增 加一条边、 减少一条边， 具体如下： 边权重增大， 若该边的终点还未求得最优路径， 则无需进行缓存失效； 这是因为此时红 点集中所有红点的最优路径都不会经过该边， 该边的权重变化不会影响到它们， 因此这些 红点的缓存值依然 有效； 若该边的终点已经求得最优路径， 即根据最优路径分析长度递增规律， 起点肯定也已 求得最优路径值， 则需要 进行下面缓存失效过程： 对于所有权重小于 “终点最优路径值 ”的红点无需进行缓存失效处理； 这是因为这部分 红点的最优路径也未 经过该边， 不受该边权 重变化的影响； 对于所有权重大于等于 “终点最优路径值 ”的红点需要进行缓存失效处理； 对于这部分 红点其实只需要对以该边终点 为直接或间接前序顶点的所有红点进行失效处 理就行了； 边断路， 相当于将该边的权重置为无穷大， 这可以按照上述 “边权重增大 ”方式进行最 优路径实效处 理。 边权重减少， 若该边的终点还未求得最优路径， 则无需进行缓存失效； 若该边的终点已 经求得最优路径， 则需要 进行下面缓存失效过程： 将起点最优路径值加上 该边减少后的权 重， 得到终点路径值的一个 “新值”； 对于所有权 重小于等于 “新值”的红点无需进行缓存失效处 理； 对于所有权重大于 “新值”的红点需要进行缓存失效处理， 所有的这部分红点都需要重 新计算一下路径分析 结果缓存内容； 增加一条边， 获取新增边的起止两节点； 若新增边的权重大于等于起止两节点间已有 任意一条边的权重， 则无需进行任何缓存失效处理； 若新增边的权重在起止两节点之间最 小， 则需要 按上述“边权重减少”方式进行最优路径失效处 理； 减少一条边， 相当于将该边的权重置为无穷大， 按照上述 “边权重增大 ”方式进行最优 路径实效处 理。 7.根据权利要求1所述的一种基于动态路网信 息的最优路径分析方法， 其特征在于： 步 骤104)中的有向图的若干区域都需要用到一个实例， 在数据量庞大的情况下， 具体创建调 用如下： 在系统启动或初始化 时， 预先创建好一定数量的实例， 这些实例对象处于就绪状态， 随 时可用， 把这些实例称为 “实例池”； 当一个路径分析任务执行线程启动时， 它可以直接从实 例池中快速获取一个空闲的实例， 并将其加锁防止其他分析线程再使用 它， 然后进行路径 分析， 分析 结束后再确保及时将该实例释放回实例中， 以供其 他分析线程使用。权　利　要　求　书 2/2 页 3 CN 114418165 A 3