(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111375023.7 (22)申请日 2021.11.19 (71)申请人 电子科技大 学 地址 611731 四川省成 都市高新区 （西区） 西源大道 2006号 (72)发明人 李龙江　康雅洁　高源辰　 (74)专利代理 机构 成都虹盛汇泉专利代理有限 公司 51268 代理人 王伟 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 50/26(2012.01) G06K 9/62(2022.01) (54)发明名称 一种基于多尺度聚类的大规模公交线网分 级优化方法 (57)摘要 本发明公开一种基于多尺度聚类的大规模 公交线网分级优化方法， 应用于交通道路规划领 域， 针对现有技术在解决特大规模公交线路网络 优化问题时存在的计算复杂 度高， 且优化结果不 理想的问题， 本发明的方法考虑基于公交IC刷卡 记录和车载GPS记录获得大批量乘客需求数据， 结合深度神经网络工具， 预测出行需求(OD流)的 时空分布。 本发 明通过选取高需求密度节点为中 心进行网络出行需求等价聚类分割， 获得 Voronoi划分簇， 基于粗粒度聚类网络生成待选 线网集合， 之后再对各簇内部网络进行细粒度聚 类等价分割， 利用最短路径偏好， 沿街道走向通 过分布式计算对跨簇路径进行簇内和簇间局部 调优筛选和调优。 权利要求书2页 说明书5页 附图3页 CN 114037175 A 2022.02.11 CN 114037175 A 1.一种基于多尺度聚类的大规模公交线网分级优化方法， 其特 征在于， 包括： S1、 基于公交IC刷卡记录和车 载GPS记录获得乘客需求数据； S2、 根据乘客需求数据构建出 行需求矩阵； S3、 将公交路网图表示为无向图G＝<V,E>， 其中V为道路交叉路口的集合， E为交叉路口 间的直接连接 关系； 每个交叉路口表 示为一个节 点， 任意两个节点之 间， 若可以通过道路相 通， 且不经过其它节点， 则这两个节 点之间存在一条边， 这条边的权重为 公交车在这两个节 点之间的行驶时间； S4、 采用Voro noi算法对无向图G＝<V,E>进行分割， 得到Voro noi划分簇； S5、 对无向图G＝<V,E>进行粗粒度聚类， 生成待选线网集 合； S6、 对各Voronoi划分簇内的待选线网， 进行小粒度聚类， 得到最总的公交线网规划结 果。 2.根据权利要求1所述的一种基于多尺度聚类的大规模公交线网分级优化方法， 其特 征在于， 步骤S4具体为： S41、 根据出 行需求矩阵， 计算个节点的出 行需求密度； S42、 选取高密度节点作为Voro noi划分簇的中心 节点， 得到若干Voro noi划分簇。 3.根据权利要求2所述的一种基于多尺度聚类的大规模公交线网分级优化方法， 其特 征在于， 步骤S41的出 行需求密度计算式为： 式中， D为考虑节点p周围出行需求的网络最短路径度量距离上限， di为第i个节点vi到 节点p的路段欧氏长度或曼哈顿长度， demandi为第i个节点vi所具有的出 行需求总数。 4.根据权利要求3所述的一种基于多尺度聚类的大规模公交线网分级优化方法， 其特 征在于， 步骤S5具体为： S51、 生成一个新的网络H＝<HV,HE>， 其中HV是Voronoi热点的集合， HE是相邻Voronoi 划分簇的中心 节点间的边的集 合； S52、 对于原网络G＝<V,E>中的某条边， 若两端节点分别位于某个相邻Voronoi划分簇 的中心节 点所在的两个Vor onoi划分簇， 则将该条边的权重累加到这对相邻Vor onoi划分簇 的中心节点的边上； S53、 若已遍历完成原网络G＝<V,E>中的所有边； 则输出待选线网集合， 否则返回步骤 S52。 5.根据权利要求4所述的一种基于多尺度聚类的大规模公交线网分级优化方法， 其特 征在于， G＝<V,E>中的边的权 重具体为： 该边的两个节点的出 行需求之和。 6.根据权利要求5所述的一种基于多尺度聚类的大规模公交线网分级优化方法， 其特 征在于， 步骤S6具体为： 基于最短路偏好， 对待选线网集合， 根据街道走向信息对线网集合 细化和调优。 7.根据权利要求6所述的一种基于多尺度聚类的大规模公交线网分级优化方法， 其特权　利　要　求　书 1/2 页 2 CN 114037175 A 2征在于， 各Voro noi划分簇内的待选线网调优 采用分布式并行计算。权　利　要　求　书 2/2 页 3 CN 114037175 A 3