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

122007高教社杯全国大学生数学建模竞赛B题【摘要】本文根据人们出行习惯、情绪等特点,确定任意两站点之间的最佳线路的模型和算法。在只考虑公汽的情况下，在以换乘次数最小为主要因素,通过建立换乘次数及线路选择模型,在要求时间，费用最小的条件下，通过进行权重分析，建立最小花费函数，从而得到最佳路线。通过运用广度优先遍历算法和MATLAB编程，由已知的数据运算得到任意给定两站点之间的所有线路选择及其最优线路。在同时考虑地铁、公汽线路时，沿用此模型思想、算法确定最佳路线。假设又考虑步行时间，可通过建立最小路径成本模型，运用最优路径改进算法，确定最优路线。最后针对对所作的模型、算法进行评价与推广，提出可行有效的改进如Dijkstra算法。【关键词】：公交最小换乘次数广度优先遍历最佳路线3一、问题重述这些年来，城市的公交系统有了很大发展，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。如何从实际情况出发考虑，满足查询者的各种不同需求。现需要解决的问题如下：分别在只考虑公交线路，同时考虑公交与地铁，或同时考虑已知站点之间的步行时间的情况下确定其最佳路线。（1）、仅考虑公汽线路，任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，在只考虑公交线路的情况下，求出以下6对已知站点之间的最佳路线（要有清晰的评价说明）。(1)、33591828SS(2)、15570481SS(3)、09710485SS(4)、00080073SS(5)、01480485SS(6)、00873676SS二、问题分析实现公交网络查询系统的最优路径查询的重点在于如何实现查询者的个人满意度最高的问题。在公交换乘的过程中，有多种优先策略考虑。比如换乘次数最少、费用最少、时间最短等。每个人考虑的重要因素不同，但大多数人对换乘次数的多少比较在意，因此我们考虑用基于换乘次数最少的公交换乘优先策略，其次考虑时间最短，最后考虑费用最少，这比较符合大众出行时的心理情况。对于只考虑公交换乘方案的问题一，则可依次寻找两站点间是否存在直达线路、一次换乘线路、二次换乘线路等直达线路一致，有结果则输出。若二次换乘仍没有结果则输出“没有找到换乘次数少于2次的最优换乘方案”，结束运算。对于问题二，需同时考虑公交与地铁线路，考虑到目前大众心理对地铁的便利性、快捷性的认同感，在考虑了换乘次数最少的情况下可优先考虑地铁换乘，其次再考虑公交换乘，其目的在于将行程的最大时间消耗不妨利用地铁的快捷减少时间上的损耗。对于问题三，在已知站点间的步行时间的条件下，对环行路线的影响较大，我们可只考虑环行路线。三、模型的假设和符号说明4（一）模型的假设：1．假设每路况和车况相同，不影响公交的正常运行，并且不考虑公交线路的运输能力的限制及拥挤影响；2．假设任意相邻两站点的距离相等，运行时间相同，等车时间相同；3．出行者总是按直达，1次换乘，2次换乘等的优先顺序选择线路；4．基本参数设定：相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）（二）符号说明：ijz——表示第i条路线，第j个站点的站名i=1..520,j=1..86；1s——表示为始点站；2s——表示为终点站；ikn——表示第i条线路k站点的站数；in——表示第i条线路的总站数；m——表示换乘的次数；0,1ib=——分别表示第i条路线为单一票价与分段计价；12Tr,r,i（）——表示在i条线路上由站点1r到站点2r所需要的时间；12Mr,r,i（）——表示在i条线路上由站点1r到站点2r所需要的票价；四、模型的建立，算法及求解（一）换乘次数及线路选择模型根据人们的出行习惯，在选择从A站到B站的乘车路线时，首先会先看经过A站的车是否有直接到B站的，若有，马上会选择直达车（图1（a））；如果存在不止一条的直达线路，再考虑距离、时间、票价等综合因素的乘车方案；如果没有直达车，就会考虑一次换乘的乘车方案：即经过A站的车与经过B站的车有公共站点C吗？如果有，则可以在公共站点C处转车(图1（b）)；如果没有则又要考虑二次换乘的乘车方案，即乘坐经过A点的车到某一站C下车，经过C站点的车与经过B站点的车是否有公共站点D，如果有就再到D转车，两次转车可到达B站(图1（c）)；如果没有，则需要三次换乘或三次以上才可到目的地。考5虑到人们的心理、情绪等特点，可设4m(人们换乘次数的最大容忍程度)，大连市89条线路，376个不同的车站，结果显示直达的占7.17%，换乘一次的占53.38%，换乘两次的占38.07%，换乘两次找不到目标站的占1.37%。（可见四次之内的换乘是比较合理的，超过四次的换乘是没有意义的，不予以考虑）图1公交线路选择图问题一建模时，将同一线路的上行、下行看作两条线路，通过对线路重新命名可以区分。按照人们出行乘车的心理特点，本文提出换乘次数及线路选择模型，通过此模型寻找经过始点站和终点站的各线路集合，再比较两集合是否有交点，从而选择是否通过直达还是换乘的线路到达终点站。即：（1）设始点站1S、终点站2S的线路，分别建立经过这两站点的所有线路的集合：11ijAsizr22ijAsizr（2）判断两集合1Ar和2Ar是否有公共交点：1．若12AArAr，则从始点站r1到终点站r2可直达且A中元素为可选路线。2．。若12AArAr，则表明从始点站r1到终点站r2不可直达，必须通过换乘方法才能达到终点站。令1ij1Br=ziAr2ij2Br=ziAr(其中iBr表示可与ir直达的所有站点所在集合)（1）、若12BBrBr，则通过换乘一次可到达终点站，B中的点为换乘站点，并可确定线路，该过程可以建模下去（2）、若12BBrBr，则表明要到终点站，必须换乘2次以上才能到达，运用上述原理，找出从ri可直达或经过一次换乘的线路集合，再判断两集合的是否存在交集：令1ij1Cr=iZBr2ij2Cr=iZBr（其中iCr表示ri可直达或经过一次换乘的线路集合）6然后再考虑1Cs与2Cs的交集情况，若不为空集，则换乘2次可到达终点站；若为空集，则必须换乘3次或3次以上通过分别考虑上、下行与环行的不同，可得到由站点1r经线路i到达站点2r所需时间及费用分别为31321irir1221iirir12nniirirnn-n*,TTr,r,i=+*n+n-n*T单行或上行和下行（），环行12,,12601TrriiMr,r,i=b（）（其中211n-nirirni+、12,,60Trri分别表示取整）（二）最佳线路模型通过确定换乘次数及线路选择模型后，可能存在换乘次数相同的多种路线选择的问题，为了选择最佳线路，现建立该模型。在换乘次数相同的情况下确定此模型，所要考虑的问题是，所花时间与费用最小，现设m为由1S导2S的最小换乘次数，则第k种选择所花时间为：113mkikiTnam所需费用为（这里考虑到票价形式的不同）：201ikniiPb（其中：a表示公共汽车换乘时间，20ikn表示取整）再通过最小花费函数F（时间，票价），考虑到双目标函数，进行对时间和费用进行权重，其中ikn表示在第k种选择下，第i次乘车行驶的站点数，进行量纲归一化（这里设最大时间为180分钟，最大费用为8元），从而最佳路线为使F最7小的k而优化问题minF的解。1808kkTMF（二）模型的算法（基于广度优先遍历的公交换乘的搜索算法）由于模型二的有关数据来源于模型一，因此合并模型一与模型二的算法为：步骤1：输入乘车的起始站点start和目的站点over，确定公交数据库。步骤2：搜索公交数据库，经过起始站点start和目的站点over的公交线路保留为A1、B1。步骤3：判断A1与B1是否相交，若相交则确定交点（可供选择的直达路线）并记录起始点和目的站点在该线路上是第几站；若不交，则转入下一步。步骤4：搜索公交数据库，将公交线路A1，B1所包含的公交站点存为可能的公交换站点集A2,比较A2与B2是否相交,若相交,则确定交点(可供选择的中转站)并记录该点所在的公交线路及该站点在线上的第几站.进一步计算乘车站数,时间与费用,并记录.（三）模型的求解根据上述模型与求解，用Matlab编制程序输入给定的6对起始站点，先直接调用程序1(附录1)判断是否为直达，由程序的结果可以知道6对站点均不能直达，因此就调用程序2(附录2)，程序结果显示一次转乘可以到达终点的有:(1)、S3359→S1828；(共11种选择)(3)、S0971→S0485:(共13种选择)(4)、S0008→S0073；(共101种选择)(6)、S0087→S3676；(共2种选择)把程序中所有结果进行处理，对总站数，时间，费用进行升序排序，得出如(图表1)表格，包括了开始点S3359转乘一次到达终点S1828的所有线路，并包括每条线路的各种因素，全部结果可以查看(附录3)，运用最佳线路选择模型原理，首先考虑总站数最少，如果总站数相同，接着就考虑时间的长短，选择时间最短，接着考虑费用最小。(图2)由上图可以看到总站数最少为32，时间最短为101分钟，费用最少为3元，用最佳线路模型中最小花费可以选择出最优路线有两条分别如下:8其余路线的最优线路同理可得，所有一次转乘的最优线路结果见附录4通过程序的调用，运行(2)、S1557→S0481，(5)、S0148→S0485，可知两对站点不能转乘一次到到达，故要二次转乘，调用程序3(附录5)，整理结果得到如(图3)和((图4)的线路表示图:(2)、S1557→S0481所有路线:(图3)(5)、S0148→S0485所有路线:(图4)同理利用最佳路线的选择方法，可得:(2)、S1557→S0481最优路线:(2)、S0148→S0485最优路线:9由于这时已经把送给6对起始站→终到站之间的最佳路线找出了，不用继续转乘。如果还要转乘，就要继续利用程序求解，但是现实生活中一般不会转乘超过两次。问题二在日常生活中，人们乘坐的公共交通工具往往包括公汽，地铁等，特别是在大城市，交通路网相对发达，交通工具类型相对较多，各种交通工具又各自有其特点如：地铁可以有效控制时间，快速便捷，但一般不在家门口，必须通过步行或乘坐其他交通工具才能到达；而公汽站点多，线路线网发达，但速度忙，容易受路况影响，究竟选择何种交通工具乘坐，逐渐成为人们必须考虑的问题。现同时考虑公汽与地铁两种交通工具，要研究任意两站点通过何种交通工具选择最佳线路的问题。在此问题上也是通过从始点站能否找到直达线路或者换乘来到达终点站，如下图5：图5现考虑只可直达或者换乘一次，有以下几种情形：（一）若始点站为地铁站，则有：地铁地铁地铁直达地铁站地铁站换乘终点站公汽站换乘（二）若始点站为公汽站，则有地铁站地铁站公汽站公汽站终点站10公汽地铁公汽地铁站公汽站终点站公汽站换乘（三）若出现换乘两次或两次以上，同理可得。根据上述分析，运用换乘次数及线路选择模型、广度优先遍历的公交换乘的搜索算法来求出任意两站点之间是否存在交集，通过判断A是否存在集合，可得到是否有直达或换乘的次数，从而选择最佳路线。若换乘次数相同时，可能存