王 庆,潘荣英
(苏州市职业大学 数理部,江苏 苏州 215104)
城市公交最优路径选择的数学模型及其算法
王 庆,潘荣英
(苏州市职业大学 数理部,江苏 苏州 215104)
通过对城市公交路径选择问题的分析,在常用的Dijkstra最短路径算法基础上进行改进,根据乘客的不同需求给出出行总距离最短、出行总费用最少、出行总时间最短的最优路径选择模型.综合考虑距离、时间、费用等多种因素给出的出行满意度最大的最优路径模型,同时以算例验证了模型和算法的合理性和实用性.
公交;Dijkstra算法;最优路径
随着苏州市经济的快速发展,城市的规模不断扩张,随之而来的是城市道路交通拥堵问题越发严重[1].为了缓解城市道路交通拥堵,苏州市近年以“公交优先”为战略,新开辟了很多的公交线路,但公众出行还面临着诸如公交网络重复度高、公交线路过长、换乘不便等问题.因此,从苏州市的实际出发,结合公众实际出行的情况,建立城市公交最优路径选择的数学模型有重要意义,不仅提高了公众的出行效率,还节约了社会成本,促进社会的可持续发展.
20世纪70年代初国外开始有关城市公交最优路径选择的研究,80年代国内学者开始关注,提出了各种相关算法,而且得到具体应用[2].本文通过对常见的迪杰斯特拉(Dijkstra)最短路径及其算法的分析,指出其实现公交最优路径选择的缺点,根据苏州市公交线路的实际,提出更适合公交查询的改进的Dijkstra最短路径算法.通过引入苏州市各条公交线路直达时的最短距离矩阵,构造了公交网络直达关系图.根据公众不同的出行需求,通过改进的Dijkstra最短路径算法,可以分别求得出行总距离最短、出行总费用最少和出行总时间最少的公交线路.综合考虑距离、时间、费用等因素,建立公众满意度最大的最优路径选择数学模型.
图1上两点间的最短路径的算法很多,1959年提出的Dijkstra最短路径算法,目前应用最为广泛.它能够得到起点到终点、起点到所有顶点的最短路径,算法如下:
第1步,初始化.图1中所有顶点组成的集合记为V={1,2,…,n},起点O到任一顶点i的最短路径距离为L[i]=min(D[i,1])(其中D[i,1]是起点O到顶点i的距离),最短路径中在顶点O之前的最近顶点记为Y[i].
第2步,在V-S集合中搜寻使L[t]最小的顶点t,放入到S集合中,当V-S是空集合时,停止搜寻.
第3步,改变Y,D中的值,即对V-S集合中顶点t的邻接顶点i,如果L[i]>L[t]+D[i,t],那么令Y[i]=t,L[i]=L[t]+D[i,t].
继续执行第2步.
由于公交线路形成的网络拓扑非常复杂,因而导致Dijkstra 最短路径算法的数据结构复杂、算法时间长.将公交站点看作网络上的顶点,相邻站点间的路段看作边,Dijkstra 算法计算最短路径时要求乘客每到一个公交站点都可以转车,从而最短路径可能需要很多次转车,这样的计算结果可行但没有意义.考虑苏州市的城市特点和公交线路的实际,认为转车不超过2次是符合实际的.为此,对Dijkstra 最短路径算法[3]进行修正.
第1步,输入起点和终点.
第2步,求过起点或其周边的路线s(i)(i=1,2,…,m),过终点或其周边的路线t(j)(j=1,2,…,n).
第3步,搜寻s(i)=t(j)的路线,若有,输出路线:起点到终点的直达路线为s(i)也即t(j);若没有,往下执行.第4步,求路线s(i)上的站点E(i,x)(x=1,2,…,p),路线t(j)上的站点F(i,y)(y=1,2,…,q).
第5步,搜寻E(i,x)=F(j,y),若有,输出路线:满足此条件的路线s(i),t(j)(可能有多条)就是换乘1次的公交路线,算出各种换乘1次的乘车路程,得到换乘1次的最短路线,再求换乘站点;若没有,往下执行.
第6步,求经过E(i,x)的路线r(z)(z=1,2,…,k),求路线r(z)的站点G(z,r)(r=1,2,…,h).
第7步,搜寻G(z,r)=F(j,y),若有,输出路线:满足此条件的路线s(i),t(j),r(z)(可能有多条),就是换乘2次的公交路线,算出各种换乘2次的乘车路程,得到换乘2次的最短路线,再求换乘地点;若没有,表明换乘2次不可行,结束搜寻.
图1 路径
2.1 出行总距离最短的最优路径选择模型
第1步,给出公交线路各站点直达时的距离矩阵.将公交站点作为顶点,依照公交车的行驶方向:双向的站点之间用边连接;单向的站点之间用弧连接,在公交线路站点的邻接关系图上运用修正的Dijkstra算法,可以求出任意两点之间的最短路径,建立该线路的最短距离直达矩阵.
第2步,构造公交系统总的各站点直达时的距离矩阵.将所有公交线路各站点直达时的距离矩阵用Λ :aΛ b =min{a, b}合成,得到公交系统总的各站点直达时的距离矩阵 B= B1ΛB2Λ…ΛBn.
第3步,对矩阵B使用修正的Dijkstra算法,可以得到连接任意两点出行总距离最短的最优路径.
2.2 出行总费用最少的最优路径选择模型
由于公交线路的收费都与乘车距离成正比,先将各条公交线路的直达距离矩阵转换为直达票价矩阵;再将直达票价矩阵利用运算Λ合成为总的直达票价矩阵;最后对该直达票价矩阵利用改进的Dijkstra算法,可以得到连接任意两点出行总费用最少的最优路径.
2.3 出行总时间最少的最优路径选择模型
出行总时间由公交运行时间、换乘、等车的时间组成,而公交运行时间与路程有关.为了求出出行总时间最少的最优路径,规定公交路线上相邻站点间的运行时间与乘客的换乘时间大致相同,将各条公交线路的直达距离矩阵转变为直达时间矩阵,再将直达时间矩阵利用运算Λ合成为总的时间矩阵,最后按照下列算法计算任意两站点之间的最短时间[4].
第3步,给出至多换乘k-1(k≥2)次就能到达的最短时间矩阵当Tk=Tk−1时,得到任意两个站点之间的最短通行时间矩阵.
2.4 出行满意度最大的最优路径选择模型
以上给出了只考虑一种因素(距离、时间、费用等)时最优路径的选择模型及算法.然而现实中,公众出行选择公交时,会综合考虑距离、时间、费用等因素来选择满意度最大的乘车路径.为此,首先根据公众出行的偏好来确定各因素的权重,将各条公交线路对应的直达距离矩阵、直达时间矩阵、直达费用矩阵标准化处理后加权平均,得到直达综合满意度矩阵;再对各条公交线路的直达综合满意度矩阵利用运算Λ合成为总的直达综合满意度矩阵,利用修正的Dijkstra算法可以求出综合满意度最大的乘车线路.
图2是由6个站点(编号为a-f),2条公交线路(实线为1号线、虚线为2号线,双向且来回站点相同,用无向图表示)构成的公交网.
图2 6个站点构成的公交网
首先,给出图2中公交线路的直达关系矩阵
其次,利用Dijkstra算法得到每条线路的最短直达距离矩阵Bk=,其中表示第k号线第i站到第j 站的最短距离,
进一步,给出图中公交系统总的直达距离矩阵
其中bij(k)表示第i站到第j站乘坐k号线的最短路径的距离.
最后,对总的直达距离矩阵使用修正的Dijkstra算法,给出任意两站之间最短路径的距离矩阵
依据最短路径的距离矩阵就能得到经过站点最少的乘车路径.
进一步,把任意站点之间的实际距离代入到各条公交线路对应的直达关系矩阵,则可以得到任意两站之间的出行总距离最短的最优路径;把任意站点之间的乘车费用代入到各条公交线路对应的直达关系矩阵,则可以得到任意两站之间的出行总费用最少的最优路径;把任意站点之间的出行时间代入到各条公交线路对应的直达关系矩阵,则可以得到任意两站之间的出行总时间最短的最优路径;将距离、时间、费用等因素赋予权重,则可以得到任意两站之间的出行满意度最大的最优路径.
利用改进的Dijkstra最短路径算法,根据乘客的不同需求给出出行总距离最短、出行总费用最少、出行总时间最短的最优路径模型,综合考虑距离、时间、费用等多种因素给出出行满意度最大的最优路径模型,同时以算例验证了模型和算法,说明模型和算法的合理性和实用性.
[1] 戴泉华,黄剑. 苏州公交发展中的矛盾及解决方案[J]. 江苏交通,2002(5):11- 13.
[2] 王建林. 基于换乘次数最少的城市公交网络最优路径算法[J]. 经济地理,2005,25(5):673-676.
[3] 王振军,王宁宁,李鸿. 基于邻接矩阵的公交换乘算法的研究[J]. 徐州工程学院学报,2006,20(3):74-77.
[4] 许军林,蒋年德. 一种改进的公交换乘算法的实现[J]. 电脑知识与技术,2007,14(2):517-518.
(责任编辑:沈凤英)
On the Mathematical Models and Algorithms of Optimal Public Transport Lines
WANG Qing,PAN Rong-ying
(Department of Mathematics and Physics,Suzhou Vocational University,Suzhou 215104,China)
Through the analysis of city bus routes,this paper intends to improve the practice over the approach of Dijkstra by putting forward a mode in determining the shortest or optimal route in terms of distance,expenditure and time allowing for different requirements from the passengers. This mode and algorithm is proved to be rational and practical by numerical examples.
public transport;Dijkstra algorithms;optimal route
O141.4
A
1008-5475(2014)04-0058-04
2014-08-20;
2014-09-18
苏州市职业大学研究性课题(SZDYKC-140901)
王 庆(1979-),男,江苏扬州人,副教授,硕士,主要从事应用数学研究.