一种建立公交网络的最短路径改进算法

A New Updated Shortest Path Algorithm for Urban Public Bus Network

目前,对最短路径问题的研究很多,基本都是关注算法的计算效率问题,而其应用到具体领域时会遇到一些算法本身无法解决的细节问题。如将邻接结点算法用于公交网络的最短路径计算时,会遇到诸如缺少网络拓扑信息、属性数据复杂等问题。本文针对这些问题给出了解决方法:在计算最短路径之前,利用算法将站点和线路数据进行自动匹配,建立公交网络的拓扑关系。同时在数据存储方式上进行了改进,运用数据库存储复杂的公交属性数据和中间过程中产生的公交网络数据,节约了运算时的内存占用率,提高了数据的利用率,使算法更具实际意义。

There are many researches and applications about the shortest path searching in GIS field, but mainly focusing on the algorithmic efficiency analysis and modeling. When those algorithm models are applied in the specific fields, they will face many difficulties for themselves to solve the details in cases. The typical sample is found in the shortest path searching for urban public bus network by using a shortest path searching algorithm based on the neighborhood node network, causing some problems in its applications, such as the lack of topo-logical network information, the difficulty to handle the complicated attribute data, etc. In this paper, the authors propose a new updated shortest path algortithem for urban public bus network through two aspects for optimization of algorithm and data storage configuration. The first one proposes the solution for constructing the topology of public bus network by automatic matching the bus stop and bus line data using the algortithm (before the shortest path calculation), and the second solution improves data storage efficiency by using the database to store the complicated transport attribute data and the newly produced transport network data in the processing, rather than through RAM. The scheme was applied in Beijing public bus network testing system, and has got satisfied effects in usability of data and saving ram storage.