(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211366350.0 (22)申请日 2022.11.03 (71)申请人 南京感动科技有限公司 地址 210004 江苏省南京市秦淮区菱角市 66号国创园39-102 (72)发明人 齐家　王鑫之　朱磊　李露露　 (74)专利代理 机构 江苏致邦律师事务所 32 230 专利代理师 樊文红　尹妍 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/20(2020.01) G06F 111/04(2020.01) G06F 111/06(2020.01) G06F 111/08(2020.01) (54)发明名称 一种利用观测数据构建路网设施拓扑结构 的方法 (57)摘要 本发明涉及一种利用观测数据构建路网设 施拓扑结构 的方法， 包括： 以车辆为单位构建观 测行程记录序列； 基于观测行程记录序列提取涉 及的设施 点作为顶点， 设施间拓扑关系 作为候选 边， 并根据顶 点出入流量将顶 点属性划分为中间 点、 入口点和出口点； 以拓扑中各中间节点的流 入与流出净差值的总和作为模型目标函数， 以最 小化模型目标函数为目标， 结合顶点和边的约 束， 建立拓扑模型； 基于启发式算法求解所述拓 扑模型， 获得最优解。 本发明利用路网路侧设备 自身的观测数据实现路侧设备拓扑关系的动态 构建， 极大程度减少人工标注的工作， 同时不依 赖空间几何计算， 在构建的过程中不依赖无需设 备位置信息与路网地理信息数据。 权利要求书2页 说明书10页 附图2页 CN 115438453 A 2022.12.06 CN 115438453 A 1.一种利用观测数据构建路网设施拓扑 结构的方法， 其特 征在于， 包括： 通过开窗或抽样从原始数据中获取车辆观测数据， 并进行数据清理， 之后以车辆为单 位， 按照数据的观测时间顺序排列， 构建观测行程记录序列； 基于观测行程记录序列提取涉及的设施点作为顶点， 设施间拓扑关系作为候选边， 并 根据顶点出入流 量将顶点属性划分为中间点、 入口点和出口点； 以拓扑中各中间节点的流入与流出净差值的总和作为模型目标函数， 以最小化模型目 标函数为目标， 结合顶点和边的约束， 建立拓扑模型； 基于启发式算法求 解所述拓扑模型， 获得最优解， 即构建的路网设施拓扑 结构。 2.根据权利要求1所述的方法， 其特征在于， 在构建观测行程记录序列之前， 对行程记 录数据进行筛选， 包括基于行程记录的车辆信息和行程特性进行筛选； 以及基于车辆信息 筛选构建拓扑的行程记录， 并利用行程特性剔除指标值离群的行程记录 。 3.根据权利要求1所述的方法， 其特 征在于， 在数据开窗时， 窗口大小的确定方式为： 1） 按照不同窗口大小对原 始数据进行分组多批次采样； 2） 对样本数据进行 预处理并建立观测行程记录序列； 3） 采用平均值或中位数对行程记录的设施数按窗口和抽样批次进行统计分析， 找到窗 口增大、 获得设备 数增加但边际收益增量下降的位置， 即为 最优窗口大小。 4.根据权利要求1所述的方法， 其特征在于， 根据顶点出入流量计算流量平衡度， 基于 流量平衡度划分顶点属性， 包括： 对所有顶点， 分别计算 其流出量总和 及流入量总和 ； 定义流量平衡度为 ； 根据实际建模时的平衡度分布直方图确定流量平衡度阈值上下限， 将流量平衡度小于 阈值下限的顶点划分为出 口点， 流量平衡度大于阈值下限的顶点划分为入口点， 其余为中 间点。 5.根据权利要求1所述的方法， 其特 征在于， 所述顶点和边约束包括： 约束任意顶点的入度与出度上限； 约束任意中间点的入度与出度下限； 约束入口点仅存在连 出边， 出口点仅存在连入边； 排除没有实际观测流 量的边及自环边。 6.根据权利要求1所述的方法， 其特 征在于， 利用模拟退火算法求 解所述拓扑模型。 7.根据权利要求6所述的方法， 其特征在于， 拓扑模型求解时， 迭代过程中拓扑结构的 调整方式为： 对顶 点间的拓扑关系的布尔值进行调整， 如果两顶点间存在拓扑关系， 则布尔 值为1， 即增 加连入边， 否则为0， 即断开连入边。 8.根据权利要求7所述的方法， 其特征在于， 拓扑模型求解时， 初始解的构建方式为以 下任意一种： a. 随机构建初始拓扑： 对任意顶点， 如果该顶点为中间点且不存在连入边， 则随机增加连入边， 若不存在连出 边， 则随机增加连出边； 如果该顶点为入口点且不存在连出边， 则随机增加连出边； 如果该 顶点为出口点且不存在连入边， 则随机增 加连入边；权　利　要　求　书 1/2 页 2 CN 115438453 A 2b. 基于连接 权重概率随机构建初始拓扑； 计算各边在同一起点的所有边中的权重， 及同一终点的所有边中的权重， 在根据顶点 按类型增 加边时， 根据边的权 重进行随机抽取； c. 在根据顶点按类型增 加边时， 直接 选取权重最高的边。 9.根据权利要求7 所述的方法， 其特 征在于， 拓扑模型求 解时， 新解的产生方法为： 在当前解中随机选择一个中间点顶点， 基于当前解计算中间点顶点上流出量和流入量 的差值； 在 满足约束的情况下对顶点进 行随机增减边， 产生新解， 如果无法在满足约束的情 况下产生新解， 或当前差值已最小， 则保持当前解进入下一迭代。 10.根据权利要求1所述的方法， 其特征在于， 还包括， 对构建的路网设施拓扑结构进行 核查， 基于地图可视化方式展示算法获得的拓扑关系， 在GIS系统中通过抽检或巡检方式检 查算法构建的拓扑关系是否存在错误或缺漏， 并对错误/缺 失的连接 关系进行删除/增补处 理。权　利　要　求　书 2/2 页 3 CN 115438453 A 3