一种基于空间节点聚类方法的快速公交换乘方法

摘要

一种基于空间节点聚类方法的快速公交换乘方法，包括以下步骤：建立城市公交站点的邻近关系网络T；使用一种空间节点聚类方法对网络T进行站点聚类，起到降低计算网络规模的目的；将运算得到的最大完全子图映射为节点，并由这些节点生成一个新的网络P进行存储；根据实际限制与实时信息每隔一定时间更新网络P连边的权值；通过持久化存储信息找到用户查询指定的起始站点S与终止站点D各自在网络P中归属的节点SC和DC；计算节点SC和DC之间由节点构成的最小代价路径；通过存储信息反向生成起始站点S到终止站点D之间的优化换乘方案。本发明有效缩短计算时间、实时性良好。

主权项

一种基于空间节点聚类方法的快速公交换乘方法，其特征在于：包括以下步骤：步骤一：建立城市公交站点的邻近关系网络T，在这个网络中，当两个站点间的物理空间距离小于等于阈值时，在两个公交站点间存在一条连边；步骤二：使用空间节点聚类方法对网络T进行站点聚类，所述聚类方法是通过查找网络T中的所有最大完全子图完成；步骤三：将通过步骤二运算得到的最大完全子图映射为节点，并由这些节点生成一个新的网络P并进行存储；在网络P中，当两个节点在网络T中对应的最大完全子图间存在直接的公交线路连接时，这两个节点间存在一条连边；步骤四：根据实际限制与实时路况信息，每隔设定时间更新调整网络P的连边的权值，所述的权值代表通过公交系统从一个站点聚类抵达另一站点聚类需要花费的代价；步骤五：确定用户查询指定的起始站点S与终止站点D各自在网络P中归属的节点SC和DC，通过Dijkstra算法或弗洛伊德算法计算节点SC和DC之间由节点构成的最小代价路径，最后通过存储信息反向生成起始站点S到终止站点D之间的优化换乘方案。