Title

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

Translated Titles

Best-routing Algorithm for Public Transportation Systems

Authors

王莉(Li Wang);李文权(Wen-Quan Li)

Key Words

公交网络 ; 最短路径 ; 最佳路径 ; 矩阵 ; 最少换乘 ; transit network ; shortest path ; best path ; matrix ; least transfer

PublicationName

東南大學學報(自然科學版)

Volume or Term/Year and Month of Publication

34卷2期(2004 / 03 / 20)

Page #

264 - 267

Content Language

簡體中文

Chinese Abstract

在分析城市道路网络最短路径算法(SP算法)和公交网络的特点的基础上,提出公共交通系统最佳路径算法。首先引入直达矩阵(T矩阵)和最小换乘矩阵(Q矩阵),讨论公交网络节点间换乘问题,得出最少换乘算法。利用Q矩阵确定节点间最少换乘次数,评价公交网络方便可达性。其次结合最少换乘算法,对最短路径算法(Dijkstra算法)进行改进。在标号过程中,利用Q矩阵对待检验T标号点进行筛选,减少T标号计算量,得到一条综合考虑路径长度和换乘的最佳路径。最后用一个简单的算例进行验算,说明该算法适用于一般公交网络,特别是换乘代价较高的公交网络。

English Abstract

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.

Topic Category 基礎與應用科學 > 基礎與應用科學綜合
生物農學 > 生物農學綜合
工程學 > 工程學綜合