乘公交看奥运方案设计

1、承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的

2、全名） 黔南民族师范学院 参赛队员 (打印并签名) ：1. 曹龙 2. 彭开连 3. 陈勇 指导教师或指导教师组负责人 (打印并签名)： 薛先贵 日期： 2011年 8 月 15 日乘公交,看奥运摘要:本文将公交线路（3957个公汽站点和520条公汽线路、39个地铁站点和2条地铁线路、地铁与公汽间转换关系）关系抽象为有向赋权图，并建立时间直达矩阵、费用直达矩阵、换乘直达线路数矩阵，利用最短路模型、搜索法及0-1整数规划模型进行解答。对于问题一，在只考虑公汽的情况下，我们用修改floyd算法求出最小转乘次数、最少费用、最少时间，并由搜索法得出最优线路；对于问题二，在考虑公汽和地铁的情况下，同样，

3、我们也用修改floyd算法求出最小转乘次数、最少费用、最少时间，并由搜索法得出最优线路；对于第三问题，我们则需要考虑步行时间进去，在问题二的基础上并利用0-1整数规划模型进行优化组合取得最优线路。关键字:线路选择 有向赋权图 修改floyd算法 搜索法 优化模型一、问题重述:奥运会是世界上举行的一项重大的赛事活动.第29届奥运会明年8月将在我国北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。近年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需

4、求，我们准备研制开发一个解决公交线路选择问题的自主查询计算机系统,关键在于线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。具体问题如下:1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给

5、出任意两站点之间线路选择问题的数学模型。基本时间参数设定:相邻公汽站平均行驶时间(包括停站时间)相邻地铁站平均行驶时间(包括停站时间)公汽换公汽平均耗时/(步行时间)地铁换地铁平均耗时/(步行时间)公汽换地铁平均耗时/(步行时间)地铁换公汽平均耗时/(步行时间)时间(分钟)32.55/(2)4/(2)6/(4)7/(4)即:换乘公汽等待分钟，换乘地铁等待分钟.公汽站地铁站（通道）公汽站.换乘耗时11分钟：步行4+4=8分钟, 等车3分钟.公交票价方式基本票价参数设定:单一计价分段计价公汽1元020站：1元；2140站：2元；40站以上：3元地铁3元（无论地铁线路间是否换乘）公交线路及相关信息

6、（见数据文件B2007data.rar）二、问题分析: 本论文主要研究公交线路选择的问题，即要求:a 如何换车.b 车与车之间的关系.c 满足乘车人关心的问题： 1）换乘次数最少； 2）费用最低； 3）时间最短（初始等车时间2(3)min也不包括在内，最后结果可加 上。）； . 在众多的条件中，为了切合人们的实际需要，优先考虑是否有直达,若无直达公汽,则我们主要从最方便、最经济、最快捷等出发，建立以换乘次数、费用、时间为最优的数学模型。三、模型假设:1、所有公交线路的每天的工作始末时间相同;2、公汽、地铁均到站停车;3、各公交车都运行正常，不会发生堵车现象;4、环线可以看作以任意站作为起点站和

7、终点站，并且是双向的,并且经过终点后 要重新收费;5、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费；6、人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度;7 初始等车时间2(或3)min也不包括在内;8、 同一公交线的往返路线视为两条单行线;9、 考虑两地铁之间不通过公汽乘换（即只：公汽站地铁站（通道）公汽站）。四、模型建立: 对于公交线路选择，我们主要考、虑乘换次数、费用、时间各因素最优。 在线路选择问题中，将公交路线关系抽象成一个有向赋权图，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为：。表示由i直达j

8、付出的代价，可以为时间或费用 (不包括换乘代价；多条线路可达时只保留最小代价)； 公交乘换方式：公汽公汽，公汽地铁，地铁公汽，地铁地铁，公汽地铁公汽。 A） i站点是公汽站点，j站点为地铁站点：（1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则 =;（2） 若j站点对应的换乘（公汽）站点k, 可从i站点直达k，则费用为 = ； 注：对于时间则需要加上k到j的步行时间. (若有多种选择，取最小成本者即可)B） j站点是公汽站点，i站点为地铁站点：（1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则 =. （2）若从i站点对应的换乘(公汽)站

9、点k，能直达j站点， 则费用为 =；注：对于时间则需要加上i到k的步行时间.定义：矩阵算子“”如下：设D（k-1）、D均为n阶方阵， D(k) = D（k-1） D (考虑换乘代价)当考虑费用矩阵间的运算时，=0；当考虑时间矩阵间的运算时，表示在k的换乘时间。 D(k)= D(k-1)D表示k次换乘的最低代价(费用或时间)，即通过修改floyd算法求解。i,j,k表示换乘时间 ：i = j 或k = i，j时，i,j,k = 0其他情形：若不可换乘(当i ，j为公汽站点而k为地铁站点，或者i ，j为地铁站点而k为公汽站点时)，则 i,j,k = 0若可换乘，则：问题一模型 ： 因为仅考虑公汽线

10、路，为了能得到两站点之间的最好选择线路，将题中所提供的公汽网络抽象成一个有向赋权图,建立直达矩阵D =。当D为时间直达矩阵时，按D(k)= D(k-1) D式重复地进行运算得到，当，时，表示从 i站点到 j站点最少换乘k次能够到达，且即表示换乘k次到达所需的最短时间。 当D为费用直达矩阵时，按D(k)= D(k-1) D重复地进行运算得到，运算适当次数后若 D(k)= D(k-1)，则表示已得到所有站点间的最小费用，即表示从i站点到j站点所需的最少费用。 根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。问题二模型 ： 当还需要考虑地铁时，为了能得到两站点之间的最好选

11、择线路，同样，将题中所提供的公汽（含地铁转换的公汽）网络抽象成一个有向赋权图,建立直达矩阵D =。算法设计基本与模型一相当。 当D为时间直达矩阵时，按D(k)= D(k-1) D式重复地进行运算得到，当，时，表示从 i站点到 j站点最少换乘k次能够到达，且即表示换乘k次到达所需的最短时间。 当D为费用直达矩阵时，按D(k)= D(k-1) D重复地进行运算得到，运算适当次数后若 D(k)= D(k-1)，则表示已得到所有站点间的最小费用，即表示从i站点到j站点所需的最少费用。根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。问题三模型： 问题三是在模型二的基础上添加步

12、行时间进行考虑。 优先考虑乘换次数。对直达时间矩阵按D(k)= D(k-1) D式重复地进行运算得到，当，时，表示从 i站点到 j站点最少换乘k次能够到达。在运算过程中可记录下换乘站点信息，随之可得到相关线路信息。若有若干条最小换乘路线，则比较另外两个目标选择最佳线路（即建立0-1整数规划模型）。 设共有m条单行公交线，构造一个m+2个点构成的完全图。 点：a为起点（出发点），b为终点（目的地），此外每条公交线也视为一个点。 边：边表示两点之间的步行关系。 边权：步行时间为边权。针对不同的边可分为上车前、下车后和换车时步行时间，构成步行时间矩阵 。行：依次表示的是m条公交线与起点，列：依次表示

13、的是m条公交线与终点。 点权：第个公交线点还有三个信息为点权。 1）公交线名称及上行或下行； 2）类型及票价方式； 3）乘车站数表矩阵 ，其中 表示从c到d经过i号公交线时需要乘车的站数,c到d利用不上i时取无穷大。这个矩阵的行列表示用S。 于是原问题转化为在这个图上求a到b的最短路。 最短的可以理解为换乘车数最少、乘车的总站数最少、总的步行时间最少、总车费最少这样几个目标的各种组合方式。 可以用0-1整数规划解决这个问题，方法是分出恰乘一次公交车，恰乘两次公交车，恰乘三次公交车等等情况分别求出下列模型解然后比较得出最优解。 优化模型：恰乘一次公交车的模型如下：变量全部是0-1变量，共有3*(

14、m)个。 表示选不选择去第i条公交线的路； 表示选不选择乘第i线公交车； 表示选不选择从第i条公交车下车后走到目的地的路。 (它们都是取1表示选择而取0表示不选择。)恰乘一次公交车的模型如下： 目标函数：据用户选择的情况用点权和边权构造，共同点都是最小值。 ( 1)步行时间最少: 目标函数 (2)总时间最少: 目标函数 其中，(3)车费最少: 目标函数： 约束条件（共2m+1个）： 只选择一条公交线； 要乘第i条公交线就要走相应的两条路。恰乘两次公交车的模型如下：步行时间:时间最少：费用最少：约束条件： 可以选择两条公交线路； 乘公交线要走的两条相应的路线。恰乘乘三次公交车模型:步行时间的目标

15、函数在的基础上添加;时间最少的目标函数在的基础上添加;费用最少:约束条件即在的基础上添加的变量即可。五、模型求解: 问题一： 由于题目所给的公交乘路信息是.txt文本文件，为了将实际问题能用数学模型来解决，我们编写程序将其导入matlab。（程序见附录1）。对于问题1，我们仅仅考虑公汽线路，为此，我们将所有的公汽路线与站点（3957个）关系构成一个图网，为了求得最小代价的选择路线，我们先建立起直达矩阵（程序见附录2），再由改进floyd算法（程序见附录3）即可求出两公汽站点之间线路选择的最小代价（乘换次数、时间最短、费用最少），乘换次数为主、时间最短和费用最少为次为约束条件用搜索法（见附录程序

16、5）搜出最优线路，具体结果如下所示：起点站终点站乘换次数时间（分钟）车费（元）线路S3359S18281893S1557S048121123S0971S048511193S0008S00731832S0148S048521063S0087S36762523问题二： 对于问题2，我们在考虑公汽线路的同时，还需将地铁线路（2条地铁线路，39个地铁站点）考虑进去，同样，将所提供的公汽（含地铁转换的公汽）网络抽象成一个有向赋权图,建立直达矩阵（程序见附录4），再由改进floyd算法（程序见附录3）即可求出两公汽站点之间线路选择的最小代价（乘换次数、时间最短、费用最少），以换乘次数为主、时间最短与费用最

17、少为次为约束条件用搜索法（见附录程序6）搜出最优线路，具体结果如下所示：起点站终点站乘换次数时间（分钟）车费（元）线路S3359S18281893S1557S048121123S0971S048511193S0008S00731832S0148S048521063S0087S36760503问题三： 问题3又增设了所有站点之间的步行时间，为了给出任意两站点之间线路选择问题的数学模型。我们则考虑大众化的想法（优先考虑乘换次数）：1若两个站点之间有直达的公交车，若只有一条，我们毫无条件地选择；若不止一条，则我们可以利用模型三的优化模型进行时间和费用的比较，取最优解；2同理，若要经过转乘一次、二次等

18、转乘情况，若转乘线路只有一种，则选择之；若转乘线路有多种，则利用模型三的优化模型进行时间和费用的比较，取最优解。六、模型优缺点:将公交图网能用有向赋权图并建立直达矩阵，再利用最短路算法及搜索算法得出线路选择的最优线路（含时间最少、费用最少等）；对于第三问题中的模型，在加入步行时间后，我们能考虑到在乘换次数最少为优先的条件下，利用优化模型进行比较是全面些。鉴于公交系统网络的复杂性，我们虽然采用了修改floyd算法，编译运行上不太好，有待改进。7、 参考文献:1蔡志杰，丁颂康 数学工程学报-公交线路选择模型 2007年12月 1005-3085（2007）08-0117-042朱参世 一种 War

19、shall和 Fl oyd算法的优化方法研究 2010年第四期 1006-2475（2010）04-0043-033刘韵，何建农 基于交通网络最短路径搜索的改进算法 2007年 1002-8331（2007）14-0220-03附录:function A = T_SORT( A ,n , p ) %建立排序函数% T_SORT( A ,n , p )% A 根据第n行排序% p=1升序，2 降% powered_BY_*SIZE=size(A);if p=1xx,idx=sort(A(n,:);for i=1:SIZE(1)A(i,:)=A(i,idx);endelseif p=2xx,idx

20、=sort(A(n,:),'descend');for i=1:SIZE(1)A(i,:)=A(i,idx);endend1、%数据处理读入matlab：%读取数据 clear L a fid = fopen('1.1 公汽线路信息.txt','r'); i=1; while 1 tline = fgetl(fid); if ischar(tline), break, end if strcmp(tline,'') continue end if strcmp(tline(1),'L') str=tline; co

21、ntinue elseif strcmp(tline,'END') break end if strcmp(tline,'单一票制1元。') P=1; continue elseif strcmp(tline,'分段计价。') P=2; continue end if strcmp(tline(1:2),'上行') Li,1=str; Li,2=P; Li,3='上行' Li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),'下行')

22、 Li,1=str; Li,2=P; Li,3='下行' Li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),'环行') Li,1=str; Li,2=P; Li,3='环行1' Li,4=strcat(tline(4:end),tline(10:end); i=i+1; %计算来回 Li,1=str; Li,2=P; Li,3='环行2' Li,4=strcat(tline(4:end),tline(10:end); i=i+1; continue elseif

23、 strcmp(tline(1),'S') Li,1=str; Li,2=P; Li,3='来回1' Li,4=tline; i=i+1; %计算来回 Li,1=str; Li,2=P; Li,3='来回2' Li,4=tline; i=i+1; continue end endfclose(fid);for i=1:size(L,1) tline=Li,4; t=findstr(tline,'S'); temp=zeros(1,length(t); if strcmp(Li,3,'来回2') | strcmp(L

24、i,3,'环行2') for j=length(t):-1:1 temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4); end else for j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4); end end L2i,1=temp; end for i=1:3957 if floor(i/10)=0 Citi=strcat('S000',num2str(i); elseif floor(i/100)=0 Citi=strcat('S00'

25、;,num2str(i); elseif floor(i/1000)=0 Citi=strcat('S0',num2str(i); else Citi=strcat('S',num2str(i); end end Cit3958='D01：S0567，S0042，S0025' Cit3959='D02：S1487' Cit3960='D03：S0303，S0302' Cit3961='D04：S0566' Cit3962='D05：S0436，S0438，S0437，S0435' C

26、it3963='D06：S0392，S0394，S0393，S0391' Cit3964='D07：S0386，S0388，S0387，S0385' Cit3965='D08：S3068，S0617，S0619，S0618，S0616' Cit3966='D09：S1279' Cit3967='D10：S2057，S0721，S0722，S0720' Cit3968='D11：S0070，S2361，S3721' Cit3969='D12：S0609，S0608' Cit3970=&

27、#39;D13：S2633，S0399，S0401，S0400' Cit3971='D14：S3321，S2535，S2464' Cit3972='D15：S3329，S2534' Cit3973='D16：S3506，S0167，S0168' Cit3974='D17：S0237，S0239，S0238，S0236，S0540' Cit3975='D18：S0668' Cit3976='D19：S0180，S0181' Cit3977='D20：S2079，S2933，S1919，

28、S1921，S1920' Cit3978='D21：S0465，S0467，S0466，S0464' Cit3979='D22：S3457' Cit3980='D23：S2512' Cit3981='D24：S0537，S3580' Cit3982='D25：S0526，S0528，S0527，S0525' Cit3983='D26：S3045，S0605，S0607' Cit3984='D27：S0087，S0088，S0086' Cit3985='D28：S085

29、5，S0856，S0854，S0857' Cit3986='D29：S0631，S0632，S0630' Cit3987='D30：S3874，S1426，S1427' Cit3988='D31：S0211，S0539，S0541，S0540' Cit3989='D32：S0978，S0497，S0498' Cit3990='D33：S1894，S1896，S1895' Cit3991='D34：S1104，S0576，S0578，S0577' Cit3992='D35：S3010，

30、S0583，S0582' Cit3993='D36：S3676，S0427，S0061，S0060' Cit3994='D37：S1961，S2817，S0455，S0456' Cit3995='D38：S3262，S0622' Cit3996='D39：S1956，S0289，S0291'2、%建立公汽间的直达矩阵clear SS(1:3957,1:3957)=zeros(1,1,'uint16');%按UInt16格式 建立1行1 列的零巨阵for i=1:1040 t=L2i,1; for j=1:l

31、ength(t)-1 for k=j+1:length(t) temp=St(j),t(k); str=Li,1; n,m=size(temp); if n=1 && temp(1,1)=0 temp(n,1)=str2double(str(2:end); if Li,2=2 if (k-j)>40 temp(n,2)=3; elseif (k-j)>20 temp(n,2)=2; else temp(n,2)=1; end else temp(n,2)=1; end temp(n,3)=k-j; else temp(n+1,1)=str2double(str(2:

32、end); if Li,2=2 if (k-j)>40 temp(n+1,2)=3; elseif (k-j)>20 temp(n+1,2)=2; else temp(n+1,2)=1; end else temp(n+1,2)=1; end temp(n+1,3)=k-j; end St(j),t(k)=temp; end endendfor i=1:3957 for j=1:3957 if length(Si,j)=1 Si,j=T_SORT(Si,j',3,1)' end endendTime=zeros(3957,3957,'uint8');

33、for i=1:3957 for j=1:3957 if length(Si,j)=1 Time(i,j)=size(Si,j,1); end endendTT=zeros(3957,3957,'uint8');for i=1:3957 for j=1:3957 temp=Si,j; if temp(1,1)=0 TT(i,j)=temp(1,3); end endEnd%时间、费用的直达矩阵(换乘直达线路数矩阵)ee,rr=size(S); ss=zeros(ee); for i=1:ee for j=1:rr if Si,j=0 ss(i,j)=length(Si,j(:,

34、1); end end end for i=1:ee for j=1:rr if ss(i,j)=0; ss(i,j)=Inf; end end end for i=1:ee for j=1:rr if i=j; ss(i,j)=0; end end end2.2 (间直达矩阵)ee,rr=size(S); ttt=zeros(ee); for i=1:ee for j=1:rr if Si,j=0 ttt(i,j)=min(Si,j(:,3); end end end for i=1:ee for j=1:rr if ttt(i,j)=0; ttt(i,j)=Inf; end end end

35、 for i=1:ee for j=1:rr if i=j; ttt(i,j)=0; end end end2.3 (费用直达矩阵)ee,rr=size(S); ppp=zeros(ee); for i=1:ee for j=1:rr if Si,j=0 ppp(i,j)=min(Si,j(:,2); end end end for i=1:ee for j=1:rr if ppp(i,j)=0; ttt(i,j)=Inf; end end end for i=1:ee for j=1:rr if i=j; ppp(i,j)=0; end end end3、%算子算法function D,pa

36、th,k,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end, end, endwhile 1<=j<=nfor k=1:n DO(k,j)=D(k,j); endendfor k=1:n for i=1:n for j=1:n if D(i,k)+DO(k,j)<D(i,j) D(i,j)=D(i,k)+DO(k,j); path(i,j)=path(i,k); end if D(i,k-1)

37、+DO(k-1,j)<D(i,j) D(i,j)=inf; if D(i,k)+DO(k,j)<D(i,j) D(i,j)=inf; k end,end end endendif nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end4、%考虑地铁的直达矩阵fid = fopen('B2007data

38、/2.1 地铁T1线换乘公汽信息.txt','r'); i=1; while 1 tline = fgetl(fid); if ischar(tline), break, end if strcmp(tline,'') continue end if strcmp(tline(1),'D') Di,1=tline(5:end); i=i+1; end end fclose(fid); fid = fopen('B2007data/2.2 地铁T2线换乘公汽信息.txt','r'); while 1 tlin

39、e = fgetl(fid); if ischar(tline), break, end if strcmp(tline,'') continue end if strcmp(tline(1),'D') Di,1=tline(5:end); i=i+1; end end fclose(fid); tx=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,. 26,12,27,28,29,30,31,32,18,33,34,35,36,37,38,39+3957; DL1,1='

40、;' DL2,1='' for j=1:23 DL1,1=strcat(DL1,1,'S',num2str(tx(j); end for j=24:41 DL2,1=strcat(DL2,1,'S',num2str(tx(j); end DL2,1=strcat(DL2,1,'S',num2str(tx(24); for i=1:1040 for j=1:41 tline=Dj,1; t=findstr(tline,'S'); for k=1:length(t) Li,4=regexprep(Li,4, s

41、trcat('S',tline(t(k)+1:t(k)+4),. strcat('S',num2str(tx(j); end end end Lt1=L; Lt11041,1='T001' Lt11041,2=3; Lt11041,3='来回1' Lt11041,4=DL1,1; Lt11042,1='T001' Lt11042,2=3; Lt11042,3='来回2' Lt11042,4=DL1,1; Lt11043,1='T002' Lt11043,2=3; Lt11043,3=

42、'环行1' Lt11043,4=strcat(DL2,1,DL2,1(6:end); Lt11044,1='T002' Lt11044,2=3; Lt11044,3='环行2' Lt11044,4=strcat(DL2,1,DL2,1(6:end); for i=1:1044 tline=Lt1i,4; t=findstr(tline,'S'); temp=zeros(1,length(t); if strcmp(Lt1i,3,'来回2') | strcmp(Lt1i,3,'环行2') for j=length(t):-1:1 temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4); end else for j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4); end end Lt2i,1=temp; end5、N=87; M=3676; % 直达 if Time(N,M)=0 temp=SN,M; for i=1:size(temp,1) disp(strcat('直达车为:L',num2str(temp(i,1)