A Novel Shortest Path Query Algorithm Based on Optimized Adaptive Topology Structure

城市轨道交通是公共交通的基本组成部分，然而常见的基于站点的路径搜索算法经常忽视换乘时间对搜索结果的影响，导致准确性降低。为了解决这个问题，本文提出了一种基于自适应拓扑优化的最短路径查询算法，称为自适应拓扑扩展道路网络结构（ATEN）。该算法将换乘站分类为不同类型，并将旅行时间和换乘时间等价地视为拓扑图中边的权重。所提出的算法引入虚拟站点来区分行人路径和列车路径，消除了对换乘站的额外操作的需要。该算法控制城市轨道交通拓扑的扩展程度，克服了现有算法中处理换乘站时引起的查询错误。最后，在北京城市轨道交通网络上进行了一系列模拟实验，以验证所提出的自适应拓扑优化算法的正确性和效率。结果表明，与现有类似算法相比，该算法具有显著的优势。

本论文旨在解决城市轨道交通中路径搜索算法忽略换乘时间对搜索结果影响的问题，提出一种基于自适应拓扑优化的最短路径查询算法ATEN。

ATEN算法将换乘站分为不同类型，将行程时间和换乘时间等同地视为拓扑图中边的权重，引入虚拟站点区分行人路径和列车路径，控制城市轨道交通拓扑图的扩展范围，从而解决了现有算法中处理换乘站的错误。

论文在北京市的城市轨道交通网络上进行了一系列模拟实验，验证了ATEN算法的正确性和效率。该算法相较于现有算法具有显著的优势。

最近的相关研究包括《Improving Shortest Path Computation in Large Road Networks by Exploiting Hierarchical Structures》、《Efficient Shortest Path Finding Algorithms for Road Networks with Turn Restrictions》等。