乘公交 看奥运

论文中matlab运行程序并未出结果所以这篇论文中并没有给出结果，只有思路。摘要本文要解决的问题是以08年北京奥运会为背景而提出的。人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。本文以以下三个影响较大的因素：第一是换乘次数；第二是乘车时间；第三是乘车费用。针对问题一，在只考虑公汽系统的情况下，我们考虑了直达，一次换乘，和两次换乘的情况，并分别讨论了在不同换乘情况下的乘车时间以及乘车费用，用matlab编程求出了任意两站点间的最佳乘车路线以及换车的地点。针对问题二，在问题一的基础上加入了地铁线路，因此增加了选择线路，同时也增加了通过步行经过地铁转乘的站点，改进问题一中的求解方法，增加线路和可达点求解。针对问题三，在问题二的基础上又增加了步行这种情况，在适当站点步行，可以节省交通费用而且不会消耗过多时间。关键词：最佳路线换乘次数乘车时间乘车费用一、 问题重述传承华夏五千年的文明，梦圆十三亿华夏儿女的畅想，2008年8月8日这个不平凡的日子终于离我们越来越近了！在观看奥运的众多方式之中，现场观看无疑是最激动人心的。为了迎接2008年奥运会，北京公交做了充分的准备，首都的公交车大都焕然一新，增强了交通的安全性和舒适性，公交线路已达800条以上，使得公众的出行更加通畅、便利。但同时也面临多条线路的选择问题。为满足公众查询公交线路的选择问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。这个系统的核心是线路选择的模型与算法，另外还应该从实际情况出发考虑，满足查询者的各种不同需求。需要解决的问题有：1、 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型算法，求出以下6对起始站到终到站最佳路线。(1)、S3359-S1828 (2)、S1557-S0481 (3)、S0971-S0485(4)、S0008-S0073 (5)、S0148-S0485 (6)、S0087-S36762、 同时考虑公汽与地铁线路，解决以上问题。3、 假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、 模型假设1、 所有公交线路的开班、收班时间相同。2、 公车不会因为堵车等因素延长行驶时间。3、 各条线路不会有新的调整与变化。4、 环线可以以任意站作为起点站和终点站，并且是双向的。5、 除环线以外的线路，到达终点站后，所有的人都必须下车。6、 人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度。7、 同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费

三、符号定义表示意义LAi第i条包含初始站点的线路，i=1,2, ,mLBj第j条包含目标站点的线路，j二1,2；・・，sLCk第k条中间线路，k二1,2, ,w …ailLA上的第/个站点，/二1；2； ,mibLB上的第r个站点，r二1,2,…,tjrjcLC上的第u个站点，u二1,2,…，vkukxi乘客在第i段线路上乘坐的站数y乘客在一次地铁线路上乘坐的总站数zi公汽换乘公汽的次数z2地铁换乘地铁的次数z3地铁换乘公汽的次数z4公汽换乘地铁的次数4.1问题一4.1.1问题分析仅考虑公汽线路的情况下，首先，需要根据题目给出的公交线路信息数据，对每条线路进行抽象处理，将分上下行的线路、双向行驶的线路和环行线路抽象为两条。然后，主要考虑公众最关心的乘车因素，即转乘次数。在最少转乘次数的基础上考虑共众对其他因素的需求，按照先后顺序考虑行程时间和乘车费用，给出供公众选用的多种参考方案。并考虑以时间为主要目标的情况下，建立最优化模型确定任意两站点行程时间最短的方案。4.1.2数据预处理将上下行的线路分为两条。中下行路线标号需要在原标号的基础上加上520，用以区分上行线和下行线。例如：L002的上行线为L002:S3748-S2160-S1223-S1404-S2377-S1477-S2017-S2019-S1321-S1381-S1383-S1691-S3766-S1729-S2654-S3231-S3917-S2303-S1327-S3068-S2833-S1733-S2113-S2636-S0012-S1968-S0004L002的下行线为L522:S0004-S1968-S0012-S2636-S2113-S2112-S2833-S0618-S1327-S2303-S3917-S3231-S2654-S1729-S3766-S1691-S1383-S1381-S1321-S2019-S2017-S1477-S1404-S1223-S2160-S3748如果下行线是上行线原路返回，那么存储的两行数据中的站点信息刚好顺序颠倒。例如L001分为L001和L521L001:S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710L521：S0710-S0128-S3914-S0820-S3524-S0819-S3612-S3885-S0436-S0429-S0392-S0348—S0388—S1914—S0619(3)如果是环行线，则将其分为顺时针线和逆时针线。如下图所示：D顺时针线路：A-B-C-D逆时针线路：A-D-C-B以L017环行路公交线路为例L017:S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S2742-S2533-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483-S0604-S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S0668-S3081-S3078-S2082-S0683-S2160-S3748L537:S3748-S2160-S683-S2082-S3078-S3081-S668-S3648-S1895-S577-S582-S427-S456-S622-S2962-S1659-S3693-S2650-S604-S483-S609-S2085-S1907-S940-S1007-S1929-S2937-S2755-S2751-S1839-S2533-S2742-S2543-S2764-S3029-S1123-S3028-S2816-S2808-S3078-S732-S2160-S37484.1.3模型建立TOC\o"1-5"\h\z将所有包含初始站点a的线路LA,LA,,LA建成一个集合S,1<l<n,il0 1 2 m 0i=1,2,,m，所有包含目标站点b的线路ZB,LB,,LB建成一个集合G，jr01 2 s1<r ，j—1,2, ,s。0•••S-・{lA,LA,,LAG-{LB,LB, ,LB12m1 2 sLA—ai 订•TaTi2Ta，i—1,2, ;m，inLB—b—b—一b，j=1,2；°°,s。j j1 j2 jt（1）直达的情况既如图所示：从A到B的直达情况示意TOC\o"1-5"\h\zA B-4 对于直达的情况，当S.GH0时，存在LA、LB,1<i<m，1<j<s，使得LA—LB，即LA.、ij ij iLB为同一线路。此线路既包含初始站点a又包含目标站点b。j il0 jr0若l<r，那么，此线路为所求直达线路。00若>r，或者当S.G=0时，考虑换乘一次的线路。(2(2)换乘一次的情况如图所示的情况，其中C为换乘点。当有LA当有LA和LB相交时，存在LA、LBi j i j1-i-m，1<j<s，有a&la严bgLB，1<l<n，jrjb为同一站点。jrbgLB，1<l<n，jrjb为同一站点。jriljr il若l<l<n，1<r<r，那么，从初始站点a乘坐线路LA，行驶至站点a，00 il0 i il即在站点b，jr换乘线路LB至目标站点b。即j jr0aT （LA）ta=bT （LB）tbil0 i il jr j jr0若不满足l<l<n・，・1<r<r，或者，当无任何LA和LB相交时，考虑换乘0 0 i j两次的线路。(3)换乘两次的情况如图，是换乘两次的情况，其中C,D是换乘点。

TOC\o"1-5"\h\z记LC,LC,,LC,LC=cTcTTc,k=1,2,,w，有LC ,1 2 w k k1 k2 kv kLC电G,k=1,2；,w，且满足LC与LA、、LB都相交时，即•k k i j线路LC既不包含初始站点a又不包含目标站点b,1<l<n,1<r<t。k ilo jr。 0 0但是存在ceLC及aeLA，使得c=a，

阿 k il i 阿 il存在ceLC及beLB，使得c=b，k«2 k jr j ku2 jr即c、a为同一站点，且c、b为同一站点。1<k<w，1<i<m，1<j<s，kU1il kU2 jr1<u<v，1<u<v，1<l<n，1<r<t。12若l<l<n，1<u<u<v，1<r<r，那么，从初始站点a乘坐LA线路,0 12 0 il0 i行驶至站点a，即在站点c，换乘LC线路至站点c，即在站点b，换乘LBil ku1 k ku2 jrj线路至目标站点b。即jr0aT(LA)—Ta=c—T (LC)Tc=bT(lb)Tbil0 i il ku1 k ku2 jr j jr0若不满足・l<l<n・，1<u<u<v，・1・<r<r•，•或者，当不存在满足条件的・LC时,0 12 0 k说明需要换乘三次才能够到达目标站点。(4)最优化模型的建立设f为乘坐公交线路的费用函数:0,1,f0,1,f(x)彳2I2,3,x=0;0<x<20;i20<x<40;ix>40i总时间函数:(0<z<2)1i=1总费用函数:F=工f(x)i其中x表示乘客在公交线路L上乘坐的站数；z表示公汽换乘公汽的次数。i i 1目标：找出任意给定的两站点的乘车线路，使T和F相对最小。4.1.4算法的解释由于人们的对换乘车次数尽量少的偏好程度总是大于对花费时间和金钱相对少的偏好程度，我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少，对得出的所有结果中进行筛选。对于整个算法对路线搜索的具体算法步骤为：第一歩:输入乘车始点站和终点站，在数据库的站点线路矩阵中查询是否有相同路线的公汽（1） 有相同路线公汽，则查询站点间有直达线路，输出所有可直达车辆信息，结束程序；（2） 没有相同路线公汽，则查询站点间需要转乘，进入第二步。第二步；将始点和终点输入公汽站点矩阵，查询是否有相同的站点（1） 有相同站点，则查询站点可以通过一次转乘达到，输出所有一次转乘的车次和中转站的信息，结束程序；（2） 没有相同站点，则查询站点间需要转乘两次，进入第三步。第三步：找最后一个中转站，在终点站所在线路中沿车驶向的反向找一个站点当做终点站称为伪终点站，根据伪终点站和始点站输入到公汽站点矩阵，查询是否有相同的站点（1） 有相同站点，则查询站点可以通过两次转乘达到，输出所有两次转乘的车次和中转站的信息，结束程序；（2） 没有相同站点，则查询站点间需要转乘三次（此论文不考虑换乘3次及3次以上的情况）以上的搜索方法得到公交查询系统的流程，具体流程图如下

4.1.5模型的求解根据以上算法和前面建立的模型一，用matlab对程序运行（程序见附录）就可以得出不同目标下的最优路线。4.2问题二4.2.1问题分析针对问题二，将公汽与地铁同时考虑，找出可行路线，然后寻找最优路线。对于地铁线路，也可以将其作为公交线路，本质上没有什么区别，只不过乘车费用、时间，换乘时间不一样罢了。因此地铁站可等效为公交站，地铁和公交的转乘站即可作为两者的交汇点。因此该模型的公交换乘路线模型与模型一中的基本相同。4.2.2算法分析由于假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，那么不妨把同一地铁站所对应的几个公汽站合并成一个站。地铁线路T1=D01今D02今今D23，T2=D24今D25今今D39今D24。1、可以乘坐地铁的线路。（1） 若初始站点和目标站点都在地铁线路T1或者T2上，那么，只乘坐地铁T1或者T2便可以直达。其中，若都在线路T2上，就选择经过站数最少的方向。若初始站点和目标站点分别在地铁线路T1和T2上，那么，需要进行一次地铁换乘地铁才能到达。（2） 若只有初始站点或只有目标站点在地铁线路上，则需要换乘公汽才能到达目标站点。初始站点aeTp，p=1,2，目标站点b电T1且b电T2，beLB。ilo jro jro jr0 j当有LB和地铁相交时，即存在LB，有beLB，使得beTy，q二1或2。jjjjjr1<i<m，1<j<s。若1<r<r，那么，从初始站点a（记为Da）乘坐地铁线路，行驶至站0%点b（记为Db），换乘公汽线路LB至目标站点b。1<a<39，1<b<39。jrj jr0即DaT(TpDaT(Tp)ailo「Da]T(Tp)血)Tb「Db]」 jr「 」ailo其中，q丰p时需要地铁换乘地铁。tb「DbIt(LB)Tb(q=p)j jroT (LB)Tb (q丰p)j jro若不满足1<r<r，或者当没有这样的LB时，说明在地铁换乘公汽后，还o j需要进行公汽换乘公汽。由于这样的情况几乎不存在，故不作考虑。目标站点beTp，初始站点a电T1且a电T2，p=1,2jro ilo ilo同理可得结论。（3）若初始站点和目标站点都不在地铁线路上，则先乘坐公汽，换乘地铁,再由地铁换乘公汽。地铁线路既和LA相交又和LB相交时，即ij地铁线路既不包含初始站点a又不包含目标站点b。但是存在LA、LB,jro i j1<i<m,1<j<s，有aeLA,aeLA,il i使得aeTp，记a为Da，il ilbeLB,jrj使得beTq，记b为Db，jr jrp=1,2,q=1或2,1<a<39,1<b<39。若l<l<n,1<r<r，那么，从初始站点a乘坐LA线路，行驶至站点a（记0 0 ilo i il为Da），换乘地铁线路至站点b.（记为Db），换乘LB线路至目标站点b。jr j 兀aT(LAaT(LA)Ta[Da]T(Tp)~Tb[Db]-T(LB)Tbilo i il jr j jro(LA•)Ta[Da]T (tp)(Tq)Tb…[Db]T(LB)i il jr j(q=p)a —TiloTbjro•••/•••、•••(q丰p)其中，q丰p时需要地铁换乘地铁。若不满足l<l<n，1<r<r，或者不存在LA、LB都与地铁线路相交，说o o ij明需要在地铁线路前或后进行公汽与公汽的换乘。由于这样的情况几乎不存在，故不作考虑。2、只乘坐公汽的线路。

完全排除地铁线路，与解决问题一的方法相同。4.2.3模型建立设f，g分别为乘坐公交和地铁线路的费用函数:01,/（x）=仁I2,、3,01,/（x）=仁I2,、3,总时间函数：x=0;0<x<20;i20<x<40;ix>40iy=0;y>0T=3^x+2.5y+5z+4z+7z+6zi 12 3 4i=1总费用函数：(0<z<2，工z<2)i ii=1(3)F=工f(x)+g(y)ii=1(4)其中x表示乘客在公交线路L上乘坐的站数;i iy表示乘客在一次地铁线路上乘坐的总站数；z,z,z,z分别表示公汽换乘公汽，地铁换乘地铁，地铁换乘12 3 4公汽，公汽换乘地铁的次数。目标：找出任意给定的两站点的乘车线路，使T和F相对最小。4.2.4模型求解首先，我们通过matlab编程（程序见附录）作出了两条铁路的位置关系图,如下图所示。T1与T2铁路位置关系图同样将地铁线路等效为公交线路得出任意两个站点间的可行线路，再将目标函数分别用上述模型建立的模型表达式表达，用matlab进行编程（程序见附录）求得出考虑地铁情况的最优路线。4.3问题三4.3.1问题分析问题三是在前面问题的基础上，加入了步行这一较为自主化的“交通工具”使得原本的选择最优线路模型不再使用，于是我们这里建立了一个线路综合评价模型，通过分类讨论的方式，提供适合各种情况的线路选择方案，从而解决在三种交通工具并行时的路线选择问题。4.3.2模型建立我们使用综合评价的方法对不同的情况进行分类，分类的标准是：乘坐的交通工具。由于这里有三种交通工具：步行、地铁、公共汽车，所有我们有种不同的搭乘方式，可分为三类：搭乘一种交通工具，搭乘两种交通工具，搭乘三种交通工具。下面我们来分别讨论。⑴搭乘一种交通工具搭乘公共汽车这时可以根据问题1的模型来解决选择线路问题。搭乘地铁这种方式只适用于起始站、属于地铁的相邻公汽站台矩阵，这时可以通过在地铁直达。步行

步行可以到达任何终点站，但从实际出发，我们认为步行距离不能过长，这里我们认为当起始站、相隔不到两站时，可以采取步行；起始站相隔超过两站时，我们认为步行不实际。⑵搭乘两种交通工具搭乘公共汽车和地铁这时就是等同于运用问题2的模型来选择线路方法。搭乘公共汽车和步行这时我们可以在问题1的基础上考虑加入步行。这里我们只提供在以下情况下采取步行较合适：为减少换乘次数：两公汽站台只相隔一站，可采取步行，从而减少了一次的换乘；为减少路费：因为分段计价的公共汽车票价为：0〜20站：1元；21〜40站：2元；40站以上：3元。所以在终点站或换乘站在21站处时，我们可提前在20站出下车，再步行1站到达终点站或换乘站，从而节省1元；当出现两站之间出现如图示情况时，可考虑不行到达终到站。搭乘地铁和步行当起始站、不属于或不全属于地铁的相邻公汽站台矩阵时，需要通过步行才能到达终点；由于地铁只有T1、T2两条线路，且两条线路只能在D12和D18处转乘，因此在需要换乘地铁时，可考虑步行到达地铁站D12或D18。⑶搭乘三种交通工具(地铁、公共汽车、步行)已知所有站点之间的步行时间，假设任意两站点i、j之间的步行时间为，通过转乘从i站到达j站所用时间t，转乘用时t，则我们可在上述的基础上加入一个0判断语句，即t+1与T比较大小，如果t+1较小，则说明通过转乘更省时；反00之，步行更省时同时也省钱，则采取步行从i站到达j站。最优化模型的建立设f,g分别为乘坐公交和地铁线路的费用函数：0,x—n0,x—n二0;ii0,y=0;3,y>0.1,2,0<x—n<20;ii20<x—n<40;g(y)=x—n>40.V • •i i根据实际情况，在地铁线路上不考虑步行。我们可以在初始站点、目标站点或换乘站点的附近考虑步行，即在任意公交线路L,1<i<3上最多下车一次。否i则，若在某个L,1<i<3上下车步行两次，则在L上需要多购买车票一次，同时i i消耗的时间更多，此做法既违反常理，又不经济实惠。

设在线路L,i二1,2,3上步行的站数为n,0<n<x，相邻公汽站步行时间i i ii为t，那么总时间函数:n+2.5yn+2.5y+5z+4z+7z+6z，(5)i 12 3 4i=1 i=1总费用函数:F仝f(x-n)+g(y),iii=1目标：找出任意给定的两站点的乘车线路，使T和F相对最小。五、 模型评价及推广本题中所构建的模型简单易懂，操作简单，涵盖了所有路线的选择情况，并且相对符合“乘公交，看奥运”的主题，解决了公交线路的选择问题，使公众的出行更加通畅便利。但是本模型忽略了人流、车流拥挤的状况。因此在实际生活中有限制。对于若干条从某一初始站点到目标站点的线路，我们可以设计一种带记忆功能的系统，即乘客选择某路径的次数越多，说明此路径是比较优的路径，为以后选择路径提供必要的信息。系统使用的时间越长，为乘客提供的信息越全面，越准确，系统也越智能化。这样就可以为乘客需求量最大的一条增加班次，以满足更多人的需要。在假设中提到，所有线路的开班、收班时间相同，但事实并非如此。那么可以在模型的设计中加入线路运行的时间元素，使乘客查询时只显示正在运行的线路。六、 参考文献[1]《大学数学实验》姜启源，邢文训，谢金星杨顶辉，北京：清华大学出版社，2000[4]《MATLAB工具箱应用》苏金明编七、附录问题一的程序代码(直达的线路)xl=input('pleaseinputstartingstation:');

yl=input('pleaseinputtheterminal:');[il,jl]=find(a==xl);[i2,j2]=find(a==yl);[m,n]=size(il);[p,q]=size(i2);r=0;fori=1:mforj=l:pifil(i,n)==i2(j,q)nv=find(xl==a(il(i,n),:));nu=find(yl==a(i2(j,q),:));ifnv〈nur=r+1;t(r)=i1(i,n);endendendendifr~=0disp(t)elset=0endj1j2%直达的输出说明t是线路j1是起点站在该线路的第几个站j2是终点站在该线路的第几个站问题一的程序代码(换乘一次的线路)x1=input('请输入起点站：')；yl=input('请输入终点站:’)；W=input('输入最多经过站点的个数:');[il,jl]=find(a==xl); %记录行和列[i2,j2]=find(a==yl);[m,n]=size(il);[p,q]=size(i2);fori=1:mforj=1:pro=0;ifil(i,n)~=i2(j,q)mv=a(il(i,n),:);mu=a(i2(j,q),:);[mo,no]=size(mv);[po,qo]=size(mu);forio=1:noforjo=l:qoifmv(mo,io)==mu(po,jo)ad=find(a(il(i,n),:)==xl);%xl所在的位置bd=find(a(i2(j,q),:)==yl); %y1所在的位置ao=find(mv(mo,io)==a(il(i,n),:));%转站点在x1所在列的位置bo=find(mv(mo,io)==a(i2(j,q),:)); %转站点在y1所在列的位置ifad〈ao&bo〈bd&(ao-ad+bd-bo)〈Wro=ro+1;to(ro)=mv(mo,io);tka(ro)=ao-l;tji(ro)=bo-l;endendendendifro~=0disp('中转站点')disp(to)disp('中转站点在始发线上的位置’)disp(tka)disp('中转站点在抵达线上的位置’)disp(tji)vo(l)=il(i,n);vo(2)=i2(j,q);disp('始发线和抵达线’)a(vo,1)disp('起点站位置')adTdisp('终点站位置')bd-1endendendend问题一的程序代码(换乘两次的线路)xl=input('请输入起点站：')；yl=input('请输入终点站:’)；W=input('输入最多经过站点的个数:');[il,jl]=find(a==xl);[i2,j2]=find(a==yl);[m,n]=size(il);[p,q]=size(i2);[vp,vb]=size(a);tto=0;%寻找不包含起点和终点的线路foriu=l:vpvc=a(iu,:);rpp=find(xl==vc);rpq=isempty(rpp);tpp=find(yl==vc);tpq=isempty(tpp);ifrpq==l&tpq==1tto=tto+l;uu(tto)=iu;endendforey=1:size(uu,2)eyy=a(uu(1,ey),:);forex=1:mexx=a(i1(ex,n),:);forez=1:pezz=a(i2(ez,q),:);mn=size(exx,2);iq=0;ih=0;%寻找exx和eyy的相同元