城市公交自主查询系统模型

1城市公交自主查询系统模型摘要：明年8月第29届奥运会将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具出行。网络的普及，如果能预先了解出行的最佳路线，那对出行者尤其是对外地游人来说就带来了极大方便。但是通常乘客选择出行路线时受到以下几个因素的作用:“换乘次数”、“出行距离”、“出行耗时”、“出行费用”等。因此，本文针对出行者的自身需求给出了求解最佳路线的数学模型。由于最佳路线受以上几个因素的影响，所以本文提出了两个数学模型分别求解出最优解。模型一是优先考虑最优的换乘次数，再找最短时间，再求最少费用。但从实际情况考虑这个模型并不一定是最优的，因此该模型的基础上又提出了模型二，用邻接矩阵的方法建立模型，该模型能同时找出三者分别达到最优的最佳路线，然后出行者可以根据自身需求找出一个最优路线。而且模型二对问题二的解决也相对容易，只需要在问题一的模型里面添加上可换乘地铁的线路再进行搜索即可。实验结果表明：用模型一对问题一中（1）的最佳路线是：换乘车一次，最短时间为101分钟，车费3元；用模型二不仅可以得出以上结果，还可以得出换乘车二次，最短时间73分钟，车费3元。针对问题二中同时考虑公汽和地铁线路用模型二进行求解，得到线路（6）的最佳路线是：乘T2直接到达，最短时间为20分钟，车费3元，若只乘坐公汽则需要转乘一次，最短时间为65分钟，车费2元，基于大多数乘客考虑显然第一条路线为最佳路线。将模型二进行拓展则可以解决问题三中考虑步行的情况，将问题三中的步行视为第三种可以到达任意站点出行方式，故只需改变邻接矩阵即可找出任意两站点之间的最佳路线。本文运用所建立的模型，基于MATLAB编程设计出一套城市公交自主查询系统，在模型的推广中详细的介绍了该系统。运用该系统输入系统中存储的任意两站点，即可寻找出满足各种不同需求的最佳路线。关键词：公交换乘，邻接矩阵，布尔法则，多目标规划2一、问题的重述与分析1.1背景的分析2004年12月10日，北京市交通委员会副主任刘小明在奥运新闻中心表示，大力发展公共交通是世界各大城市解决交通问题的惟一出路，为了确保北京全面、协调、可持续发展，确保奥运会的顺利举行，北京市计划到2008年，公共交通将占城市出行比例的50％以上，全天候的公交出行比例占40％至42％。刘小明说，公共交通是城市发展过程中能够支持城市高效运转的重要方式，在纽约、东京、巴黎等大城市，公共交通所占的通行比例达到60％以上，而目前北京公共交通仅占城市出行比例的26.5％。对此，北京市政府决定，在发展交通系统方面将给予公共交通，特别是轨道交通更多的优先。刘小明表示，市交通委员会今后将通过建设公交专用道网络和加强改善公交系统运营等措施，在城市中形成准快速的公共交通系统、增强公共交通吸引力，从而实现到2008年公交占城市交通结构40％的预期目标。1.2问题的叙述明年8月第29届奥运会将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具出行。近年城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加便利，但同时也面临多条线路的选择问题。针对市场需求，公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为设计该系统，其核心是线路选择的模型与算法，从实际情况出发考虑，满足查询者的各种不同需求。现要求解决如下三个问题：1）、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762）、同时考虑公汽与地铁线路，解决以上问题。3）、假设又知道所有站点之间的步行时间，要求给出任意两站点之间线路选择问题的数学模型。1.3城市公交网络的特点分析城市中公交线路网是建立在道路网之上,依据道路建立的网络模型并不能直接应用于公交网络,这是因为公交网络与道路网络相比有它的一些特点。连通性在道路网络模型中,通常是将道路交叉点抽象成一个结点,也就是说该结点连接着多条路段,路段与路段之间在该结点处具有连通性。但在公交网络中,如果将公交站点视为结点的话,那么同路公交线路在该点的连通性与不同公交线路在该点的连通性是有差别的,这是因为不同路的公交线在同一站点上的连通是需要换车而增加时间消耗的。另外多条公交线路虽然可以相交于空间上的同一个点,但是该点不一定是公交停靠站点,或者不是同时有停靠点,在这种情况下不同公交线路在这一点也不是连通的。公交站点的特性在公交线路网中,不同的线路上一定会有同名站点,但在公交站点分布的实际情况中,即使3是同名站点也存在空间位置相异的情况。如果将一个公交站点视为一个结点,在进行网络分析时,就要求把空间上相近的异线同名站点合理抽象成一个结点，这样才能模拟不同公交线之间的可换车情况。1.3问题的分析在研究公交网络模型和最优路径算法时,首先要了解公交乘客出行时所考虑的因素,通过对公交乘客出行心理、行为的研究来确定模型的优化目标和约束条件。通常乘客选择出行路线时受到以下几个因素的作用:“换乘次数”、“出行距离”、“出行耗时”、“出行费用”。为满足人们出行的不同需求，本文将换乘次数、出行耗时、出行费用这几个要素综合考虑，建立城市公交网络自主查询系统模型，利用公交网络邻接A矩阵求解，寻求出行的最优路线。针对题目要求的第二问加以考虑地铁，我们同样把它当作公交线路来考虑，只是在站点与费用的计算的时候做相应的处理，如同一地铁站对应的任意两个公交站点视为同一站点，不需要转乘就可以到达。问题三需要我们将步行的情况加以考虑，在我们所建立的模型的基础上，将步行同样也当作一种特殊的交通方式来进行建模，在综合考虑耗时、费用等因素的时候，给出行提供更多的选择方案。二、基本假设与符号说明2.1基本假设1)相邻公汽站和相邻地铁站之间平均行驶时间为定值；2)各公交线路正常运行，不考虑线路阻塞的情况；3)同名站点间距离相同即所需的步行时间相同；4)各线路的人、车流量忽略不计；5)所有公交车发车频率相同；6)不考虑出始站的步行时间；7)环行地铁视为双行线；2.2符号说明符号解释说明A邻接矩阵Si第i个公交站点Lj第j条公交线路P乘车的最低费用T乘车的最短时间N乘车的最小换乘次数n换乘次数Kj1(Si1,Si2)第j1条线路第i1站到第i2站途径公汽站数Mj2(Si3,Si4)第j2条线路第i3站到第i4站途径地铁站数Nj3(Si5,Si6)第j3条线路第i5站到第i6站步行途径站数k1公汽换乘公汽的次数k2地铁换乘地铁的次数k3地铁换乘公汽的次数k4公汽换乘地铁的次数F(x)汽车间隔x站的收费Uj第j次车行驶方向标记4Wj第j次车的计费标准Wj=0为分段计价，Wj=1为单一票价三、模型的建立3.1模型的建立根据上述问题的分析，要找出任意两站点的最佳路线，需建立多目标多约束的优化模型。本文问题的目标函数为：1.换乘次数最少2.出行时间最短3.费用最低其中上述目标函数为通常出行者所最优先考虑的因素，分析各目标函数之间相关联的数学关系，减少目标函数数目或约束条件的数目，依据限定条件，针对具体数据通过挖掘隐含信息降低求解的难度。同时可以根据实际情况分析各目标的权重，去掉影响很小的目标函数从而达到简化的目的。由于数据量太大，本文采用遍历搜寻算法与邻接矩阵公交网络算法相结合的方法找出满足不同需求的目标。3.2基于遍历搜寻算法的模型我们建立站点与车行路线的矩阵A：A=[],式中其中，当车Li在Sj点停靠时，对应元素取值为1，否则取值为0。从题目所给的公交信息进行统计可知，整个北京的公交站点将近4000个，公交线路520条，如此建立的矩阵大小为1040*3957，该矩阵直接表示出个站点的相互联系，可以查询出任意两站是否可以直接到达。对于任意的两个公交站点，我们首先寻找看是否有公交线路可以直接到达，对于可以直接到达的站点，我们直接从矩阵中就可以直接读取出来，即矩阵中对应在该线路上起始点和终点值为1。对于需要换乘才能到达的站点，通过分别查询与起始站点和终点站之间相互联系的中间站点，例如：某乘客需要从站点Si到站点Sj去，中间没有直达车，这是就需要转乘第三辆车Lk，需要第三辆车Lk途经中间站点Sk，连接起始站点Si和终点站Sj。同理，需要经过两次以上换乘才能到达的站点，用同样的算法实现中间站点的搜寻与查找。53.3基于邻接矩阵的算法模型我们建立关于公交线路的邻接矩阵，利用邻接矩阵建立城市公交线路换乘的模型和算法。基于模型，可以研制开发成符合不同乘客需求的城市公交线路自主查询系统。本文主要采用图论中邻接矩阵的思想来寻找最优的乘车路线，下面给出邻接矩阵的概念。邻接矩阵是图论中重要的理论，邻接矩阵和有向图之间有着一一对应的关系，即从邻接矩阵可以画出唯一的有向图，反之，根据有向图可以构造出唯一的邻接矩阵。具体如下：对于有n个要素的系统(P1,P2,P3……Pn)，定义邻接矩阵A:A=[]，式中，=1,0其中，当线段从Pi向着Pj时，，否则值为0。依据邻接矩阵的概念，我们建立了关于城市公交网络的邻接矩阵，具体的算法实现我们选用公交网络的一部分来进行探讨分析。换乘问题的算法实现分为以下两个步骤：1)构造换乘邻接A矩阵，获得出行路线现题目给出北京市共有520条公交线路，任意两条公交线路之间的联系取决于两者之间是否相交（公共的停靠站点），相应的该两条线路之间的矩阵元素值为0或1。因为存在上行与下行的问题，我们把每一条线路都拆分成上下行，这样就把城市公交网络抽象成1040*1040邻接矩阵。为了说明邻接矩阵的算法，我们从中任意选取10条相交线路举例说明。所组成的邻接A矩阵为：A=1000001000110000000101110000010101100001001010000100000100101101001001010100110100000001100010110001该矩阵表明，1路和6路之间有共同的停靠点，也就是1路和6路之间最多经过一次换乘就可以到达目的地，而1路与2路之间没有共同的停靠点，即经过一次换乘无法到达，其他依此类推。邻接矩阵表示了城市各公交线路之间的直接联系，基于此构造一次换乘邻接A矩阵。有些站点通过一次换乘可能不能到达，可能需要两次或者更多。对于该问题，利用邻接矩阵的计算就可以得到解决。具体的算法采用布尔法则运算，即0+0=0，0+1=1,1+1=1;0*0=0,0*1=0，1*1=1;可以得到：6A*A=1101001001111011100111111100011111110001011111000100000101101111111001111111110101010011110111110011*******************************比较与A的区别，可以观察到，用*标记的元素表示由原来的0变为1，即经过两次换乘可以到达。如果两次换乘仍然不能到达的话，第三次换乘，依次类推。通过计算可以得出A=1111111001111111101111111110111111111011111111001101010111111111111011111111111111111111111111110111***********************在我们所建立的大小为1040*1040的换乘邻接A矩阵中，矩阵和之间元素值没有明显的变化，即在网络中，三次转乘与四次转乘相差不大，而且经过三次换乘几乎能够到达所有的站点，相对于整个庞大的公交网络中，可以忽略不计。最后所得到的矩阵就包含了多次换乘关系，以满足各站点的乘车需要