公交网络模型

《公交网络模型》由会员分享，可在线阅读，更多相关《公交网络模型（22页珍藏版）》请在装配图网上搜索。

1、公共交通网络模型公共交通网络模型第一组：刘毅 张学令 郑榕娇摘要北京申奥的成功，给北京的交通带来了巨大的影响。本文就公交线路的选择 问题，采用广度优先搜索的理论与方法建立了公共交通网络模型，并提出了满足 公交乘客各种不同需求的快速算法，针对实际问题给出了最优路径。对于问题（1），首先根据公共交通网络的特点，把公交网络模型映射为一个 无向图来表示公交线路及站点分布情况。结合图论中的广度优先搜索方法并对其 进行改进，即从起点和终点同时搜索，找出起点与终点的所有可行路径（包括直 达、一次换乘、两次换乘的情况），再分别求出每条路径的耗时、花费及换乘次 数进行比较，选出最优路径。对于问题（2），同时考虑

2、公汽与地铁线路时，可以将可换乘的地铁站和公汽 站视为对等的，这样就与第一问相同了，可利用相同的方法来解决。对于问题（3），考虑步行，通过对时间加一个阈值（乘客可以容忍的步行时 间），通过 Floyd 算法求出任意两站点间的最短步行时间，并与阈值进行比较， 建议乘客是否应该步行。该模型的创新点在于克服了广度优先搜索盲目搜索的缺点，采取从起点和终 点同时搜索的方法，大大提高了搜索效率；同时为了更全面的考虑问题，我们分 别以行程耗时、花费与换乘次数为优先考虑，找出了最优路径，以满足公交乘客 的各种不同需求；最后结合乘客都会尽量选择有座位的公交的实际情况对模型进 行了改进。关键词：公交网络，广度最优搜

3、索，最优路径，Floyd算法，MATLAB1. 问题的重述北京申奥的成功，对北京市的交通系统提出了更高的要求。奥运期间交通状 况是否良好，交通管理是否高效，是关系奥运盛会能否圆满成功举办的重要条件 之一。届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具 （简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发 展，北京市的公交线路已达800 条以上，使得公众的出行更加通畅、便利，但同 时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公 交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况 出发

4、考虑，满足查询者的各种不同需求。解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与 算法。并根据相关数据，利用模型与算法，求出以下6对起始站一终到站之间的 最佳路线（要有清晰的评价说明）。（1）、S3359-S1828（2）、S1557-S0481（3）、S0971-S0485（4）、S0008-S0073（5）、S0148-S0485（6）、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的 数学模型。2. 模型的假设与符号说明2.1 模型的假设（1）乘客到达站点时可以直接选择

5、公汽或地铁班次上车，即不考虑乘客在 站点的等待时间。（2）在实际过程中，对于公交（包括公汽与地铁）可能要换车2次以上，用 户已无法容忍，视为无法到达。（因为如果他们之间换乘就使得费用增大了很多， 这是人们不愿意看到的，且一般只坐地铁是无法到达终点站的，所以还要再换乘 其他的工具，换乘次数太大我们也不再将其纳入考虑的范围）。（3）相邻地铁站平均行驶时间（包括停站时间）： 2.5 分钟。（4）相邻公汽站平均行驶时间（包括停站时间）： 3 分钟。（5）公汽换乘公汽平均耗时：5 分钟（其中步行时间 2 分钟）。（6）地铁换乘地铁平均耗时：4 分钟（其中步行时间 2 分钟）。（7）地铁换乘公汽平均耗时：

6、7 分钟（其中步行时间 4 分钟）。（8）公汽换乘地铁平均耗时：6分钟（其中步行时间 4分钟）。（9）公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计 价票价为：020站：1元；2140站：2元；40站以上：3元。（10）地铁票价： 3 元（无论地铁线路间是否换乘）。（11）已知所有站点之间的步行时间。（12）同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付 地铁费）。（13）郊区和繁华地区公交车站的间隔大概一致。2.2 符号说明G = （V, E）表示公交网络无向图；V = * II i n）表示所有节点即公交站点的集合，n为节点数；E二.11 j m如示路段集合

7、，即线路上任意两站点间的一段，m是路段 数；L = l I1 j m表示指定两站点间运行线路的集合；C = I1 j T时，为了满足乘客想转乘次数少的心理， 做进一步判断，若 tiT, 建议乘客步行走完该路段；否则，选择相应的交通工具。4. 模型的建立与求解根据杨新苗等1对公交乘客的出行心理的研究表明，对于公交(包括公汽与地铁)可能要换车2次以上，用户已无法容忍，所以我们仅考虑换乘次数在2次 以内的情况。分别以行程耗时、花费与换乘次数为优先考虑，找出了最优路径， 以满足公交乘客的各种不同需求。对于无特殊要求的乘客，把三个因素视为同等 重要，加和取平均，得出最优路径。4.1 问题(1)模型的建立

8、与求解4.1.1 模型的建立首先，只考虑公汽的情况时，我们将公汽的上、下行看作不同的线路。对于 有n个站点的公交网络，根据公共交通网络的特点，把公交网络模型映射为一个 无向图G二(V,E)来表示公交线路及站点分布情况，并得出相应的n阶邻接矩阵 A =(8 )，其中：rs nxn0,表示r, s站点间无法直达，即没有边相连；5=2rs 1,表示r, s站点间可以直达，有边相连。然后，利用图论中的广度优先搜索算法(Breadth-First-Search)，又译作宽度 优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始， 沿着树的宽度遍历树的节点，如果发现目标，则算法终止。如

9、图 1：但由于BFS是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点， 以寻找结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到 找到结果为止。搜索效率较低。为了提高搜索效率,我们对广度优先搜索算法进行改进，采取从起点（Origin） 和终点（Dstination ）同时搜索，并结合集合的思想，采用两个集合之间逐渐逼 近的搜索方法，在一个庞大的无向交通网络中，寻找可行路径。如图 2：考虑对于任意起点和终点，可能存在以下四种情况：（1）起点和终点在同一线路上，不需要换车（即存在直达路线）；（2）起点和终点不在同一线路上，需要换车 1 次；（3）起点和终点不在同一线路上，需要换

10、车 2 次；（4）起点和终点不在同一线路上，需要换车大于2 次，视为通过换车无法达 到（见模型假设 2）。分别对前三种情况进行搜索。情况 1：直接搜索起点和终点有无一条边直接连接，若有，则说明两站点间 可直达；否则，无法直达。情况2：从起点（Origin）和终点（Dstination）同时搜索其邻接站点，分别 构成集合V和V，判断两集合中是否存在交集，若有交集，则两站点间可通过 OD 一次换乘到达，且交点为一次换乘的中转站点；否则两站点无法通过一次换乘到 达。如图2中，V =V ,V ,V , V =V ,V , V V =V ，则表明起点与终O 1 2 3 D 1 4 O D 1点可通过一次

11、换乘到达，且V为该一次换乘的中转站点。1情况3：从起点和终点同时搜索其邻接站点，分别构成集合V和V，判断两 OD集合中任意两站点V和卩（V V ,V eV ）是否有一条边相连，若有，则说明起 i j i O j D点与终点间可通过两次换乘到达，且V和V为两次换乘的先后中转站点；否则,ij两站点无法通过两次换乘到达。如图 3：从图3中可看出，V与V ,V均有边相连（V,V eV ,V eV ），说明起点与终42323 O 4 D点不仅可通过一次换乘到达，也可通过两次换乘到达，中转站先后分别为V和V24或V和V。34考虑到信息的存贮，我们对每一条连接两站点的边建立一个链表，用于存贮 两邻接站点间的

12、所有通行线路L =（L II j m及线路对应的路段所经过站点 j数CI1 j 20?MjMjL , Cj /输入L/, CCj 40?L :Cj j是M = 2 j开始结束图 4 路段费用计算流程图若从起点到终点，需经过换乘N （Nv3）次，则可计算出所有可行路径的总 耗时S与总花费M，公式如下：S = S + S + S + N5 X（2）12N + 1M 二 M + M + M（3）12N + 1再分别从行程耗时（分）、花费（元）与换乘次数三方面对可行路径进行比 较，针对公交乘客的各种不同需求提供合适路线。最后，对三个因素进行综合考虑，取平均，给出最优路径。max先对行程耗时S、花费M与

13、换乘次数N消除量纲，令：S = SSMMN NNMmaxmax若乘客无特殊要求，把三个因素视为同等重要，则加和取平均，给出最优路 径。Y = S+ M，+ N(5)3Y 值越小，路线最好。4.1.2 模型的求解运用上述算法，我们从搜索出的6对起始站一终到站之间的所有可行路径中 分别以行程耗时、花费与换乘次数为优先考虑，找出了最优路径，并从最优路径 中随机选出了两条线路(若最优路径多于两条以上)，满足乘客的不同需求。最后 综合考虑，对三者进行加权，得出最优路径，乘车公交路线如下：表1S3359-S1828的可行路线起点站班次中转站班次中转站班次终点站时间总费用转乘时间最S3359-L474S20

14、93L201S1783L041S18287332短S3359-L469S2027L201S1783L041S18287332花费最S3359-L436S1784-L167S182810131少S3359-L436S1784-L217S182810131转乘最S3359-L436S1784-L167S182810131少S3359-L436S1784-L217S182810131综合考S3359-L436S1784-L167S182810131虑S3359-L436S1784-L217S182810131表2 S1557-S0481的可行路线起点站班次中转站班次中转站班次终点站时间总费用转乘时间

15、最S1557-L084S1919-L189S3186-L460S048110632短S1557-L363S1919-L189S3186-L460S048110632花费最S1557-L084S1919-L189S3186-L460S048110632少S1557-L363S1919-L189S3186-L460S048110632转乘最S1557-L084S1919-L189S3186-L460S048110632少S1557-L363S1919-L189S3186-L460S048110632综合考S1557-L084S1919-L189S3186-L460S048110632虑S1557-

16、L363S1919-L189S3186-L460S048110632起点站 班次 中转站 班次 中转站 班次 终点站 时间 总费用 转乘时间最 S0971-L013S2517L296S2480-L417S048510632短S0971L094S1609-L140S2654L469S048510632花费最S0971-L013S2184-L417S048512831少转乘最S0971-L013S2184-L417S048512831少综合考S0971-L013S2184-L417S048512831虑表4S0008-S0073的可行路线起点站班次中转站班次中转站班次终点站时间总费用转乘时间最S0

17、008L198S3766L296S2184L345S00736732短花费最S0008-L159S0291-L058S00738321少S0008-L355S2263L345S00738321转乘最S0008-L463S2083L057S00738321少S0008-L159S0491-L058S00738321综合考S0008-L355S2263L345S00738321虑S0008-L463S2083L057S00738321表5S0148-S0485的可行路线起点站班次中转站班次中转站班次终点站时间总费用转乘时间最S0148L308S0036L156S2210-L417S04851063

18、2短S0148L308S0036L156S3332-L417S048510632花费最S0148L308S0036L156S3351-L417S048510632少S0148L308S0036L156S3332-L417S048510632转乘最S0148L308S0036L156S3332-L417S048510632少S0148L308S0036L156S2210-L417S048510632综合考S0148L308S0036L156S3351-L417S048510632虑S0148L308S0036L156S2210-L417S048510632表6 S0087S3676的可行路线起点

19、站班次中转站班次中转站班次终点站时间总费用转乘时间最S0087-L021S0088L231S0427L097S36764632短S0087-L454S0088L231S0427-L462S36764632花费最S0087L454S3496-L209S36766521少转乘最S0087L454S3496-L209S36766521少综合考S0087L454S3496-L209S36766521虑班次前的负号表示该线路为下行线)系统可根据公交乘客对换乘次数、行程耗时与费用的不同要求，并进行综合 考虑，提供合适的路径。该算法的时间复杂度与邻接矩阵的稀疏程度有关，在一般情况下，其时间复杂度为 O(l

20、V I +1 EI)。4.2 问题(2)模型的建立与求解4.2.1 模型的建立因为公汽与地铁之间可以换乘，所以当同时考虑公汽与地铁线路时，可以将 可换乘的地铁站和公汽站视为对等的，这样就与第一问相同了，可利用相同的方 法来解决。地铁站对应的公汽站与同一地铁线路上其他地铁站对应的公汽站彼此间是 可以直达的。女如地铁T1线上的地铁站D01对应公汽站S0567, S0042, S0025, 地铁站D02对应公汽站S1487，则我们认为S1487与S0567, S0042, S0025分 别都是可以直达的,那么5=5=5= 1(S1487,S 0567)(S1487,S0042)(S1487,S002

21、5)相应的n阶邻接矩阵A =(5 )也发生改变，再利用问题(1)的算法进行搜rs nxn索，找出起点与终点的所有可行路径。此外，此时站点数分别与费用和行程耗时的关系发生了变化，需利用新的算 法求解再比较得到最优路线，不同的是换乘情况变得更为复杂。L为中转站的前一线路，L为中转站的后一线路，C在该中转站换乘所需的时间 i j ij换乘所需时间的算法流程图如下：是否否是否6CjL , Cj /L地铁/公汽L地铁/地铁L , C j j是C = 7 i/C = 5 ij输入L, LjC = 4 jLL公汽j j公汽开始结束4.2.2 模型的求解对于前2对指定的起始站f终到站，加入地铁后的所有线路，由

22、于需要换乘 的次数较多，行程耗时较长，超过了人们可以承受的限度，且如果采纳这样的路 线行驶，会使金钱上的花费巨大，所以不采用这类方案，而直接采用一种交通工 具即公汽。那么在这种情况下，它们的最优路线并没有改变，即上面表格统计结 果。针对问题(2),与问题(1)相比，其中第3、4、5、6对起始站f终到站的 乘车线路有些变化：起点站班次中转站班次中转站班次终点站时间总费用转乘时间最S0971L094S0567T1S0464L104S04859652短S0971-L119S0567T1S0466L051S04859652花费最S0971-L013S2184-L417S048512831少转乘最S09

23、71-L013S2184-L417S048512831少综合考S0971-L013S2184-L417S048512831虑表8S0008-S0073的可行路线起点站班次中转站班次中转站班次终点站时间总费用转乘时间最S0008-L150S3874T2S0525L103S00735552短S0008-L159S3874T2S0525L103S00735552花费最S0008-L159S0291-L058S00738321少S0008-L355S2263L345S00738321转乘最S0008-L463S2083L057S00738321少S0008-L159S0491-L058S0073832

24、1综合考S0008-L355S2263L345S00738321虑S0008-L463S2083L057S00738321表9S0148-S0485的可行路线起点站班次中转站班次中转站班次终点站时间总费用转乘时间最S0148-L024S1487T1S0464-L469S048587.552短S0148-L024S1487T1S0466-L450S048587.552花费最S0148L308S0036L156S3351-L417S048510632少S0148L308S0036L156S3332-L417S048510632转乘最S0148-L024S1487T1S0464L104S048587

25、.552少S0148-L024S1487T1S0466L051S048587.552综合考S0148L308S0036L156S3351-L417S048510632虑S0148L308S0036L156S2210-L417S048510632起点站 班次 中转站 班次 中转站 班次 终点站 时间 总费用 转乘花费最S0087L454S3496-L209S36766521时间最 S0087 T2短S36762530少转乘最S0087T2S36762530少综合考S0087T2S36762530虑班次 T1、T2 为地铁线路）4.3 问题（3）模型的建立与求解最后，考虑步行,通过调查对时间加一个

26、阈值T（乘客可以容忍的步行时间）。 在第二问算法基础上求出任意两站点间的最优路径，通过Floyd算法求出路径上 每个路段及从起点到终点的最短步行时间，分别为ti和t。若求出两点间的最短步行时间tT时，为了满足乘 客想转乘次数少的心理，做进一步判断，若 ti52 0 对地铁的处理if route(route_len).RouteLength=0route(route_len).Money=0;route(route_len).Time=8二个公交站经过地铁站转走的时间elseroute(route_len).Time=route(route_len).RouteLength*2.5; route

27、(route_len).Money=3;endelseif dat a(2+(abs(ro ut e(ro ut e_len).CarNumber)-1)*4,1)=1111%寸单程 记票的公交车处理route(route_len).Time=route(route_len).RouteLength*3; route(route_len).Money=1;else%寸分段计票的公交车的处理route(route_len).Time=route(route_len).RouteLength*3;route(route_len).Money=ceil(route(route_len).RouteLength/20); if route(route_len).Money3route(route_len).Money=3;endendif string=.break;endendfunction change_time=change_bus(carnum1,carnum2)if carnum1=520 &carnum2520 &carnum2520% 地铁转地铁change_time=4;elseif carnum1520 & carnum2=52 0% 地铁转公汽change_time=7;else%公汽转地铁change_time=6;end