摘要:明年8月第29届奥运会将在北京举行,届时有大量观众到现场观看奥运比赛,这将对北京的交通带来巨大的影响。本文以给出的北京地区公交路线为参考资料,根据公交网络换乘问题构建了公共交通网络模型。对三个问题的解决方案如下:(1)针对问题1,本文首先利用MATLAB编程将公交线路读出,求出各站点间的邻接矩阵。再根据所求的邻接矩阵。对求得的邻接矩阵进行处理;判断起点和终点之间有没有直达的线路,如有就确定为最优线路,没有就在通过程序寻找一个合适的数值(记为M)作为限制(即找出邻接点最多的那部分站点),找出通过次数超过这个数值的站点。下一步则寻找换乘站点。通过把求得的站点与要求的起点和终点,建立循环逐个修改开始站点与最终站点的值可求出通过各站点的路线,再将经过所求得的站点的路线与经过起点和终点的路线进行比较,寻找相同的路线,若存在,则这个站点可以作为所给的这对起点与终点的中转站(但根据人们乘车的习惯,假设中转的次数不超过2次)。如果的站点中无法找到中转站,则调整M的值,直到可以找到可行的乘车路线为止。根据得到的可行乘车线路,利用路过分别与费用和时间的函数关系,计算出按照吸收较小转车次数的原则,比较用钱少、费时少的线路,最终得到最优的乘车方案。(2)针对问题2,将换乘地铁站和公汽站视为对等的,与问题1相似,利用相同的方法求出最优线路,但是情况比问题1更复杂,特别是地铁与地铁之间还可以换乘,这需要单独进行考虑。此时,站点数、费用和时间的函数发生了变化,因此,利用新的函数表达式求解再比较得到最优线路。(3)针对问题3,考虑步行时,可先利用图论中的Floyd算法求出任意两站点间的最短道路,并在此基础上求出这段路步行所需要的时间。再在第二问的基础上,对时间加一个阈值T。当计算出的两点间最短路的步行时间阈值T时,就选择步行,否则,选择问题2中求得的最优线路。本文所考虑的算法,可以查询任意两个站点间的乘车最优路径。关键词:MATLAB程序、公交换乘、限制求解、Floyd算法、最优线路一、问题重述北京申奥的成功,对北京市的交通系统提出了更高的要求。依据国外举办奥运会的经验教训来看,奥运期间交通状况是否良好,交通管理是否高效,是关系奥运盛会能否圆满成功举办的举足轻重的条件之一。因此,必须在全面调研基础上,制定切实可行的交通规划及管理策略,为奥运会的成功保驾护航。在观众的交通行为中,轨道站点、外围停车场和专用巴士的换乘,是整个交通链的重要环节,一旦出现交通瓶颈,其向上游反馈形成的阻塞波(或者称为交通扰动)会溯源而上并且影响加剧,最终造成主会场人员疏散的延误和交通设施服务水平的降低以及一定程度上的混乱和连带的不可估量的经济损失、负面的社会影响。因此应从系统全局考虑进行换乘系统规划,保证观众出行全过程的流畅。二、模型假设1、乘客到起始站可以直接选择公汽或地铁班次上车,即不记在起始站的等待时间。2、在实际过程中,对于公交(包括公汽与地铁)可能要换车2次以上,用户已无法容忍,视为无法到达。(因为如果他们之间换乘就使得费用增大了很多,这是人们不愿意看到的,且一般只坐地铁是无法到达终点站的,所以还要再换乘其他的工具,换乘次数太大我们也不再将其纳入考虑的范围)。3、相邻地铁站平均行驶时间(包括停站时间):2.5分钟。4、相邻公汽站平均行驶时间(包括停站时间):3分钟。5、公汽换乘公汽平均耗时:5分钟(其中步行时间2分钟)。6、地铁换乘地铁平均耗时:4分钟(其中步行时间2分钟)。7、地铁换乘公汽平均耗时:7分钟(其中步行时间4分钟)。8、公汽换乘地铁平均耗时:6分钟(其中步行时间4分钟)。9、公汽票价:分为单一票价与分段计价两种,标记于线路后;其中分段计价票价为:0~20站:1元;21~40站:2元;40站以上:3元。10、地铁票价:3元(无论地铁线路间是否换乘)。11、已知所有站点之间的步行时间。12、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。13、郊县和繁华地区公交车站的间隔大概一致。三、符号说明1、表示第一问中从起点站到终点站所用的总时间。2、表示表示第一问中从起点站到终点站经过的总站点数。3、M表示求取局部最优解的限制值。4、T表示判断是坐车还是步行的阈值,但这个值因人而易。四、问题的分析文献[2]对公交乘客的出行心理进行了研究,其结果表明,“换乘次数”是大部分公交乘客在选择出行路线时首先考虑的因素,其次是出行耗时和距离长短。而出行耗费的时间与换乘的次数,及等车的时间以及距离的长短密切相关。因此,对于出行耗时和距离长短,转化为换乘次数最少的基础上出行距离最短的问题。对公交换乘的问题进行研究,首先就是要解决公共交通网络模型如何合理地表述;其次是公交换乘问题的解决思想。公共交通网络不同于一般的道路交通网络,在许多书籍文献中都对公共交通网络的特点进行了阐述,如网络的连通性不同于普通道路网,结点有其空间位置特性和一对多的属性等,并分析了弧段的特性及有向线的性质。对于公交网络的特点不再赘述。在GIS网络分析中,公共交通网络可以映射为一个有向图。根据公共交通网络的特点,把公交网络模型映射为,其中,G为有向赋权图;V表示网络上所有结点即公交站点的集合,一个公交站点可能是多条公交线路的上下客站点;表示网络边(连接公交线路上两个公交站点之间的弧段)的集合,若A站点与B站点是n条线路的相邻上下客站点,那么A与B之间至多有2n条连接边:R表示网络上连接起始点和目标点间所有结点的公交线路的集合;是结点的非负权值;是边的非负权值[4]。最优出行路径就是指乘客从起始点到目标点所选择的一系列连通结点组成的距离最短的路段及最少换乘的公交线路的集合。[3]在GIS中道路网络的基本框架是“结点一弧段”模型。但对于弧段包含的属性是一对多的关系、弧段使用线型系统而不是二维坐标确定点的位置、弧段中的属性需要分段处理等情况,这种模型显得无能为力。这里将交通网络模型采用“结点一弧段(可有多条弧段)一有向线”的数据结构(如图1)来存储网络图。按照公共汽车线路选择所经过的“站点一路线一站点”形成路径分析中的有向线。所以以分支多的站点作为求解换乘站点的突破点。由对与各站点邻接的站点的个数的统计,如图2所示(其中14表示的是含有邻接点个数为16的情况),可以断定邻接点个数较小的站点的比列较大,在大部分站点处换乘机会存在的可能性很小,所以我们并没有必要多所有的站点进行搜索,找寻换乘点;而只需在含有邻接点个数较大的站点中找寻,从而产生了限制性的搜索方法。五、模型的建立5.1只考虑公汽的情形:由于公交车站的间隔大概在1000m左右(郊县和繁华地区可能略有差别,所以忽略这种差别),因此在换乘次数尽量最少的原则之下,以从出发地点到达目的地点的总乘车站数为基准,找出换乘车前后总乘车站数为最少的作为系统的推荐线路,这样即符合常规,也可能是最优线路[2]。对于任意的起点和终点,可能存在以下四种情况:(1)、起点与终点在同一线路上,不需要换车(即存在直达路线);(2)、起点与终点不在同一线路上,需要换车1次;(3)、起点与终点不在同一线路上,需要换车2次;(4)、起点与终点不在同一线路上,需要换车次数大于2次,视为通过换车无法达到(见模型假设2)。为尽量满足使换乘次数达到最少,首先利用递归的方式,判断起点和终点之间是否有直达路线,如有就比较其用时与费用,选择花费时间与金钱都最少的路线作为最优路线;否则,就确定M的值,选择含有邻接站点个数大于M的那些站点进行考虑(即采取限制求解的方法),在他们中间寻找换乘站点,而不是对所有的路线进行考虑。具体方法是:把求得的站点与要求的起点和终点,利用附录:(三),建立循环诼个修改begin_s与end_s的值可求出通过各站点的路线,再将经过所求得的站点的路线与经过起点和终点的路线进行比较,寻找相同的路线,若存在,则这个站点可以作为所给的这对起点与终点的中转站(但根据人们乘车的习惯,假设中转的次数不超过2次。如果求得的站点中无法找到中转站,就调整M的值,依上面的步骤继续进行,直到可以找到可行的乘车路线为止。根据得到的可行乘车线路,利用路过分别与费用和时间的函数关系,计算出按照吸较小转车次数的原则,比较用钱少、费时少的线路,最终得到最优的乘车方案。如所走线路与时间的函数关系为:5.1同时考虑公汽与地铁线路的情形:因为公汽与地铁之间可以换乘,所以当同时考虑公汽与地铁线路时,可以将可换乘的地铁站和公汽站视为对等的,这样就与第一小问相同了,可利用相同的方法来解决。虽然仍只是先求出可行线路,但情况要更复杂了,特别是地铁与地铁之间的换乘,这还需要单独进行考虑。此外,此时站数分别与费用和时间的函数却发生了变化,需利用新的函数表达式求解再比较得到最优线路。新的站数与时间的函数如下:设n表示走地铁所经过的站数其中:a式表示从起点经过地铁直达终点所费时间;b式表示从起点经过公交和地铁到达终点所费时间;c式表示从起点经过公交和地铁,再经过公交到达终点所费时间。由条件可知,T1是上行,下行站完全相同的一条地铁,而T2是一条环路,且他们之间在D12站点可以相互换乘,即是说两条地铁的结构图可能为螃蟹型。5.3、当已知所有站点之间的步行时间时的情形:可先利用图论中的Floyd算法[1]求出任意两站点间的最短道路,并在此基础上求出这段路步行所需要的时间。再在第二问的基础上,对时间加一个阈值T。①、当计算出的两点间最短路的步行时间阈值T时,就选择步行,走得到的最短道路;②、当计算出的两点间最短路的步行时间阈值T时,就选择第二问中求得的最优线路。六、模型的求解6.1、只考虑公汽的情形求解结果得:针对问题1,运用本文所述算法,求得6条线路的乘车公交线路如下:(1)、S3359→S1828换乘一次起点站班次中转站班次终点站时间总费用S3359L436S2606L217S18281303S3359L436S1784L167S18281013(其中粗线条的行表示求得的最优公汽线路)(2)、S1557→S0481换乘两次起点站班次中转站一班次中转站二班次终点站时间总费用S1557L84S0028L348S2361L312S04811574S1557L84S0055L348S2361L312S04811603S1557L84S0978L206S1511L460S04811624S1557L84S0978L212S3409L460S04811333S1557L84S1919L189S3186L460S04811063S1557L84S1921L279S0618L72S04811694S1557L84S1921L279S0327L72S04811603S1557L84S1921L80S0618L72S04811694S1557L84S1921L58S3878L239S04811964S1557L84S1921L58S3878L514S04811934S1557L84S1921L80S1327L72S04811603S1557L84S1919L80S0618L72S04811604S1557L84S1919L80S1327L72S04811513(3)、S0971→S0485换乘一次起点站班次中转站班次终点站时间总费用S0971L13S0992L417S04851313(4)、S0008→S0073换乘一次起点站班次中转站班次终点站时间总费用S0008L159S3919L103S00731493S0008L198S1383L282S00731133S0008L198S3766L282S00731133S0008L355S2302L57S0073862S0008L463S1383L282S00731133S0008L463S2083L170S0073922S0008L463S2084L170S0073922(5)、S0148→S0485换乘两次起点站班次中转站一班次中转站二班次终点站时间总费用S0148L308S0128L276S1671L395S04-852326(6)、S0087→S3676换乘一次起