(19)中华 人民共和国 国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202111613349.9 (22)申请日 2021.12.28 (65)同一申请的已公布的文献号 申请公布号 CN 113987729 A (43)申请公布日 2022.01.28 (73)专利权人 广州市交通 规划研究院 地址 510030 广东省广州市越秀区广仁路1 号广仁大厦15楼 (72)发明人 景国胜　马小毅　刘明敏　何鸿杰　 李彩霞　刘新杰　金安　陈先龙　 李磊　陈建均　张科　吴恩泽　 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/20(2020.01) G06K 9/62(2022.01)G06F 111/04(2020.01) (56)对比文件 CN 112309119 A,2021.02.02 CN 111260221 A,2020.0 6.09 CN 112347596 A,2021.02.09 CN 109808741 A,2019.0 5.28 CN 112861383 A,2021.0 5.28 陈建均. 《基 于聚类分析法的广州地铁周末 客流变化规律》 . 《轨道交通》 .2019,第141-147 页. 审查员 李艳丽 (54)发明名称 一种基于土地利用的大规模城市轨道网络 自动生成方法 (57)摘要 本发明公开了一种基于土地利用的大规模 城市轨道网络自动生成方法， 分为六个步骤： S1 建立数学模型； S2进行聚类分析获得多个站点聚 类； S3对各个站点聚类求解最小生成树， 合并各 个最小生成树； S4对合并后生成的网络方案进行 网络修正； S5计算修正后的生成网络方案的总长 度， 若小于最小总长度， 更新最优生成网络方案 和最小总长度； S6若迭代次数未达到上限， 回到 步骤S3， 多次迭代以上步骤S3 ‑S5， 否则结束流 程； 所述生成方法能够基于土地利用的站点选址 方案， 量化地进行城市轨道网络设计， 以克服主 观设计规划方案难度高、 站点和网络结构形式繁 多、 影响因素较多导致方案优选困难等问题， 提 高城市轨道网络规划的科 学性和合理性。 权利要求书3页 说明书10页 附图11页 CN 113987729 B 2022.03.01 CN 113987729 B 1.一种基于土地利用的大规模城市轨道网络自动 生成方法， 所述轨道网络自动 生成方 法能够基于站点选址方案 自动生成整体轨道网络； 所述站点选址方案包括站点编号、 名称 和对应的空间地理位置坐标； 其特 征在于， 详细步骤如下： S1根据站点选 址方案选择聚类算法， 建立数 学模型； S1.1设站点选址方案内的站点集合为 ， 期望生成的轨道网络表示为决策变量矩阵X， 矩阵中对应的某一元 素为 ， 其实际意 义为： S1.2对模型进行多种约束， 所述约束包括站点间可达性约束、 站点的度约束、 线路角度 约束、 站间距约束， 所述约束将通过生成网络修 正方法得到满足； S1.3对于城市轨道交通， 轨道网络生成的目标 是得到长度最小化的生成网络： 式中， cij——站点i和站点j间单位长度固定建 设成本； dij—— 站点i和站点j间的线路建 设长度； S2进行聚类分析并获得多个站点聚类； S2.1根据站点的空间地理位置坐标， 对站点选址方案中的站点进行空间上的层次划 分， 将所有站点划分为 不同的站点群， 并预 先构造生成网络的初始形态； S2.2不同类型的轨道交通网络所对应的最适用聚类算法不相同， 按照以下情形进行选 择： 1） 环形、 曲线和条状线路组成的轨道网络： 基于层次聚类中的单 连接准则； 2） 放射性和混合轨道网络： K ‑Means算法； 3） 多中心团块状轨道网络： 除谱聚类算法外任何算法均可； S2.3在确定使用的聚类算法后， 使用平均轮廓系数评价聚类效果， 并根据评价结果选 择最优的聚类算法超参数， 轮廓系数由以下公式计算： 式中，ai——在同一个聚类内， 站点 i和其他簇内站点的平均距离； bi——站点i和站点i所在聚类相邻最接 近聚类内所有站点的平均距离； S3对各个站点聚类求 解最小生成树， 合并各个最小生成树， 直到站点间相互可达； 最小生成树的求 解基于聚类分析 得到的站点群， 具体步骤如下： S3.1聚类分析： 将构成轨道交通网络所有的站点聚类， 按照站点的相对位置采用适当 的聚类算法进行聚类分块； S3.2最小生成树求解： 使用Krusk al算法求解各个聚类的最小生成树， 对所有站点构 建 最小生成树的总问题分解 为对各个 较小聚类构建最小生成树的子问题； S3.3子最小生成树合并： 将求解子问题得到的最小生成树合并为所有站点的生成树， 该生成树的边的总长度应接近对所有站 点直接构建的最小生成树， 合并的原则是在使 所有权　利　要　求　书 1/3 页 2 CN 113987729 B 2站点之间相互可达， 同时网络总长度增 加最小化； S4对合并后生成的网络方案进行网络修 正； S5计算修正后的生成网络方案的总长度， 若小于最小总长度， 更新最优生成网络方案 和最小总长度； S6若迭代次数未达到上限， 回到步骤S3， 多次迭代以上步骤S3 ‑S5， 否则结束流程， 即可 得到最优生成网络方案和最小总长度。 2.根据权利要求1所述的一种基于土地利用的大规模城市轨道网络自动生成方法， 其 特征在于， 步骤S4对合并后生成的网络方案进行网络修 正， 步骤如下： 三角形分支修复： 三个站点仅需由两条较短的边连接即可保持相互可达， 对不符合要 求的站点进行修 正； 锐角分支修正： 对从多条线路交叉处的锐角部分延伸出来的站点数量仅为2 的错误分 支进行修 正， 将该错 误分支融合到临近线路； 线路交叉修复： 在网络密度较大处， 对大量聚集、 紧邻的异常的交叉点进行修复和融 合； 冗余分支合并： 移除两段平行直线段间存在多余连接， 并进行调整； 起终点站点筛选： 度为1的站点若不是起终点站点， 需要在满足约束的情况下与周边站 点建立新连接相连， 以延长潜在线路的长度； 锐角线路修复： 网络部分区域的边集不满足角度约束， 角度过小， 需要对不满足约束的 边集进行修复； 潜在线路延长： 在将最小生成树求解算法应用于棋盘型网络而非放射型网络时， 会导 致生成网络无法形成棋盘型网络， 大部分站点之间处于不相互直接连接的状态， 经过较多 站点的长距离线段 无法形成， 潜在线路较短， 需要尽可能将某些网络 部分进行延续。 3.根据权利要求1 ‑2任一项所述的一种基于土地利用的大规模城市轨道网络自动生成 方法， 其特征在于， 步骤S1.2中， 所述站点间可达性约束、 站点的度约束、 线路角度约束、 站 间距约束如下： 1） 站点间可达性约束： 所有站点必须全部被网络访问， 即任意两站点间一定可达； 设网 络X对应的可达矩阵为A， A可通过Warshall算法计算得到， 当站点 i和j之间相互可达时， A的 元素aij=1， 否则aij=0； 该约束可以表示 为： 2） 站点的度约束： 网络中以某一站点 为端点的边设置的最大 数量； 该约束可以表示 为： 式中， Pmax——站点的最大度； 3） 线路角度约束： 网络 中的欧拉路径非交点部分， 角度不能过大； 设站点间的距离矩阵 为D， 若站点 i和站点j间存在邻 接关系， 其元素 dij表示站点间的邻 接距离； 若站点 i和站点j 间不存在邻接关系，  dij表示站点间的直线距离； 若 i=j， 则dij=0； 对于欧拉路径上三个连续 的站点i， j， h， 应满足如下关系：权　利　要　求　书 2/3 页 3 CN 113987729 B 3