数学建模——乘公交看奥运.doc

2010高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 烟台大学文经学院 参赛队员 (打印并签名) ：1. 苑婷婷 2. 黄继龙 3. 张海峰 指导教师或指导教师组负责人 (打印并签名)： 日期： 2010 年 9 月 6 日赛区评阅编号（由赛区组委会评阅前进行编号）：乘公交，看奥运摘要随着城市交通系统的日益发达，线路的选择问题也日益严重。本文通过对北京交通路线的分析，并从实际情况出发考虑，建立了满足查询者各种不同需求的最佳路线的查询模型，并用程序加以实现。首先，对所有路线进行预处理，只筛选出从起点到终点换乘两次以下的可行路径，以减少计算量。问题一是只考虑公汽路线的情况下，在考虑查询者的各种不同需求的基础上建立了五个模型。他们分别为最短路径模型、最短时间路径模型、最少换乘路径模型、最省钱路径模型以及满意度最高路径选择模型。其中，满意度最高的路径模型是通过层次分析法，给出路径长度，时间，钱数，换乘数这四个评价指标对应的权重，通过加权法计算各个可行路径的评价值，给出最佳路径。问题二是在问题一的基础上，增加了地铁路线，先将地铁站点转化成公交站点。在地铁路线转化为公交路线的基础上，修改了问题一的五个模型，实现更方便、准确的搜索。问题三在前两问的基础上考虑站点间的步行，修改问题二中的模型。考虑到步行过长不合理，因此只选择步行少于3站的路线，减少数据量。使模型更符合现实。通过建立上述模型，可以实现公交路径的选择。前两问给出6对起始站终到站之间的最佳路线。第三问通过Java编程实现所有点之间最佳路径的选择问题。关键词：路经筛选；最短路径；层次分析法；加权法；最佳路径201 问题重述随着交通系统的快速发展，交通路线的选择问题已成为人们关注的焦点。例如第29届奥运会在北京举行期间，有大量观众到现场观看奥运比赛，其中大部分人都选择乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。要求针对市场需求，从实际情况出发考虑，满足查询者的各种不同需求，开发一个解决公交线路选择问题的自主查询计算机系统。根据已给数据解决以下三个问题。1.1 问题一仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4) 、S0008S0073 (5)、S0148S0485 (6)、S0087S36761.2 问题二要求同时考虑公汽与地铁线路，解决问题一所述的问题。1.3 问题三假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2 问题分析2.1 查询需求分析分析查询者的需求可将问题分为以下五种情况建立模型，分别为最短路径模型、最短时间路径模型、最少换乘路径模型、最省钱路径模型以及满意度最高路径选择模型，即用户可能要查询路径最短的，时间最短的，换乘最少的，最省钱的，以及综合四个因素而成的最满意的路径。因此三个问题都分为以上五种建立模型。2.2 问题一分析在只考虑公汽的情况下，若查询所有的可以从起点到终点的路径，程序的时间复杂度很高。因此建立模型时需要先进行筛选，把换乘过多的情况排除掉，来减少复杂度。2.3 问题二分析问题二的关键在于地铁路线如何转化为公汽路线处理，可以将地铁站点转化为公交站点处理。2.4 问题三分析在考虑到步行时，也要根据步行站数不能太多来筛选路线，以便减少程序的复杂性。3 模型假设(1) 假设站点之间的距离相等。(2) 假设不考虑交通堵塞和其他延误车辆速度的问题。(3) 假设相邻公汽站平均行驶时间为3分钟(包括停车时间)。(4) 假设相邻地铁站平均行驶时间为2.5分钟(包括停站时间)。(5) 假设公汽换乘公汽平均耗时为5分钟(其中步行时间2分钟)。(6) 假设地铁换乘地铁平均耗时为4分钟(其中步行时间2分钟)。(7) 假设地铁换乘公汽平均耗时为7分钟(其中步行时间4分钟)。(8) 假设公汽换乘地铁平均耗时为6分钟(其中步行时间4分钟)。(9) 假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。(10) 公汽票价分为两种，单一票价和分段计价两种，单一票价为1元，分段计价为 020站：1元；2140站：2元；40站以上：3元。(11) 地铁票价为3元(无论地铁线路之间是否换乘)。4 符号说明：查询者要查询的起点。： 查询者要查询的终点。：路线所经过点的集合。：地铁路线所经过的地铁站点对应公交站点的集合，。： 第种交通路线乘坐公汽需要经过的所有站点个数。： 第种交通路线中乘坐线路的公汽需要经过的站数。： 第种路线需要乘坐地铁所要经过的站数。： 第种路线所需时间。：第种路线所需花费的钱数。： 第种路线中乘坐公交中为单一票制1元的个数。：第种路线中乘坐地铁的次数。：第种路线需要公汽换乘公汽的次数。：第种路线需要地铁换乘地铁的次数。：第种路线需要地铁换乘公汽的次数。：第种路线需要公汽换乘地铁的次数。： 相邻公汽站平均行驶时间。： 相邻地铁站平均行驶时间。： 公汽换乘公汽平均耗时。： 地铁换乘地铁平均耗时。： 地铁换乘公汽平均耗时。： 公汽换乘地铁平均耗时。：站点到站点需要的步行时间。模型建立4.1 问题一模型建立在只考虑公汽的情况下，根据用户的不同需求建立以下五种路径选择模型。由于换乘次数太多是很不合理的，最大的忍耐程度是有限的，假设最大的忍耐度为2，即最多换乘两次。可画出如下的示意图，其中=0，1，2。图1. 换乘图如图1所示的换乘方式，为直达路径；，公交路线为有一条交点的路径，即需换乘一次的路径；、公交路线为有两个交点的路径，即需要换乘两次到达目的地的路径。直达路径的求法：对于线路，满足，(1)则为站点到站点的直达路径。换乘一次的路径求法：线路，满足，(2)则、为站点到站点的换乘一次的需要乘坐的路线。换乘两次的路径求法：线路，满足，(3)则、为站点到站点的换乘两次需要乘坐的路线。查找到以上三种可行路径，再用以下的方法查找出满足查询者的各种不同需求的最佳路线。4.1.1 最短路径模型由于假设各站之间的距离相等，因此最短路径也就是经站点最少的路径。首利用程序查出所有由起点到终点可行路线，并通过记录每条路径所经过的站点数。因此只需求满足的路线。4.1.2 最短时间路径模型最短时间路径，即查找由起点到终点的耗时最少的路径。首利用程序查出所有由起点到终点可行路线，由于路径所耗时间包括乘车时间以及换乘所用时间，因此需记录每条路径所经过的站点数以及该路径所需换乘次数。因此只需求满足的路线，其中。 (4)4.1.3 最少换乘路径模型查找最少换乘路径，首先利用程序查出所有由起点到终点可行路线，并记录每条路径所需换乘次数，因此只需求满足的路线。4.1.4 最省钱路径模型由于公汽的收费分为两种，一种是通价票1元，另一种是分段计价的票价为：020站：1元；2140站：2元；40站以上：3元，所以要分别记录该路径上乘坐这两种车的次数。查找最省钱路径，首先利用程序查出所有由起点到终点换乘在2次以下的可行路线，每条路径所需换乘次数，以及其中是通价1元的车辆次数和非通价1元的路线需要经过的站数。 (5)因此，查找最省钱路径只需找满足式(5)的路径。4.1.5 满意度最高路径选择模型综合以上四个因素，利用层次分析法可建立满意度最高路径。图2. 层次模型图建立路径满意程度的判断矩阵。 (6)矩阵通过列归一化处理，行求和等操作后可得特征向量。 (7)矩阵的特征向量式(5)的规一化处理后得到 ， (9)。 (10)带入式(10)对矩阵的一致性检验，通过一致性检验，认为判断矩阵的一致性是可以接受的，因此得出表1权重表。准则层权重0.1070.4550.197 0.241 表4.1. 最终的权重表因此根据表1权重的大小，可以列出下式。 (11)首先对数据无量纲化处理，再根据式(11)求出各个路线的评价值，评价值最小的即为满意度最高的路径。4.2 问题二模型建立将地铁线路考虑到模型中，根据假设(9)可以将地铁路线转化为公汽路线。首先，求出地铁站对应的各个公交站点组成的点集，就可以将地铁路线看成公交路线。再利用式(1)、(2)、(3)所示的方法求解换乘2次以下的可行路径。4.2.1 最短路径模型由于假设各站之间的距离相等，因此最短路径也就是经站点最少的路径。首利用程序查出所有由起点到终点可行路线，并通过记录每条路径所经过的站点数。因此只需求满足的路线。4.2.2 最短时间路径模型添加地铁路线后，由于地铁的站点间的乘车时间、换乘时间与公汽不同，因此要单独计算。最短时间路径，即查找由起点到终点的耗时最少的路径。首利用程序查出所有由起点到终点可行路线，并记录每条路径所经过的站点数以及该路径所需换乘次数、。因此只需求满足的路线，其中。 (12)4.2.3 最少换乘路径模型查找最少换乘路径，首先利用程序查出所有由起点到终点可行路线，并记录每条路径上四种换乘方式对应的次数、 ，有。(13)满足式(13)的路径即为换乘最少即可到到目的地的路径。4.2.4 最省钱路径模型查找最省钱路径，首先利用程序查出所有由起点到终点可行路线，每条路径所需换乘次数，以及其中是通价1元的车辆次数，第种交通路线中乘坐线路的公汽需要经过的站数，第种交通路线中乘坐地铁的次数。 (14)因此，查找最省钱路径只需找满足式(14)的路径。4.2.5 满意度最高路径选择模型根据表1权重的大小，可以列出下式。 (15)首先对数据无量纲化处理，再根据式(15)求出各个路线的评价值，值最小的即为满意度最高的路径。4.3 问题三模型建立由于考虑到站点之间都可用步行的方式到达，而步行是要消耗时间而不需要费用的，但考虑到走的站数越多费用越少，但步行的站点过多是不合理的，因此限制步行的站数不能多于3站。4.3.1 最短路径模型由于假设各站之间的距离相等，因此最短路径也就是经站点最少的路径。首利用程序查出所有由起点到终点可行路线，并通过记录每条路径所经过的站点数。因此只需求满足的路线。4.3.2 最短时间路径模型最短时间路径，即查找由起点到终点的耗时最少的路径。首利用程序查出所有由起点到终点可行路线，并通过记录每条路径所经过的站点数以及该路径所需换乘次数。因此只需求满足的路线，其中。 (16)4.3.3 最少换乘路径模型查找最少换乘路径，首先利用程序查出所有由起点到终点可行路线，并记录每条路径上四种换乘方式对应的次数、 ，有。(17)满足式(17)的路径即为换乘最少即可到到目的地的路径。4.3.4 最省钱路径模型由于考虑到站点之间都可用步行的方式到达，而步行是要消耗时间而不需要费用。考虑到走的站数越多费用越少，但步行的站点过多是不合理的，因此限制步行的站数不能多于4站。查找最省钱路径，首先利用程序查出所有由起点到终点可行路线，每条路径所需换乘次数，以及其中是通价1元的车辆次数，第种交通路线中乘坐线路的公汽需要经过的站数，第种交通路线中乘坐地铁的次数。 (18)因此，查找最省钱路径只需找满足式(18)的路径。4.3.5 满意度最高路径选择模型根据表1权重的大小，可以列出下式。 (19)首先对数据无量纲化处理，再根据式(19)求出各个路线的评价值，值最小的即为满意度最高的路径。5 模型实现5.1 问题一模型求解如果所得到的可行路径中满足模型要求的路线很多，那么只取同时满足模型五中的评价值最小之中的3条路线作为代表，可得如下的表格。5.1.1 模型一最短路径模型表问题一(1)S3359S1828的最短路径 因素路径路径路经站数时间花费换乘数评价值1L015(下行)S2903L485(环行)S1784L167(下行)1864320.670962L123(上行)S2903L485(环行)S1784L167(下行)1864320.670963L469(下行)S2027L485(环行)S1784L217(下行)1864320.67096表问题一(2)S1557S0481的最短路径 因素路径路径路经站数时间花费换乘数评价值1L084(下行)S1919L189(下行)S3186L460(下行)32106320.82632L363(下行)S1919L189(下行)S3186L460(下行)32106320.8263表问题一(3)S0971S0485的最短路径 因素路径路径路经站数时间花费换乘数评价值1L013(下行)S2517L290(环行)S2159L469(上行)31103320.7333表问题一(4)S0008S0073的最短路径 因素路径路径路经站数时间花费换乘数评价值1L043(下行)S1383L290(环行)S2184L345(上行)1967320.75032L198(上行)S1691L290(环行)S2184L345(上行)1967320.75033L198(上行)S3766L296(环行)S2184L345(上行)1967320.7503表问题一(5)S0148S0485的最短路径 因素路径路径路经站数时间花费换乘数评价值1L308(上行)S0036L156(上行)S2210L147(下行)32106320.63092L308(上行)S0036L156(上行)S3332L147(下行)32106320.63093L308(上行)S0036L156(上行)S3351L147(下行)32106320.6309表问题一(6)S0087S3676的最短路径 因素路径路径路经站数时间花费换乘数评价值1L021(下行)S0088L231(环行)S0427L097(上行)1246320.77172L206(上行)S0088L231(环行)S0427L097(上行)1246320.77173L454(下行)S0088L231(环行)S0427L462(下行)1246320.77175.1.2 模型二最短时间模型有数据分析到，模型二的数据结果与模型一的完全相同，分别见表、表、表、表、表、表。5.1.3 模型三最省钱路径模型有数据得到(1)、(2)、(3)、(5)的答案与模型一相同，分别见表、表、表、表，而(4)、(6)的答案如下。表问题一(4)S0008S0073的最省钱路径 因素路径路径路经站数时间花费换乘数评价值1L159(下行)S2683L058(下行)2683210.62892L159(下行)S0291L058(下行)2683210.62893L463(下行)S2083L057(上行)2683210.6289表问题一(6)S0087S3676的最短路径 因素路径路径路经站数时间花费换乘数评价值1L454(上行)S3496L209(下行)2065210.719972L454(上行)S1893L209(下行)2271210.760865.1.4 模型四最少换乘路径由数据得到第(2)、(5)的答案与模型一相同，见表、表；(4)、(6)与模型三答案相同，见表、表；而(1)、(3)的答案如下。表问题一(1)S3359S1828的最少换乘路径 因素路径路径路经站数时间花费换乘数评价值1L436(下行)S1784L167(下行)32101310.73482L436(下行)S1784L217(下行)32101310.73483L436(下行)S1241L167(下行)34107310.7603表问题一(3)S0971S0485的最少换乘路径 因素路径路径路经站数时间花费换乘数评价值1L013(下行)S2184L417(下行)41128310.71742L013(下行)S0992L417(下行)41131310.72703L013(下行)S2322L417(下行)43134310.73665.1.5 模型五满意度最高路径由数据得到(1)、(2)、(5)的答案与模型一相同，见表、表、表；(4)、(6)与模型三答案相同，见表、表；(3)与模型四答案相同，见表。5.2 问题二模型求解如下表所示加入地铁后部分数据发生变化，而其他的由于地铁比较快因此最短路径和时间最短路径发生变化，而由于地铁比较贵，因此最省钱的模型没有变化。详细变化如表所示。表5.2.1问题二(2)S1557S0481的最短路径，时间最短路径 因素路径路径路经站数时间花费换乘数评价值1L084(下行)D20(S1919)T1(上行)D01(S0567)L166(上行)2185.5620.9952L363(下行)D20(S1919)T1(上行)D01(S0567)L166(上行)2185.5620.9953L084(下行)D04(S1919)T1(下行)D23(S0567)L166(上行)2185.5620.995表5.2.2问题二(3)S0971S0485的最短路径 因素路径路径路经站数时间花费换乘数评价值1L013(下行)S2517L290(环行)S2159L469(上行)31103320.73332L094(上行)D01(S0567)T1(上行)D21(S0466)L051(上行)3196520.97363L119(下行)D01(S0567)T1(上行)D21(S0466)L104(上行)3196520.9736表5.2.3问题二(4)S0008S0073的最短路径，时间最短路径 因素路径路径路经站数时间花费换乘数评价值1L200(上行)D15(S2534)T1(上行)D08(S0616)L345(上行)1355.5520.99142L200(上行)D09(S2534)T1(下行)D16(S0616)L345(上行)1355.5520.9914表5.2.4问题二(5)S0148S0485的最短路径 ，时间最短路径 因素路径路径路经站数时间花费换乘数评价值1L024(下行)D02(S1487)T1(上行)D21(S0464)L104(上行)2887.5520.756972L024(下行)D02(S1487)T1(上行)D21(S0464)L051(上行)2887.5520.756973L024(下行)D22(S1487)T1(下行)D03(S0464)L395(下行)2887.5520.75697表5.2.5问题二(6)S0087S3676最短、时间最短、费用最少、换乘最少、最满意的路径 因素路径路径路经站数时间花费换乘数评价值1T2(环行)1025300.39896 模型评价与分析6.1 模型评价该模型根据用户的不同的需求分为五个模型，更符合实际。通过层次分析法计算的权重计算评价值更有说服力。利用程序实现路线的筛选功能，排序功能，路径查找功能。6.2 模型缺点首先，由于在数据方面进行预处理使程序复杂度减小，程序运算速度快，但是在所求答案不精确。其次，由于模型五的权值赋予有一定的偏差，更看重时间方面，因此所得答案不一定准确。问题三由于没有具体数据因此只能建立模型而没有办法实现。参考文献1 雷一鸣，公交最优路径选择的数学模型计算法J，湖南城市学院学报，17卷：50页，2008年6月。2 康志瑜，王明生，城市道路交通网中最短路径搜索算法设计及其实现J，国防交通工程与技术，第1期：57页，2004年。3 向荣武，刘艳杰等，图论中最短路径问题的解法J，沈阳航空工业学院学报，第21卷第2期：86页，2004年。4 Btuce Eckel，Java编程思想M，北京：机械工业出版社，2007.6。附录代码附录1计算路径的各个因素值代码：public class Path implements Cloneable, Comparableprivate ArrayList path;private int num = 0;private int cost = 0;private int time = 0;private int change = 0;private double value = 0;public Path()path = new ArrayList();public int getNum()return num;public int getCost()return cost;public int getTime()return time;public int getChange()return change;public void computeValue(double aveNum, double aveTime, double aveTransfer, double aveCost)value=(0.107*num/aveNum+0.455*time/aveTime+0.197*change/aveTransfer+0.241*cost/aveCost);public void computing(ArrayList routeList)for(int i=1; ipath.size(); i=i+2)for(int j=0; jrouteList.size(); j+)Route route = routeList.get(j);if(route.getRoutName().equals(path.get(i)num+=route.getStationNum(path.get(i-1),path.get(i+1);cost += route.getCost(path.get(i-1), path.get(i+1);change = path.size()/2-1;time = num*3 + change*5;代码附录2路径排序代码：public class PathList private ArrayList pathList;public PathList()pathList = new ArrayList();public void addPath(Path list)pathList.add(list);public String toString()StringBuilder sb = new StringBuilder();for(int i=0; ipathList.size(); i+)sb.append(pathList.get(i).toString() + n);return sb.toString();public void computeValue()float aveNum = 0;float aveTime = 0;float aveTransfer = 0;float aveCost = 0;int sumNum = 0;int sumTime = 0;int sumTransfer = 0;int sumCost = 0;for(int i=0; ipathList.size(); i+)sumNum += pathList.get(i).getNum();sumTime += pathList.get(i).getTime();sumTransfer += pathList.get(i).getChange();sumCost += pathList.get(i).getCost();int size = pathList.size();aveNum = sumNum/size;aveTime = sumTime/size;aveTransfer = sumTransfer/size;aveCost = sumCost/size;for(int i=0; ipathList.size(); i+)pathList.get(i).computeValue(aveNum, aveTime, aveTransfer,aveCost);Object obj = pathList.toArray();Arrays.sort(obj);pathList.clear();for(int i=0; isize; i+)pathList.add(Path)obji);代码附录3搜索可行路径代码：public class SearchPath private String start;private String end;private ArrayList routeList;public SearchPath(String start, String end， ArrayList routeList)this.start = start;this.end = end;this.routeList = routeList;public PathList search()/包含起点的线路ArrayList passStart = new ArrayList(); /包含终点的线路ArrayList passEnd = new ArrayList(); /既不包含起点也不包含终点的线路ArrayList candidate = new ArrayList(); ArrayList bridgeStart = new ArrayList(); Path path = null; PathList pathChoser = new PathList(); for(int i=0; irouteList.size(); i+)path = new Path();ArrayListnodeList = routeList.get(i).getNodeList();if(nodeList.contains(start) & !nodeList.contains(end)passStart.add(routeList.get(i).cutRoute(start,true);if(!nodeList.contains(start) & nodeList.contains(end)passEnd.add(routeList.get(i).cutRoute(end,false);if(!nodeList.contains(start) & !nodeList.contains(end)candidate.add(routeList.get(i);if(nodeList.contains(start) & nodeList.contains(end)if(routeList.get(i).isConnection(start, end) = true)path.addNode(start,routeList.get(i).getRoutName(), end);puting(routeList);pathChoser.addPath(path);for(int i=0; ipassStart.size(); i+)ArrayListstartNode= passStart.get(i).getNodeList();for(int j=0; jpassEnd.size(); j+)ArrayListendNode= passEnd.get(j).getNodeList();ArrayListretainNode=(ArrayList) startNode.clone();retainNode.retainAll(endNode);if(retainNode.isEmpty() = false)for(int k=0; kretainNode.size();