公共交通系统最佳路径算法  

Best-routing algorithm for public transportation systems

作　　者：王莉[1] 李文权[1] 

机构地区：[1]东南大学交通学院,南京210096

出　　处：《东南大学学报（自然科学版）》2004年第2期264-267,共4页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目 ( 5 0 0 780 15 )

摘　　要：在分析城市道路网络最短路径算法 (SP算法 )和公交网络的特点的基础上 ,提出公共交通系统最佳路径算法 .首先引入直达矩阵 (T矩阵 )和最小换乘矩阵 (Q矩阵 ) ,讨论公交网络节点间换乘问题 ,得出最少换乘算法 .利用Q矩阵确定节点间最少换乘次数 ,评价公交网络方便可达性 .其次结合最少换乘算法 ,对最短路径算法 (Dijkstra算法 )进行改进 .在标号过程中 ,利用Q矩阵对待检验T标号点进行筛选 ,减少T标号计算量 ,得到一条综合考虑路径长度和换乘的最佳路径 .最后用一个简单的算例进行验算 ,说明该算法适用于一般公交网络 ,特别是换乘代价较高的公交网络 .This paper presents a best-routing algorithm for public transportation systems on the basis of analyzing the shortest path algorithm in urban traffic network and the character of transit network. T matrix and Q matrix are introduced to discuss the path-planning problem and the least transfer algorithm is obtained. By using Q matrix the least transfer between two nodes can be determined and the performance of the transit network is evaluated. By integrating the algorithm into shortest path algorithm, a best path in consideration of path length and transfer can be found. Finally, a simple numerical example is given which shows that this algorithm is applied to general transit network especially to a high transfer-cost network.

关 键 词：公交网络 最短路径 最佳路径 矩阵 最少换乘 

分 类 号：U491[交通运输工程—交通运输规划与管理]