一种公交最佳路径选择方法.doc

一种公交最佳路径选择方法杨峰1，纪凯2，陈涛焘3，韩栋1（1.中国矿业大学（北京）资源与安全工程学院，北京100083；2.安徽省交通职业技术学院，安徽 合肥 230051；3.武汉理工大学交通学院，湖北 武汉 430070）摘要：本文通过分析最短路径算法及城市公交网络的特点提出了城市公交网络换乘的实现方法。首先，针对城市公交网络构造公交网络模型。其次，根据城市公交网络特点引入公交网络的直达矩阵，并依据该直达矩阵将城市公交网络抽象表示成一个“公交网络邻接图”。再次，利用最短路径算法结合城市公交抽象网络图计算，得出最少换乘次数和可能的换乘站点。最后，利用所建立公交网络模型及所得换乘次数和可能的换乘站点进行计算，得到了综合考虑最小换乘和最短路径的最佳路径。并用一算例检验了该算法的有效性。关键词：公交网络；最短路径；最小换乘；地理信息；网络分析One Way For Optimal Public Traffic Route ChoiceYANG FENG1， JI KAI2，CHEN TAO-tao3，HAN DONG1(1.School of Resource and safety engineering,China University of mining and Technology(Beijing),Beijing 100083，China；2.Anhui Communication Vocational & Technical Colleague，Anhui，230051，China；3.School of Transportation of WHUT，Wuhan University of Technoloy，Hubei，430070，China_)Abstract：This paper presents a way of public traffic transfer in city public transfer network by analyzing the arithmetic of shortest path and character of the city public traffic network system.Firstly,a publict traffic network model is made on the basis of city public traffic system.Secondly,a through matrix of the public traffic network was introduced into the article,and transform the city public traffic network system into an abstract “public traffic network adjacent plot”on the basis of the through matrix of the public traffic network.Thirdly,getting the least transfer number and the possible transfer station using the shortest path algorithm and city public traffic network system abstract plot.Finally, getting the optimal result in consideration of the shortest transfer and the shortest path length problem by using the publict traffic network model and the possible transfer station.And then,a simple example was made which validate the feasibility of the algorithm in the city public traffic system network.Key words：transit network; shortest path; least transfer; geography information; networks analysis随着我国社会经济的快速发展和城市化进程的加快，城市交通问题日趋严重。汽车的增加不仅造成了交通拥挤行车不畅，而且也造成了大量的空气污染和噪音污染。 公交系统是城市基础设施的一个重要组成部分。随着我国可持续发展战略的提出，合理规划、充分利用城市公交系统是缓解我国目前许多城市交通问题的重要途径，也是充分利用不可再生能源保护环境的一种重要手段。 目前我国的许多城市尤其是大城市都拥有城市电子地图。城市电子地图中的公交模块提供的交通查询服务功能为人们的出行提供了巨大的方便。通过该模块，用户可以方便的获得出行路线和换乘方案的信息。例如，当用户输入起始点和目标点之后，系统便可以给用户提供最优的公交出行方案。1公共交通网络模型一个公共交通网络是由一组公交线路及公交上下车站组成。每一条公交线路贯穿一组不同的上下车站点，且各条公交线路可以有相重合的上下车站点。在数学上，公交网络其实质是一个无向连通图1。表示为G(V，A)。其中V为公交网络中所有上下车站点的集合，A为公交路段的集合（即相邻两个上下车站点之间的线路）。图1为一个简易公交网络示意图。其中有三条公交线路L1L2L3，它们经过的公交站点分别如表所示：公交线路名公交线路所经站点名L1A、C、E；L2 A、B、C；L3D、C、F。表1为对应于该公交网络中各上下车站上所经过的公交路线，其中各边所对应的数字为其权。公交网络模型采用“结点弧段线”的数据结构表示2。该结构由表242表示，其中公交线路表中节点顺序按照公交线路中原始线路排列。在实际当中，虽然会有公交路口将两个相邻站点间的弧段分割，但这种分割并不影响我们对公交换乘问题的分析。因而无须在公交网络图中明确标出，只需表示出一条连接两相邻站点的弧段就可以。2公交换乘的算法2.1Dijkstra算法5 在求最短路径的各种算法中，目前公认的效率最高的算法是1959年由荷兰计算机专家E.W.Dijkstra提出的标号算法，该算法一般称为Dijkstra算法。该算法不仅可以求得从v点到w点之间的最短距离而且可以求从v点到图中任意点之间的最短距离。在Dijkstra算法中将图G中顶点分为P和T两部分，P为永久节点集，对P中的节点进行P标号l (v)，表示从v1到v的最短路径，T=V-P为临时节点集。对T中节点进行T标号l (v)，表示v1到v的一条路上的权。 其算法过程为： 令P=v1，对v1进行P标号，且l (v1)=0，其余节点T=V-P进行T标号，l (vj)=w1j，j=2,3,n，w1j为v1导vj的边上的权； 在T标号的节点中选择最小标号节点vj进入P； 对中选择的节点vj根据下式进行修改：min l (vj)，l (vi)+wij； 重复上述步骤，直到到达目标点。2.2公交网络抽象图 对于公交问题而言，其实质就是提供给乘客一种从出发点到目的点的最佳解决方案。通过对乘客出行的心理调查得知，在乘客出行时其最关心的问题是出行路线的便利性，即只需最小换乘次数便可到达目的地。其次才是时间最少，距离最短。而时间又与步行时间、等车时间、换乘次数、路线距离密切相关。因而本文所述公交换乘算法是基于最少换乘基础上的最短距离算法。 对于公交网络中任意一条公交线路上的任意两个上下车站点而言，其都是可以直接到达不需换乘。从而我们可以得到公交网络的直达矩阵T3。在该矩阵中，两站点间如果至少有一条公交线路经过则Tij=1，否则Tij=0。在公交网络的直达矩阵中，其行列顺序均为从的字母顺序依次进行排列。矩阵表示如下所示：根据该直达矩阵，整个公交网络便可以抽象表示成一个连通图（如图2）。图2公交网络邻接图在该图中，各个结点对应于公交网络中各上下车站点。对于图中任意两点间若有一条公交路线通过两点间便用一个弧段相连。为便于分析，对图2作如下规定：对于共交网络中不管两站点间有几条公交线路经过，图中只用一条弧段进行表达；各个弧段所对应的权均为1。对于该图我们可以称之为“公交网络站点邻接图”，它是公交网络图的抽象。2.3基于邻接图的最少换乘次数 利用Dijkstra算法，在图2中任给两点求出其最短路径。若两点间只有一条边相连，则说明两点间至少有一条公交线路经过，这两点可直达换乘次数N=0；若两点间需经n条弧段才能到达，则说明需要换乘，其换乘次数N=n-1，n为连接两站点间最少经过的弧段数，且换乘点为中间经过的点。2.4算法思想对公交换乘问题的解决思想分为如下几步：通过抽象公交路线图利用Dijstra算法求解在抽象公交网络图中起始站点与目标站点间的最短路径；获得所求最短路径中各个换乘站点，并将其按顺序排列；获得中所得到各相邻站点间所有公交线路；通过组合，依次连接各段公交线路，得到多条公交线路结果；计算求得各线路的路径长度即各段路径权的和，选出最短的线路即为所求结果。3算例 根据图1所示交通网络，我们求从A点至F点的最佳路径。（如图3所示） 第一步：通过对该公交网络的抽象图2，用Dijistra算法求得图2的最短路径，也即求得图1的最少换乘路径。计算步骤如下： 根据图2可知A点与F点不相邻，因而不存在一条公交路线从A点直接到达F点。必须进行换乘； 将A标号为P标号点。与A相邻的点有B、C、E。A点到这三点的权值 均为1，选取这三点为待定点，将其标记为T标号点； 求B、C、E点的相邻点。B点的相邻点为C，C点相邻点为D和F，E点无下一相邻点。B、C点到达其邻接点的权值均为1； 由于F即为所查找目的点，查找结束。将C点标记为P标号点。 A点到F点的路径为ACF。路径长度为L=AC+CF=2，换乘次数为n=路径长-1=2-1=1。换乘点为C点。 图3第二步：根据公交线路表求得最佳路径。其步骤如下：求经过公交路段两端点的所有公交线路；对于第一步所得各公交站点依顺序排列：A、C、F，则相邻两站点间为一公交路段。求经过相邻两站点间的所有公交线路。由表1得，经过A点且经过C点的公交线路有L1和L2。由所得各公交线路，根据公交线路表求得各线路长度。对L1线路而言，由表1可知在L1线路上A站点和C站点是相邻的两站点，根据表4得AC=2。对L2线路而言，由表1可知在L2线路上从A站点至C站点经过B站点，在L2线路上A站点至C站点的路线为：ABC。根据表4得，AB=1，BC=2，因而L2线路上AC=AB+BC=1+2=3。重复、步骤，求得各公交路段的实际路径长度，直至目标点。从C站点到F点只有L3线路，线路长度为CF=3。将各段线路组合得出各个线路换乘方案，对所得各方案中各段线路相加、比较，得最佳结果。 方案1：AF=L1+L2=AC+CF=2+3=5； 方案2：AF=L2+L3=AB+BC+CF=3+3=6； 比较后可知最佳路径为方案1，从A点乘L1至C点换乘L3即可到达F点。4结论 设计合理的公交网络和公交最佳路径选择方法给人们的出行带来极大的便利。而公交换乘是公交网络敏感而又不可避免的问题。距离最短往往并不意味着线路是最优的。本文通过对公交网络进行抽象生成新的抽象公交网络图，并根据Dijkstra算法首先确定出最少换乘次数及换乘点。再通过第一步所得结果根据公交线路表最终得到综合考虑换乘次数和路径长度的最佳公交换乘线路。参考文献：1严蔚敏、吴伟民，数据结构M，北京：清华大学出版社，1997