07年高教社杯全国大学生数学建模竞赛B题.doc

《07年高教社杯全国大学生数学建模竞赛B题.doc》由会员分享，可在线阅读，更多相关《07年高教社杯全国大学生数学建模竞赛B题.doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、,2007高教社杯全国大学生数学建模竞赛B题【摘要】本文根据人们出行习惯、情绪等特点,确定任意两站点之间的最佳线路的模型和算法。在只考虑公汽的情况下，在以换乘次数最小为主要因素,通过建立换乘次数及线路选择模型,在要求时间，费用最小的条件下，通过进行权重分析，建立最小花费函数，从而得到最佳路线。通过运用广度优先遍历算法和MATLAB编程，由已知的数据运算得到任意给定两站点之间的所有线路选择及其最优线路。 在同时考虑地铁、公汽线路时，沿用此模型思想、算法确定最佳路线。 假设又考虑步行时间，可通过建立最小路径成本模型，运用最优路径改进算法，确定最优路线。 最后针对对所作的模型、算法进行评价与推广，提

2、出可行有效的改进如Dijkstra算法。【关键词】：公交 最小换乘次数 广度优先遍历 最佳路线一、 问题重述这些年来，城市的公交系统有了很大发展，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。如何从实际情况出发考虑，满足查询者的各种不同需求。现需要解决的问题如下：分别在只考虑公交线路，同时考虑公交与地铁，或同时考虑已知站点之间的步行时间的情况下确定其最佳路线。（1）、仅考虑公汽线路，任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，在只考虑公交线路的情况下，求出以下6对已知站点之间的最佳路线（要有清晰的评价说明）。 (1)、 (2)、 (3)、(4)、 (5)

3、、 (6)、二、 问题分析实现公交网络查询系统的最优路径查询的重点在于如何实现查询者的个人满意度最高的问题。在公交换乘的过程中，有多种优先策略考虑。比如换乘次数最少、费用最少、时间最短等。每个人考虑的重要因素不同，但大多数人对换乘次数的多少比较在意，因此我们考虑用基于换乘次数最少的公交换乘优先策略，其次考虑时间最短，最后考虑费用最少，这比较符合大众出行时的心理情况。对于只考虑公交换乘方案的问题一，则可依次寻找两站点间是否存在直达线路、一次换乘线路、二次换乘线路等直达线路一致，有结果则输出。若二次换乘仍没有结果则输出“没有找到换乘次数少于2次的最优换乘方案”，结束运算。对于问题二，需同时考虑公交

4、与地铁线路，考虑到目前大众心理对地铁的便利性、快捷性的认同感，在考虑了换乘次数最少的情况下可优先考虑地铁换乘，其次再考虑公交换乘，其目的在于将行程的最大时间消耗不妨利用地铁的快捷减少时间上的损耗。对于问题三，在已知站点间的步行时间的条件下，对环行路线的影响较大，我们可只考虑环行路线。三、模型的假设和符号说明（一）模型的假设：1 假设每路况和车况相同，不影响公交的正常运行，并且不考虑公交线路的运输能力的限制及拥挤影响；2 假设任意相邻两站点的距离相等，运行时间相同，等车时间相同；3 出行者总是按直达，1次换乘，2次换乘等的优先顺序选择线路；4 基本参数设定： 相邻公汽站平均行驶时间(包括停站时间

5、)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：站：1元；站：2元；站以上：3元地铁票价：3元（无论地铁线路间是否换乘）（二）符号说明：表示第条路线，第个站点的站名；表示为始点站；表示为终点站；表示第条线路k站点的站数；表示第条线路的总站数；表示换乘的次数；分别表示第条路线为单一票价与分段计价；表示在

6、条线路上由站点到站点所需要的时间；表示在条线路上由站点到站点所需要的票价；四、模型的建立，算法及求解（一）换乘次数及线路选择模型根据人们的出行习惯，在选择从A站到B站的乘车路线时，首先会先看经过A站的车是否有直接到B站的，若有，马上会选择直达车（图1（a）；如果存在不止一条的直达线路，再考虑距离、时间、票价等综合因素的乘车方案；如果没有直达车，就会考虑一次换乘的乘车方案：即经过A站的车与经过B站的车有公共站点C吗？如果有，则可以在公共站点C处转车(图1（b）)；如果没有则又要考虑二次换乘的乘车方案，即乘坐经过A点的车到某一站C下车，经过C站点的车与经过B站点的车是否有公共站点D，如果有就再到D

7、转车，两次转车可到达B站(图1（c）)；如果没有，则需要三次换乘或三次以上才可到目的地。考虑到人们的心理、情绪等特点，可设 (人们换乘次数的最大容忍程度)，大连市89条线路，376个不同的车站，结果显示直达的占7.17%，换乘一次的占53.38%，换乘两次的占38.07%，换乘两次找不到目标站的占1.37%。（可见四次之内的换乘是比较合理的，超过四次的换乘是没有意义的，不予以考虑）图1 公交线路选择图问题一建模时，将同一线路的上行、下行看作两条线路，通过对线路重新命名可以区分。按照人们出行乘车的心理特点，本文提出换乘次数及线路选择模型，通过此模型寻找经过始点站和终点站的各线路集合，再比较两集合

8、是否有交点，从而选择是否通过直达还是换乘的线路到达终点站。即：（1）设始点站、终点站的线路，分别建立经过这两站点的所有线路的集合： （2）判断两集合和是否有公共交点：1若，则从始点站r1到终点站r2可直达且A中元素为可选路线。2。若，则表明从始点站r1到终点站r2不可直达，必须通过换乘方法才能达到终点站。令 (其中表示可与直达的所有站点所在集合) （1）、若，则通过换乘一次可到达终点站，B中的点为换乘站点，并可确定线路，该过程可以建模下去（2）、若，则表明要到终点站，必须换乘2次以上才能到达，运用上述原理，找出从ri可直达或经过一次换乘的线路集合，再判断两集合的是否存在交集：令 （其中表示ri

9、可直达或经过一次换乘的线路集合）然后再考虑与的交集情况，若不为空集，则换乘2次可到达终点站；若为空集，则必须换乘3次或3次以上通过分别考虑上、下行与环行的不同，可得到由站点经线路到达站点所需时间及费用分别为 （其中、分别表示取整）（二）最佳线路模型通过确定换乘次数及线路选择模型后，可能存在换乘次数相同的多种路线选择的问题，为了选择最佳线路，现建立该模型。 在换乘次数相同的情况下确定此模型，所要考虑的问题是，所花时间与费用最小，现设为由导的最小换乘次数，则第种选择所花时间为：所需费用为（这里考虑到票价形式的不同）： （其中：a表示公共汽车换乘时间， 表示取整） 再通过最小花费函数F（时间，票价）

10、，考虑到双目标函数，进行对时间和费用进行权重，其中表示在第种选择下，第次乘车行驶的站点数，进行量纲归一化（这里设最大时间为180分钟，最大费用为8元），从而最佳路线为使最小的而优化问题的解。 （二）模型的算法（基于广度优先遍历的公交换乘的搜索算法）由于模型二的有关数据来源于模型一，因此合并模型一与模型二的算法为：步骤1：输入乘车的起始站点和目的站点，确定公交数据库。步骤2：搜索公交数据库，经过起始站点和目的站点的公交线路保留为、 。步骤3：判断与是否相交，若相交则确定交点（可供选择的直达路线）并记录起始点和目的站点在该线路上是第几站；若不交，则转入下一步。步骤4：搜索公交数据库，将公交线路，所

11、包含的公交站点存为可能的公交换站点集A2,比较A2与B2是否相交,若相交,则确定交点(可供选择的中转站)并记录该点所在的公交线路及该站点在线上的第几站.进一步计算乘车站数,时间与费用,并记录.（三）模型的求解根据上述模型与求解，用Matlab编制程序输入给定的6对起始站点，先直接调用程序1(附录1)判断是否为直达，由程序的结果可以知道6对站点均不能直达，因此就调用程序2(附录2)，程序结果显示一次转乘可以到达终点的有:(1)、S3359S1828；(共11种选择)(3)、S0971S0485: (共13种选择)(4)、S0008S0073； (共101种选择)(6)、S0087S3676； (

12、共2种选择)把程序中所有结果进行处理，对总站数，时间，费用进行升序排序，得出如(图表1)表格，包括了开始点S3359转乘一次到达终点S1828的所有线路，并包括每条线路的各种因素，全部结果可以查看(附录3)，运用最佳线路选择模型原理，首先考虑总站数最少，如果总站数相同，接着就考虑时间的长短，选择时间最短，接着考虑费用最小。(图2)由上图可以看到总站数最少为32，时间最短为101分钟，费用最少为3元， 用最佳线路模型中最小花费可以选择出最优路线有两条分别如下:其余路线的最优线路同理可得，所有一次转乘的最优线路结果见附录4通过程序的调用，运行 (2)、S1557S0481 ，(5)、S0148S0

13、485，可知两对站点不能转乘一次到到达，故要二次转乘，调用程序3(附录5)，整理结果得到如(图3)和(图4)的线路表示图: (2)、S1557S0481所有路线:(图3)(5)、S0148S0485所有路线:(图4)同理利用最佳路线的选择方法，可得:(2)、S1557S0481最优路线:(2)、S0148S0485最优路线:由于这时已经把送给6对起始站终到站之间的最佳路线找出了，不用继续转乘。如果还要转乘，就要继续利用程序求解，但是现实生活中一般不会转乘超过两次。问题二在日常生活中，人们乘坐的公共交通工具往往包括公汽，地铁等，特别是在大城市，交通路网相对发达，交通工具类型相对较多，各种交通工具

14、又各自有其特点如：地铁可以有效控制时间，快速便捷，但一般不在家门口，必须通过步行或乘坐其他交通工具才能到达；而公汽站点多，线路线网发达，但速度忙，容易受路况影响，究竟选择何种交通工具乘坐，逐渐成为人们必须考虑的问题。现同时考虑公汽与地铁两种交通工具，要研究任意两站点通过何种交通工具选择最佳线路的问题。在此问题上也是通过从始点站能否找到直达线路或者换乘来到达终点站，如下图5：地铁站地铁站公汽站公汽站终点站 图5现考虑只可直达或者换乘一次，有以下几种情形：（一）若始点站为地铁站，则有：（二）若始点站为公汽站，则有（三）若出现换乘两次或两次以上，同理可得。根据上述分析，运用换乘次数及线路选择模型、广

15、度优先遍历的公交换乘的搜索算法来求出任意两站点之间是否存在交集，通过判断A是否存在集合，可得到是否有直达或换乘的次数，从而选择最佳路线。若换乘次数相同时，可能存在多种线路可供选择条件下，乘客根据个人的需要选择时间最小或者票价最少或者时间和票价的最优组合,通过对影响路线选择的主要因素如时间、票价等因素进行权重。有以下几种情形：1.当存在直达时，比较地铁与公汽在相同站点数与不同站点数所需要的时间，票价，从而选择最佳线路；2.当要换乘时，比较地铁与公汽在相同站点数与不同站点数所需要的时间，票价，从而选择最佳线路；3.当既存在直达又有换乘时，比较地铁与公汽在相同站点数与不同站点数所需要的时间，票价，从

16、而选择最佳线路；从上述分析，确定时间，票价模型如下：（其中g,q分别表示是乘公汽，地铁，）（其中d=0表示只乘地铁直达，否则为1，表示取整）再定义最小花费函数F（时间，票价），对时间和票价进行权重,并进行量纲归一化（这时设最大时间为180分钟，最大费用为8元）：利用上述模型和算法，可得到对站点的线路选择情况，如下图： 由上述图表，可知(3)、S0971S0485，(4)、S0008S0073 ， (5)、S0148S0485通过换乘地铁比较节省时间，如果(1)、S3359S1828 ， (2)、S1557S0481 ， (6)、S0087S3676，选择换乘地铁的话所要花费的时间比坐公交车更慢

17、，问题三从上述问题可以发现只有当不同线路之间具有公共站点时才能够进行转车，这样计算出来的结果有时并不符合实际情况，比如在实际出行时只需换乘二次便可到达目的地，但计算出来的结果却需要换乘三次或四次。出现这种情况的原因是忽视了现实生活中人们步行小段距离再转车的现象。具体地说，人们在转车时，并不是下车后直接在下车的站点处转车，往往需步行一小段距离到附近的站点去转车。人们选择这种方式通常可以减少换乘次数，而且这种换车方式也是由站点的分布情况所决定的。紧邻是一个半定量的距离概念，用以描述公交站点空间位置上的距离关系，通常是根据人们为习惯和平均公交路段长度来决定的。紧邻站点的存在使得人们在选择换乘路线时多

18、了一个考虑，就是如果在某一点下车后没有直接换乘的车次，还可以考虑附近的站点是否有换乘车次。根据这种思想， 本文对上面的算法进行了改进，即在换乘时，加入对紧邻站点的判断和分析。这种算法更加符合站点的分布情况以及人们出行时的实际选择情况。从前面的公交乘客出行心理调查统计表可以看出,换乘次数最少是公交乘客出行时考虑的第一重要因素,所以就以换乘次数最少作为最优路径算法的第一约束目标,而出行耗时最少虽是公交乘客考虑的第二重要因素,但因为其难以准确测算,所以选择易于量化的出行距离最短作为第二约束目标。可以通过建立最小成本路径模型,得到最佳线路.然后运用最优路径改进算法的基本思想为分别从起点A、终点B出发,

19、通过比较公交网络上各车站的可换乘车站,追索A到B的可能路径,然后比较各可能路径的距离,来确定最小成本路径。设S(I)(I=1,2,m)(m为正整数)为经过A或其附近的线路集。T(J)(J= 1,2,n)(n为正整数)为经过B或其附近的线路集。E(I,U)(U= 1,2,p,p为正整数)为线路S(I)上的站点。F(J,V)(V= 1,2,q,q为正整数)为线路T(J)上的站点。R(K)(K= 1,2,g)(g为正整数)为经过E(I,U)的线路。Y(O)(O= 1,2,z)(z为正整数)为经过F(J,V)的线路。G(K,W)(W= 1,2,i)(i为正整数)为线路R(K)上的站点。L(O,X)(X

20、= 1,2,j)(j为正整数)为线路Y(O)上的站点。d(m,n)表示站点m与站点n之间沿道路的距离。w表示乘客在换车时步行距离的最大心理承受值,它是一个人为干预的经验值,与公交站点间的平均长度呈线性相关。对于站点m与站点n之间的紧邻关系,可以用一个不等式来表示:d(m,n) =w。根据经验表明,即使在上海这样的大都市的公交网络上,换4次车即乘坐5条线路的公交车,方可到达目的地的情况都是很少发生的6。所以根据杭州市公交线路的实际情况,本文认为三次以内的转车是比较合理的,超过三次的转车的情况在这里不予考虑。算法的步骤如下:(1)输入乘车的起始站点A及目的站点B;(2)求经过站点A的所有线路集S(

21、I)和经过站点B的所有线路集T(J) ;(3)判断S(I) =T(J)吗?如果有,则找到了从站点A到站点B的直达线路S(I)即T(J) ,输出结果,结束运算,如果没有则进行下一步。(4)求线路S(I)上的站点E(I,U)以及线路T(J)上的站点F(J,V) ; (5)判断是否存在相同站点,即E(I,U) =F(J,V) ,或者存在紧邻站点,即满足d(E,F) =w;如果满足E(I,U) =F(J,V) ,则线路S(I),T(J)即为一次转车的线路,E(I,U)即为转车站点且换车时不用更换站点;如果满足E(I,U)F(J,V)但满足d(E,F) =w,则线路S(I),T(J)即为一次转车的线路,

22、E(I,U)即为转车站点但换车时要步行到紧邻站点F(J,V)。如果没有,再执行下面。(6)求经过E(I,U)的线路集R(K) ,经过F(J,V)的线路集Y(O) ;(7)判断R(K) =Y(O)吗?如果有,则线路S(I),R(K),T(J)为两次换车的线路,换车站点为E(I,U)和F(J,V) ,输出结果,结束运算;如果没有,则执行下面。(8)求线路R(K)上的站点G(K,W)和线路Y(O)上的站点L(O,X) ;(9)判断是否存在相同站点,即G(K,W) =L(O,X) ,或者存在紧邻站点,即满足d(G,L) =w;如果满足G(K,W) =L(O,X) ,则线路S(I),R(K),Y(O),

23、T(J)即为三次转车的线路,E(I,U),G(K,W),F(J,V)即为转车站点,且换车时不用更换站点;如果满足G(K,W)L(O,X)但满足d(G,L) =w,则在站点G(K,W)转车时要步行到紧邻站点L(O,X)。在上述情况中,满足条件的线路可能不止一种,这时再计算每种方案的乘车距离,取距离最短的乘车方案,输出结果。五、模型的检验我们的模型主要功能就是查找两个任意站点之间的最优线路，通过求解问题一和问题二后，把模型找到的所有路线，通过在原数据中选择性对照，检验可得找到的线路是可令两站点通过线路可达，接着比较各条路线的最优性，得到的最优路线就是模型找到的最优路线。通过检验，模型的结果和现实是

24、吻合的，表明模型准确率高稳定性好。六、模型的评价和改进优点：1仅考虑公汽线路的情况下，为了得出任意两站点之间的最佳线路，运用换乘次数及线路选择模型，通过对各线路各站点分析，比较经过任意两站点的线路集合，从而得到可直达线路或换乘的次数以及公共站点。该模型从数集角度分析，容易判断任意两集合是否存在交点，易于计算，效果理想。2.根据换乘次数及线路选择模型，利用广度优先遍历的公交换乘搜索算法，容易解决寻找线路问题，并对数据进行遍历，在理论上一定可以找到最优路线，其准确率高，操作简单。3 在考虑多种交通工具情况下，要得到任意两站点之间的最佳线路，运用此模型和算法在MATLAB上仍很好地运行，结果令人满意

25、。不足之处：1进行初步建立模型时，忽略了道路、公交车的状况，得出的最佳线路不一定最佳，可能与实际情况相差很大，不能准确提供模型改进方向：可以考虑对那些因素进行灵敏度分析。2建立换乘次数及线路选择模型，运用广度优先遍历的公交换乘搜索算法，在实际应用上存在算法复杂，迭代次数过多，所耗的时间长。模型改进方向：建议采用Dijkstra算法。七、模型的推广和建议广度优先遍历类似于树的按层次遍历，采用的搜索方法的特点是尽可能先对横向进行搜索，其算法是一种应用极广的算法，不仅能应用本模型上，一定程度可以用于公交线路查询；其还可以应用于互联网上进行搜索信息，也可在交叉立方体应用，也可以解决农夫过河问题，解决有

26、向图重组规则次序，河流演进动态仿真的实现等等，因此很好应用于实际中，但其本身仍然存在着不足之处，需有待提高。七、附录清单附录一：（直达线路计算m文件）zhida.m;附录二：（一次换乘计算m文件）huan1.m;附录三：（一次换乘计算每条线路各因素结果excle文件）huan1.xls;附录四：（一次换乘计算最有线路结果excle文件）huanyou1.xls;附录五：（二次换乘计算m文件）huan2.m;八、参考文献文献1 赵静 但琦，数学建模与数学实验（第2版），北京，高等教育出版社，2003年。文献2 扈震 张发勇 刘书良，城市公交换乘数据模型研究及算法实现，电信网技术，第4期，第71-74页，2007年4月。文献3 王建林，基于换乘次数最少的城市公交网络最优路径算法，经济地理，第25卷第5期，第673-676，2005年9月。