公交网络最优路径求解算法的回溯实现.pdf

第34卷第3期湖南农业大学学报(自然科学版)Vol.34No.3
2008年6月JournalofHunanAgriculturalUniversity(NaturalSciences)Jun．2008

文章编号：1007-1032(2008)03-0379-04

公交网络最优路径求解算法的回溯实现

伍雁鹏1，彭小奇2，李仁明1
(1.邵阳学院网络中心，湖南邵阳422000；2.中南大学能源科学与工程学院，湖南长沙410083)
摘要：为解决大规模公交网络最优路径查询模型中的换乘问题，提出一种回溯的公交网络最优路径求解算法：
首先求解具有最短出行时间的最优路径的片段信息，然后回溯推导出最优路径的完整路径信息．算法所需内存少，
查询效率高，能很好解决公交网络换乘问题．
关键词：公交网络；公交换乘；最优路径；回溯
中图分类号：U491文献标识码：A

Implementationofbacktrackingpublictrafficpathsearchingalgorithm

WUYan-peng1，PENGXiao-qi2，LIRen-ming1
(1.CompusNetworkCenter，ShaoyangUniversity，Shaoyang,Hunan422000，China；2.SchoolofEnergyScienceand
Engineering，CentralSouthUniversity，Changsha410083，China）
Abstract：Traditionalshortestpathsearchingalgorithmcan’tsolvethetransferproblemintheoptimalpathsearching
modeloflargescalepublictransportnetwork.Anoptimalpathsearchingalgorithmofpublictransportnetworkbasedon
backtrackingispresent.Afterfindingoutfragmentinformationofoptimalpathwithshortesttimevalue,thisalgorithm
backtrackandsearchotherinformationtocompletewholeoptimalpathinformation.Thisalgorithmneedslessmemory
withhighefficiency.Experimentalresultsshowthealgorithmcansolvethetransferproblemperfectly．
Keywords：publictransportnetwork；publictraffictransfer；optimalpath；backtracking

城市交通网络越来越庞大复杂，设计一种高性易产生维数爆炸问题[4]．笔者提出公交网络最优路
能的城市公交网络最优路径求解算法，可以方便公径回溯求解算法，可以很好地解决大规模公交网络
众出行，缓解公交交通压力，提高城市形象[1]．经最优路径求解问题．
典最短路径算法，如Dijkstra算法、A*算法、Floyd
[2-3]1公交网络相关概念
算法等，可以很好地求解公交网络最短路径．但
是距离最短路径并不代表该路径的出行时间最少，一个公交网络包括多条公交线路，每条线路上
或出行费用最低，因为途中可能需要多次换乘不同分布有若干个上下乘客的站点．公交线路方向类型
的公交线路．也就是说经典最短路径算法可以求得有单向、双向、环行等，但均可转换成等价单向线
距离最短路径，但不能求得最优路径．有些算法将路形式．
最小换乘次数、最少出行时间或最少出行费用等目(1)公交网络用有向图G=()V，R表示，V是
标转换成统一度量目标，然后应用经典最短路径算站点的集合，R是所有公交线路集合．|V|=n，表
法进行计算，不足之处在于转换过程中难以标定换示有n个不同的站点．

算的系数．另外一些算法使用广度搜索算法或深度(2)公交线路定义：r={v1，v2，⋯，vi}，vi∈V，

搜索算法对最小换乘次数、最少出行时间、最少出表示线路r从站点v1出发，依次经过站点v2，⋯，

行费用等多个单目标依次进行搜索求解，但此类算最后到达站点vi．
法在计算过程中会搜索大量不合理的出行路径，容rr12rrdd−1
(3)公交路径定义：vvv012→→"→vdd−1→v，

收稿日期：2008-03-15简写为vv0→d，其中s表示在站点v0乘r1至v1，
基金项目：
邵阳市科技计划项目(53J07)然后换乘线路r2至站点v2，⋯，最后换乘线路rd
作者简介：伍雁鹏(19