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

城市公交自主查询系统模型摘要：明年8月第29届奥运会将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具出行。网络的普及，如果能预先了解出行的最佳路线，那对出行者尤其是对外地游人来说就带来了极大方便。但是通常乘客选择出行路线时受到以下几个因素的作用:“换乘次数”、“出行距离”、“出行耗时”、“出行费用”等。因此，本文针对出行者的自身需求给出了求解最佳路线的数学模型。由于最佳路线受以上几个因素的影响，所以本文提出了两个数学模型分别求解出最优解。模型一是优先考虑最优的换乘次数，再找最短时间，再求最少费用。但从实际情况考虑这个模型并不一定是最优的，因此该模型的基础上又提出了模型二，用邻接矩阵的方法建立模型，该模型能同时找出三者分别达到最优的最佳路线，然后出行者可以根据自身需求找出一个最优路线。而且模型二对问题二的解决也相对容易，只需要在问题一的模型里面添加上可换乘地铁的线路再进行搜索即可。实验结果表明：用模型一对问题一中（1）的最佳路线是：换乘车一次，最短时间为101分钟，车费3元；用模型二不仅可以得出以上结果，还可以得出换乘车二次，最短时间73分钟，车费3元。针对问题二中同时考虑公汽和地铁线路用模型二进行求解，得到线路（6）的最佳路线是：乘T2直接到达，最短时间为20分钟，车费3元，若只乘坐公汽则需要转乘一次，最短时间为65分钟，车费2元，基于大多数乘客考虑显然第一条路线为最佳路线。将模型二进行拓展则可以解决问题三中考虑步行的情况，将问题三中的步行视为第三种可以到达任意站点出行方式，故只需改变邻接矩阵即可找出任意两站点之间的最佳路线。本文运用所建立的模型，基于MATLAB编程设计出一套城市公交自主查询系统，在模型的推广中详细的介绍了该系统。运用该系统输入系统中存储的任意两站点，即可寻找出满足各种不同需求的最佳路线。关键词：公交换乘，邻接矩阵，布尔法则，多目标规划一、 问题的重述与分析1.1 背景的分析2004年12月10日，北京市交通委员会副主任刘小明在奥运新闻中心表示，大力发展公共交通是世界各大城市解决交通问题的惟一出路，为了确保北京全面、协调、可持续发展，确保奥运会的顺利举行，北京市计划到2008年，公共交通将占城市出行比例的50以上，全天候的公交出行比例占40至42。刘小明说，公共交通是城市发展过程中能够支持城市高效运转的重要方式，在纽约、东京、巴黎等大城市，公共交通所占的通行比例达到60以上，而目前北京公共交通仅占城市出行比例的26.5。对此，北京市政府决定，在发展交通系统方面将给予公共交通，特别是轨道交通更多的优先。刘小明表示，市交通委员会今后将通过建设公交专用道网络和加强改善公交系统运营等措施，在城市中形成准快速的公共交通系统、增强公共交通吸引力，从而实现到2008年公交占城市交通结构40的预期目标。1.2 问题的叙述明年8月第29届奥运会将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具出行。近年城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加便利，但同时也面临多条线路的选择问题。针对市场需求，公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为设计该系统，其核心是线路选择的模型与算法，从实际情况出发考虑，满足查询者的各种不同需求。现要求解决如下三个问题：1）、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762）、同时考虑公汽与地铁线路，解决以上问题。3）、假设又知道所有站点之间的步行时间，要求给出任意两站点之间线路选择问题的数学模型。1.3 城市公交网络的特点分析城市中公交线路网是建立在道路网之上,依据道路建立的网络模型并不能直接应用于公交网络,这是因为公交网络与道路网络相比有它的一些特点。l 连通性在道路网络模型中,通常是将道路交叉点抽象成一个结点,也就是说该结点连接着多条路段,路段与路段之间在该结点处具有连通性。但在公交网络中,如果将公交站点视为结点的话,那么同路公交线路在该点的连通性与不同公交线路在该点的连通性是有差别的,这是因为不同路的公交线在同一站点上的连通是需要换车而增加时间消耗的。另外多条公交线路虽然可以相交于空间上的同一个点,但是该点不一定是公交停靠站点,或者不是同时有停靠点,在这种情况下不同公交线路在这一点也不是连通的。l 公交站点的特性在公交线路网中,不同的线路上一定会有同名站点,但在公交站点分布的实际情况中,即使是同名站点也存在空间位置相异的情况。如果将一个公交站点视为一个结点,在进行网络分析时,就要求把空间上相近的异线同名站点合理抽象成一个结点，这样才能模拟不同公交线之间的可换车情况。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次车行驶方向标记Wj第j次车的计费标准Wj=0为分段计价，Wj=1为单一票价三、 模型的建立3.1 模型的建立根据上述问题的分析，要找出任意两站点的最佳路线，需建立多目标多约束的优化模型。本文问题的目标函数为：1.换乘次数最少N=minn2.出行时间最短T=minj1=0n13kj1Si1,Si2+j2=0n22.5Mj2Si3,Si4+j3=0Nj3Si5,Si6+5k1+4k2+7k3+6k4 其中 k1+k2+k3+k4=nk1+k2+k3+k403.费用最低P=f(Kj1Si1,Si2;Wj=01;Wj=1+0 ; Mj2Si3,Si4=03; Mj2Si3,Si40其中fx=3,x402,40x201,20x上述目标函数为通常出行者所最优先考虑的因素，分析各目标函数之间相关联的数学关系，减少目标函数数目或约束条件的数目，依据限定条件，针对具体数据通过挖掘隐含信息降低求解的难度。同时可以根据实际情况分析各目标的权重，去掉影响很小的目标函数从而达到简化的目的。由于数据量太大，本文采用遍历搜寻算法与邻接矩阵公交网络算法相结合的方法找出满足不同需求的目标。3.2 基于遍历搜寻算法的模型我们建立站点与车行路线的矩阵A：A=ai,j,式中 ai,j=1，0 其中，当车Li在Sj点停靠时，对应元素取值为1，否则取值为0。从题目所给的公交信息进行统计可知，整个北京的公交站点将近4000个，公交线路520条，如此建立的矩阵大小为1040*3957，该矩阵直接表示出个站点的相互联系，可以查询出任意两站是否可以直接到达。对于任意的两个公交站点，我们首先寻找看是否有公交线路可以直接到达，对于可以直接到达的站点，我们直接从矩阵中就可以直接读取出来，即矩阵中对应在该线路上起始点和终点值为1。对于需要换乘才能到达的站点，通过分别查询与起始站点和终点站之间相互联系的中间站点，例如：某乘客需要从站点Si到站点Sj去，中间没有直达车，这是就需要转乘第三辆车Lk，需要第三辆车Lk途经中间站点Sk，连接起始站点Si和终点站Sj。同理，需要经过两次以上换乘才能到达的站点，用同样的算法实现中间站点的搜寻与查找。3.3 基于邻接矩阵的算法模型我们建立关于公交线路的邻接矩阵，利用邻接矩阵建立城市公交线路换乘的模型和算法。基于模型，可以研制开发成符合不同乘客需求的城市公交线路自主查询系统。本文主要采用图论中邻接矩阵的思想来寻找最优的乘车路线，下面给出邻接矩阵的概念。邻接矩阵是图论中重要的理论，邻接矩阵和有向图之间有着一一对应的关系，即从邻接矩阵可以画出唯一的有向图，反之，根据有向图可以构造出唯一的邻接矩阵。具体如下：对于有n个要素的系统(P1,P2,P3Pn)，定义邻接矩阵A:A=ai,j，式中，ai,j=1,0 其中，当线段从Pi向着Pj时，ai,j=1，否则值为0。依据邻接矩阵的概念，我们建立了关于城市公交网络的邻接矩阵，具体的算法实现我们选用公交网络的一部分来进行探讨分析。换乘问题的算法实现分为以下两个步骤：1) 构造换乘邻接A矩阵，获得出行路线现题目给出北京市共有520条公交线路，任意两条公交线路之间的联系取决于两者之间是否相交（公共的停靠站点），相应的该两条线路之间的矩阵元素值为0或1。因为存在上行与下行的问题，我们把每一条线路都拆分成上下行，这样就把城市公交网络抽象成1040*1040邻接矩阵。为了说明邻接矩阵的算法，我们从中任意选取10条相交线路举例说明。所组成的邻接A矩阵为：A=该矩阵表明，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;可以得到：A2=A*A=比较A2与A的区别，可以观察到，用*标记的元素表示由原来的0变为1，即经过两次换乘可以到达。如果两次换乘仍然不能到达的话，第三次换乘A3=A2*A，依次类推。通过计算可以得出A3=A2*A=在我们所建立的大小为1040*1040的换乘邻接A矩阵中，矩阵A4和A3之间元素值没有明显的变化，即在网络中，三次转乘与四次转乘相差不大，而且经过三次换乘几乎能够到达所有的站点，相对于整个庞大的公交网络中，可以忽略不计。最后所得到的矩阵就包含了多次换乘关系，以满足各站点的乘车需要。到此，第一步的换乘邻接A矩阵已经构造完成。2) 换乘站点的搜寻通过换乘邻接A矩阵，我们可以找到出行的路线，该结果为r次换乘情况下的线路，由于可选线路条数较多，所以在这个基础上，我们对线路进行采样抽取，然后综合考虑换乘次数、出行耗时、费用等因素，从中选取最优路线。3) 上行下行以及环行的处理读取原数据，将上行下行等参数作为Uj参数储存，其中1为双线行驶，2为上行，3为下行，4为环行。在搜索出可能的线路后利用Kj1(Si1,Si2)进行途径站数的统计，如果是双线为Si1-Si2的绝对值，如果为2、3，则将Si1，Si2在线路j中比较大小，如果Si1在Si2的下行，说明该线路方向错误，该途径错误。4) 花费的处理查询Wj，确定该线路的计费方式，如果Wj=1，该线路票价直接为1元，如果Wj=0，则带入函数Kj1（Si1，Si2）求出途径站点个数，利用f(x)求出花费，特别的对于地铁线，起始点如果是同一地铁口，其花费为零，途径站点个数也处理成零，否则票价为3元。四、 模型的求解我们在建立模型的过程中，尝试了如下两种方法，最终选择第二种方法进行建模。现简单介绍两种算法。4.1 方法一：遍历搜寻算法首先制作公交路线网络图用（0-1矩阵表示）将城市的所有公交站点和公交线路转化为下列元素为0、1 的数表(举例)。S1S2S3S4S5S6S7S8S9L1101010001L2000100101L3111010010L4000110000L5010000111L6000011000L7101100101L8000010000L9010001000表一 公交路线网络图表举例其中,Li表示公交路线,Sj表示停车点,表中矩阵元素Wij值为0或1,如果Wij=0则表示Li在Sj不停,如果Wij=1则表示Li在Sj停靠。由此表可以看出该城市的所有公交路线在所有停车点的状态，基于此矩阵来找乘车路线。具体的算法步骤如下：1) 查找否存在LkL1,L2,Lf,使得Wki=Wkj=1，如果存在,则说明只要乘车一次就可到达目的地，乘车路线为:Si-Lk-Sj,其中Lk满足Wki=Wkj=1。2)如果1)不成立,则需要换车，搜索集合SS1=L1,L2,Lf,SS2=S1,S2,Sh，看是否存在Sj1SS2,Li1、Li2SS1,满足:Wi1,j=Wi1,j1=1,Wi2,j1=Wi2,j=1。如果存在,则说明需乘车两次(换车一次),即可到达目的地，乘车路线为: Si-Li1-Sj-1Li2-Sj。3)如果1),2)都不行,说明需要换乘至少两次或以上。搜索集合SS1=L1,L2,Lf,SS2=S1,S2,Sh，看是否存在Sj1,Sj2SS2,Li1,Li2,Li3SS1,满足:Wi1,i=Wi1,j1=1,Wi2,j1=Wi2,j2=1,Wi3,j2=Wi3,j=1。如果存在,则说明只需乘车三次(换车两次)即可达到目的地。乘车路线为: Si-Li1-Sj1-Li2-Sj2-Li3-Sj。4)如果前面的操作都不行,则说明需要乘车至少四次(换车三次)，具体的求解步骤与前面的步骤完全相同,可类似进行。但是该算法并不适用于城市公交自助查询系统，究其原因有如下几点：1. 数据结构复杂公交网络在结点和连通性上有它的特殊性，这也是它不同于道路网络的原因之所在，如果采用上述算法，共有520条公交线路，不包括上下行，3957个站点，所建立的公交网络矩阵数据结构将是非常复杂的。2. 运算时间长该算法的一个基本思想就是遍历搜寻，在一个如此复杂的数据结构中寻找其中一个元素，特别是在换乘两次或以上的时候，将占用大量的计算机内存，同时大矩阵运算起来也是相当费时的。3. 公交转乘的特殊性随着公交网络的日益完善，使得交通更加便捷、迅速，各公交站点的换乘更加方便。例如题中所给的从站点S3359到站点S1828，可以选择坐L436到S1784转乘L167到达终点；也可以选择坐L015到S1327转乘L201，然后在S0485转乘L041同样也可以到达，从表面上看，后者转乘两次看似复杂，但第一种方案途经32站，需要101min，而第二条方案仅途经22站，耗时76min，极大的节约了出行时间，而两种方案所花费都是3元，综合考虑，选第二种方案更优。又例如题中从站点S0971至站点S0485，现提供两种方案对比：乘坐L013在S2184转乘L417，途经41站；另外就是乘L310在S3693转乘L017，然后在S2082转乘L450，途经39站点；两种方案均是花费3元，综合考虑，选第一种方案换乘次数最少反而更符合实际。综上所述，考虑到该算法的不足，提出了更加简洁的基于邻接A矩阵的换乘算法。4.2方法二：基于邻接A矩阵的换乘算法基于上述有关邻接A矩阵的介绍说明，我们建立关于城市公交网络的邻接A矩阵。在题目数据文件中所提供的520条公交线路中，有409条分上下行路线，89条往返线路，22条环形线路，为了方便建立邻接A矩阵，我们将每一条线路都假设成上下行两条有方向的线路，按照邻接矩阵的概念，建立大小为1040*1040的公交网络邻接A矩阵。该A矩阵为是非对称矩阵，这就很好的解决了上行与下行线路选择的问题。在A矩阵中，任意两条线路若相交，则对应元素值为1，否则为0。该矩阵直接表示了任意两条公交线路之间的直接联系，对于一次换乘能够到达的站点很容易就能够搜索出来。并非所有的公交站点经过一次换乘都能够到达，这就需要我们二次换乘或多次。根据前述布尔法则，进行A*A运算，我们将得到的A2矩阵记录至算法中，方便查询。二次换乘中，因为经过两个换乘点，而在换乘A2矩阵中所表示出来的只是开始和最后所选择的路线，并未将中间的一次车表示出来，造成此结果的原因就是布尔法则中1+1=1这一条，所以在二次换乘过程中，即进行乘方的时候，我们需要标记出这一点，而这一点记录了中间一次路线的关键信息，是二次换乘的关键点之所在，同时也是该模型的一个核心点。我们也做了A3矩阵，并且和A2进行了比较，结果发现几乎所有元素值A（i，j）为1，也就是说，经过二次换乘，对于绝大部分站点均能达到，这也符合实际情况，而且并未考虑地铁，所有说，我们限定转乘次数为2。经过程序的运行求解，我们发现在二次换乘的情况下，可以有很多种方案，其中一部分在同一条线路的不同站点换乘，中间相差的站点很少，而且对费用没有产生影响。分析原因是因为城市公交系统中各线路为平行或者垂直，没有弯曲交缠。在这种情况下，我们对线路进行采样，以减少计算量。我们对采样前后的数据进行对比，以保证采样的合理有效性。我们根据相同线路减少取样数目，保证每一条线路都能兼顾的原则进行采样，前后数据分布图如下：图一 二次换乘所有不同中转站的途经站数及其部分抽样从两图的直观对比中可以看出，采样后的数据保留了所需的特征量，速度约是以前的十倍的左右，计算速度有相当高的提升。但由于采样时没能继续将可能包含最有解的线路组合继续求出最佳换乘地点，因此在使用本优化的情况下，所求最佳路线在线路上准确，换成地点存在偏差，误差平均在3站之内。由此可见使用部分采样数据是合理的。输入起点、终点数据公交线路网络表构建T矩阵一次换乘利用An求n次换乘搜索出可直达的所有列车输出不同目标的最佳方案开始结束输出所有方案图二、换乘算法流程图具体的搜索算法流程如图二所示：最终，经过Matlab编程实现算法，求得最优出行路线如下：线路换乘次数（次）最短时间（分钟）费用（元）线路及途径站点S3359S182811013先乘L436到S1784站转乘L167到S1828站2733先乘L015到S2903站转乘L201到S0485站再转乘L041到S1828站S1557S048121063先乘L084到S1919站转乘L189到S1386站再转乘L460到S0481站S0971S048511283先乘L013到S2184站转乘L417到S0485站2*1153先乘L013到S1609站转乘L140到S2654站再转乘L104到S0485站S0008S00731*832先乘L159到S0291站转乘L058到S0073站2793先乘L200到S0778站转乘L099到S2633站再转乘L474到S0073站S0148S048521063先乘L308到S0036站转乘L156到S2210站再转乘L417到S0485站S0087S36761652先乘L454到S3496站转乘L209到S3676站2*463先乘L021到S0088站转乘L231到S0427站再转乘L097到S3676站表二 问题一最优乘车方案表中的六条线路中用*标注的表示该线路在换乘次数、最短时间、费用相同的情况下存在多条最佳路线，各线路的其他最优路线如下：S0971S0485先乘L013到S1609站转乘L140到S3037站再转乘L104到S0485S0008S0073先乘L159到S0491（S2683或S3614）站转乘L058到S0073站先乘L159到S0400（S2633或S3053）站转乘L474到S0073站先乘L355到S2263（S2303或S3917）站转乘L345到S0073站先乘L463到S2038站转乘L057到S0073站S0087S3676先乘L021到S0088站转乘L231到S0427站再转乘L462到S3676先乘L206到S0088站转乘L231到S0427站再转乘L462到S3676先乘L206到S0088站转乘L231到S0427站再转乘L097到S3676通过对表中六条路线的分析，我们可以依据不同的乘客需求选择不同的出行路线，如线路一中在费用相同的情况下，若以时间最短为目标就可选择换乘两次的车次，反之，若以换乘次数最少为目标就可选择乘车时间稍长点的车次。表中的第四条路线的一次换乘和二次换乘都具有多条相同时间相同费用的最优路线，只是各条路线的换乘站点有所不同。对于题目中要求的第二问，加入考虑地铁的情况，我们将地铁线路编加到公交网络邻接矩阵，对于站点和费用等要素重新考虑。矩阵转变如下：S0001S0619S3957L001010L1051.0L520000T1000T2000L001L105L520T1T2步行L001100001L105010001L520001001T1000111T2000111表三 问题一到问题二的算法转换图根据题目中附录中的所给出的信息，地铁站对应的任意两个公汽站点可以通过地铁换乘，而不需要计算费用，我们将这几个对应的公汽站看作是同一站点处理来进行模型求解，最终得到的最优路线如下：表中的六条线路中用*标注的表示该线路在换乘次数、最短时间、费用相同的情况下存在多条最佳路线，S0148S0485先乘L204到S1487站转乘T1到S0464站再转乘L104到S0485先乘L204到S1487站转乘T1到S0464站再转乘L395到S0485各线路的其他最优路线同表二。由表中的数据可知，搭乘地铁较搭乘公汽省时的多。针对路线（6）在费用相同的情况下，搭乘地铁应为该线所有线路中的最优路线，若不考虑换乘次数和出行时间则乘坐公汽比乘坐地铁省钱。基于决大多数乘客的多方面综合因素考虑线路（6）的最佳路线是从起点站乘T2直达终点站。线路换乘次数（次）最短时间（分钟）费用（元）线路及途径站点S3359S182811013先乘L436到S1784站转乘L167到S1828站2733先乘L015到S2903站转乘L201到S0485站再转乘L041到S1828站S1557S048121063先乘L084到S1919站转乘L189到S1386站再转乘L460到S0481站S0971S048511283先乘L013到S2184站转乘L417到S0485站2*1153先乘L013到S1609站转乘L140到S2654站再转乘L104到S0485站S0008S00731*832先乘L159到S0291站转乘L058到S0073站2793先乘L200到S0778站转乘L099到S2633站再转乘L474到S0073站S0148S048521063先乘L308到S0036站转乘L156到S2210站再转乘L417到S0485站2*87.55先乘L204到S1487站转乘T1到S0466站再转乘L051到S0485站S0087S36761652先乘L454到S3496站转乘L209到S3676站2*463先乘L021到S0088站转乘L231到S0427站再转乘L097到S3676站0203乘 T2直接到达表四 问题二最优乘车方案题中第三问假设知道所有站点之间的步行时间，我们将步行也当作一种特殊的交通方式来进行处理。仍然是基于我们所建立的公交自主查询系统模型，在之前建立的邻接矩阵中加入步行这一特殊的交通方式，因为可以在任意站点之间采用步行的方式，所以在元素取值上，所有的值均为1。矩阵转换如下：S0001S0619S3957L001010L1051.0L520000T1000T2000步行111L001L105L520T1T2步行L001100001L105010001L520001001T1000111T2000111步行111111表五 问题二到问题三的算法转换图多一种方式，就可能会多一种出行方案的选择。假设我们知道所有站点之间的步行时间，在所有的方案当中，综合考虑时间、换乘、费用这些关键因素，在所有的可行解当中选择最优的方案。算法方面，仍然可以采用邻接矩阵的算法。五、 模型的评价及改进方向本文在分析了一般公共交通的特点和乘客出行心理的基础上，综合考虑以换乘次数、出行时间即途经站数以及出行费用这些因素，建立了城市公交自助查询系统模型，研究了以城市为背景的公交网络优化求解问题。在简单情形下，可以通过公交线路网络矩阵,很容易得到最短乘车路线。在多目的的情况下，通过构造局部网络图，通过计算机程序化,从而可以迅速、方便地得到所需的解。应用此方法,可以方便乘客查找最佳的乘车线路，也可以综合应用此方法对城市的公交线路网络图的性能状况进行评估分析，为公交线路的结构进一步改进提供建议。在拥有近4000多个站点的公交有向图中,实施在寻求任意给出的两个站点之间最少换车询问时，的确体现出优异快捷的运算速度,收到了良好的效果。然而，该算法属于理想化算法，目前尚有许多问题,如多个可行出行点、非线性费用结构、个人偏好等 ,都需进一步研究。在多次换乘的情况下，由于需要记录中间的换乘线路，相应的增加了计算量。本模型可以应用于城市中的公交查询系统，可以满足不同需求的乘客要求，以换乘次数，乘车时间，乘车费用等不同方面为目的的最优线路均可通过本模型制造的系统进行查询。同时本模型还支持换乘次数较多的线路查找，且查找迅速准确，从而满足旅游者的需求。特别是针对大城市站点多线路多的特点，运用邻接矩阵解决了由于该问题引起的运算量大的问题。运用本模型我们制作了一套基于MATLAB的人机交互的城市公交查询系统，查询者只需按照界面提示输入目标站点（起始站和终点站），即可找出多条公交线路，查询者还可以自定义搜索深度（换乘次数）和目标数目（所需线路条数），从而满足查询者的不同需求。该系统的操作界面举例：参考文献：1 马良河，刘信斌，廖大庆，城市公交线路网络图的最短路与乘车路线问题，数学的实践与认识，第34卷第6期，2004年6月2 赵巧霞，马志强，张发，以最小换乘次数和站数为目标的公交出行算法，计算机应用，第24 卷第12 期，2004 年12 月3 王建林，基于换乘次数最少的城市公交网络最优路径算法，经济地理；第25 卷第5 期，2005 年9 月4 王振军，王宁宁，李鸿，牛洪亮，基于邻接矩阵的公交换乘算法的研究，徐州工程学院院报，第21卷第3期，2006年3月附录主程序：main.mclc;qui=0; %退出标记fw=0;shendu=1;shum=10;tujins=1;while qui=0 if tujins=1 ask=input(请输入您要的最有路线，1为换乘次数最少，2为时间最短，3为花费最少:n); A,I=sort(tujin); output(tujin(I(1,ask),:); fprintf(n以下为三种类型的最有路线n最少换乘线路:n); output(tujin(I(1,1),:); fprintf(最短时间线路n); output(tujin(I(1,2),:); fprintf(最少花费线路n); output(tujin(I(1,3),:); tujins=1; end flag=0; fprintf(n-乘公交看奥运-北京公交查询系统-n);cho=input(本查询系统默认为仅查询10条一次换乘以内的公交线，设置输入 0，退出请按 -1n请输入查询的起点站：n);switch cho case 0 fw=input(请输入查询范围，0为公交线，1为地铁公交线：n); shendu=input(请输入查询深度,1为一次换乘以内，2为二次换乘以内：n); shum=input(请输入需要查询的目标个数：n); case -1 qui=1; otherwise qidian=cho; if fw=0 load shuju1; fanwei=1040; else load shuju2; fanwei=1044; end if fw=0 f=公交线; else f=地铁公交线; end zhongdian=input(请输入终点:n); fprintf(您查询的线路为%s到%s，目标为%s 搜索深度为:%d，目标个数限制%dnWaiting.n,dz(qidian),dz(zhongdian),f,shendu,shum); shumu=shum+1; save shuju;%途径：tujin(1.换乘次数,2.途径站数,3.花费,4.换乘车辆1,5.换乘站1,.)%途径个数tujinstujin=;tujins=1;tjtemp=1;%直接到达的for i=find(gw2(:,qidian) if gw2(i,zhongdian)=1 & gs(i,qidian,zhongdian)=-1 %找到直达车 i为换乘列车所在行 tujin(tujins,1)=1; tujin(tujins,2)=gs(i,qidian,zhongdian); tujin(tujins,3)=money(i,qidian,zhongdian); tujin(tujins,4)=i; output(tujin(tujins,:); if tujinsshumu flag=9; break; end tujins=tujins+1; end if flag=9 break; endendif tjtemp=tujins fprintf(Sorry,没有直达车，Waiting.n)end tjtemp=tujins; %换乘1次 使用T矩阵%起点终点所有列车行fbg=;fed=;%遍历可能地起始汽车x=1;for i=1:fanwei if sum(cell2mat(strfind(g(i),dz(qidian)0 fbg(1,x)=i; x=x+1; endend%遍历终点汽车x=1;for i=1:fanwei if sum(cell2mat(strfind(g(i),dz(zhongdian)0 fed(1,x)=i; x=x+1; endend%起始与终点的T矩阵检验for i=fbg if flag=9 break; end for j=fed if gn(i,1)=gn(j,1) if t0(i,j)=1 %找到相交汽车线路 第i行，第j列；继续查找相交位置 temp=(gw2(i,:).*gw2(j,:); for k=find(temp) if gs(i,qidian,k)=-1 & gs(j,k,zhongdian)=-1 tujin(tujins,1)=2; tujin(tujins,2)=gs(i,qidian,k)+gs(j,k,zhongdian); tujin(tujins,3)=money(i,qidian,k)+money(j,k,zhongdian); tujin(tujins,4)=i; tujin(tujins,5)=k; tujin(tujins,6)=j; if tujinsshumu flag=9; break; end output(tujin(tujins,:); tujins=tujins+1; end if flag=9 break; end end if flag=9 break; end end if flag=9 break; end end if flag=9 break; end end if flag=9 break; endendif tjtemp=tujins fprintf(Sorry,没有一次换乘的汽车，Waiting.n)endif shendu=2 |flag=9 continue;end%二次换乘tjtemp=tujins;%起点终点所有列车行fbg=;fed=;%遍历可能地起始汽车x=1;for i=1:fanwei if sum(cell2mat(strfind(g(i),dz(qidian)0 fbg(1,x)=i; x=x+1; endend%遍历终点汽车x=1;for i=1:fanwei if sum(cell2mat(strfind(g(i),dz(zhongdian)0 fed(1,x)=i; x=x+1; endend%起始与终点的T矩阵检验for i=fbg if flag=9 break; end for j=fed if flag=9 break; end if gn(i,1)=gn(j,1) if flag=9 break; end if